Paper 2014/725

Efficient Software Implementation of Ring-LWE Encryption

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


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.

Available format(s)
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
2015-01-13: last of 2 revisions
2014-09-19: received
See all versions
Short URL
Creative Commons Attribution


      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{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.