Paper 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

Abstract

Lattice based cryptography is one of the leading candidates of the post quantum cryptography. A major obstacle of deployment, though, is that its payload is relatively larger than the classical solutions, such as elliptic curve Diffie-Hellman. In this paper, we investigate the approach of reducing the key size and ciphertext size by decreasing the size of the modulus, and propose the first instantiation to the family of ring learning with error based solutions where the modulus is at a byte level. The main technical contributions of this paper are around the implementation side of the algorithms. With the use of large-block error correction code, we are able to propose parameter sets with small moduli while achieving a negligible decryption error rate. We investigate best known attacks, and give a concrete security estimation of the proposed parameter sets. Since our parameter sets are no longer compatible with number theoretic transform (NTT), we also present optimizations for ring multiplications. As a result, our scheme is more compact and nearly as efficient as popular solutions in this domain, such as NewHope and Kyber.

Note: revise to add "and" between the name of different authors