Cryptology ePrint Archive: Report 2018/1009

LAC: Practical Ring-LWE Based Public-Key Encryption with Byte-Level Modulus

Xianhui Lu and Yamin Liu and Zhenfei Zhang and Dingding Jia and Haiyang Xue and Jingnan He and Bao Li and Kunpeng Wang

Abstract: We propose an instantiation of public key encryption scheme based on the ring learning with error problem, where the modulus is at a byte level and the noise is at a bit level, achieving one of the most compact lattice based schemes in the literature. The main technical challenges are a) the decryption error rates increases and needs to be handled elegantly, and b) we cannot use the Number Theoretic Transform (NTT) technique to speed up the implementation. We overcome those limitations with some customized parameter sets and heavy error correction codes. We give a treatment of the concrete security of the proposed parameter set, with regards to the recent advance in lattice based cryptanalysis. We present an optimized implementation taking advantage of our byte level modulus and bit level noise. In addition, a byte level modulus allows for high parallelization and the bit level noise avoids the modulus reduction during multiplication. Our result shows that \LAC~is more compact than most of the existing (Ring-)LWE based solutions, while achieving a similar level of efficiency, compared with popular solutions in this domain, such as Kyber.

Category / Keywords: public-key cryptography / lattice based cryptography, learning with errors, error correction, NIST post-quantum cryptography standardization.

Date: received 16 Oct 2018, last revised 19 Dec 2019

Contact author: luxianhui at outlook com

Available format(s): PDF | BibTeX Citation

Note: revise to update the parameters according to efficiency improvement and security analysis result.

Version: 20191219:090122 (All versions of this report)

Short URL: ia.cr/2018/1009


[ Cryptology ePrint archive ]