Efficient software implementation of ring-LWE encryption

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 r...

Full description

Saved in:
Bibliographic Details
Main Authors: de Clercq, Ruan, Roy, Sujoy Sinha, Vercauteren, Frederik, Verbauwhede, Ingrid
Format: Conference Proceeding
Language:English
Subjects:
discrete Gaussian sampling
Encryption
Gaussian distribution
Indexes
number theoretic transform
Polynomials
post-quantum secure
public-key encryption
Registers
ring learning with errors (ring-LWE)
Software
software implementation
Table lookup
Citations: Items that cite this one
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1530-1591
1558-1101
DOI:10.7873/DATE.2015.0378