TY - GEN
T1 - Efficient software implementation of ring-LWE encryption
AU - De Clercq, Ruan
AU - Roy, Sujoy Sinha
AU - Vercauteren, Frederik
AU - Verbauwhede, Ingrid
PY - 2015/4/22
Y1 - 2015/4/22
N2 - 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. Our implementation beats all known software implementations of ring-LWE encryption by a factor of at least 7. We further show that our scheme beats ECC-based public-key encryption schemes by at least one order of magnitude. At medium-term security we require 121 166 cycles per encryption and 43 324 cycles per decryption, while at a long-term security we require 261 939 cycles per encryption and 96 520 cycles per decryption. Gaussian sampling is done at an average of 28.5 cycles per sample.
AB - 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. Our implementation beats all known software implementations of ring-LWE encryption by a factor of at least 7. We further show that our scheme beats ECC-based public-key encryption schemes by at least one order of magnitude. At medium-term security we require 121 166 cycles per encryption and 43 324 cycles per decryption, while at a long-term security we require 261 939 cycles per encryption and 96 520 cycles per decryption. Gaussian sampling is done at an average of 28.5 cycles per sample.
KW - discrete Gaussian sampling
KW - number theoretic transform
KW - post-quantum secure
KW - public-key encryption
KW - ring learning with errors (ring-LWE)
KW - software implementation
UR - http://www.scopus.com/inward/record.url?scp=84945935254&partnerID=8YFLogxK
U2 - https://doi.org/10.7873/DATE.2015.0378
DO - https://doi.org/10.7873/DATE.2015.0378
M3 - Conference contribution
AN - SCOPUS:84945935254
SP - 339
EP - 344
BT - Proceedings of the 2015 Design, Automation and Test in Europe Conference and Exhibition, DATE 2015
PB - EDA Consortium
T2 - 2015 Design, Automation and Test in Europe Conference and Exhibition, DATE 2015
Y2 - 9 March 2015 through 13 March 2015
ER -