Cryptology ePrint Archive: Report 2014/725

Efficient Software Implementation of Ring-LWE Encryption

Ruan de Clercq, Sujoy Sinha Roy, Frederik Vercauteren, 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.

Category / Keywords:

Original Publication (with minor differences): Design, Automation and Test in Europe (DATE 2015). DATE 2015, March 09-13, 2015 IEEE.

Date: received 18 Sep 2014, last revised 13 Jan 2015

Contact author: ruan declercq at esat kuleuven be

Available format(s): PDF | BibTeX Citation

Version: 20150113:124821 (All versions of this report)

Short URL: ia.cr/2014/725

Discussion forum: Show discussion | Start new discussion