Efficient Software Implementation of Ring-LWE Encryption

Ruan de Clercq; Sujoy Sinha Roy; Frederik Vercauteren; Ingrid Verbauwhede

Paper 2014/725

Efficient Software Implementation of Ring-LWE Encryption

Ruan de Clercq, Sujoy Sinha Roy, Frederik Vercauteren, and Ingrid Verbauwhede

Abstract

Present-day public-key cryptosystems such as RSA and Elliptic Curve Cryptography (ECC) will become insecure when quantum computers become a reality. This paper presents the new state of the art in efficient software implementations of a post-quantum secure public-key encryption scheme based on the ring-LWE problem. We use a 32-bit ARM Cortex-M4F microcontroller as the target platform. Our contribution includes optimization techniques for fast discrete Gaussian sampling and efficient polynomial multiplication. This implementation beats all known software implementations, on any architecture, by at least one order of magnitude. We further show that our scheme beats all ECC-based public-key encryption schemes by at least one order of magnitude. At 128-bit security we require 121166 cycles per encryption and 43324 cycles per decryption, while at a 256-bit security we require 261939 cycles per encryption and 96520 cycles per decryption. Gaussian sampling is done at an average of 28.5 cycles per sample.

Metadata

Available format(s): PDF
Publication info: Published elsewhere. Minor revision. Design, Automation and Test in Europe (DATE 2015). DATE 2015, March 09-13, 2015 IEEE.
Contact author(s): ruan declercq @ esat kuleuven be
History: 2015-01-13: last of 2 revisions; 2014-09-19: received; See all versions
Short URL: https://ia.cr/2014/725
License: CC BY

BibTeX

@misc{cryptoeprint:2014/725,
      author = {Ruan de Clercq and Sujoy Sinha Roy and Frederik Vercauteren and Ingrid Verbauwhede},
      title = {Efficient Software Implementation of Ring-LWE Encryption},
      howpublished = {Cryptology ePrint Archive, Paper 2014/725},
      year = {2014},
      note = {\url{https://eprint.iacr.org/2014/725}},
      url = {https://eprint.iacr.org/2014/725}
}