LARA - A Design Concept for Lattice-based Encryption

AutorEl Bansarkhani, Rachid
ArtConference Proceedings
AbstraktLattice-based encryption schemes still suffer from a low message throughput per ciphertext and inefficient solutions towards realizing enhanced security properties such as CCA1- or CCA2-security. This is mainly due to the fact that the underlying schemes still follow a traditional design concept and do not tap the full potentials of LWE. Furthermore, the desired security features are also often achieved by costly approaches or less efficient generic transformations. Recently, a novel encryption scheme based on the A-LWE assumption (relying on the hardness of LWE) has been proposed, where data is embedded into the error term without changing its target distributions. By this novelty it is possible to encrypt much more data as compared to the classical approach. In this paper we revisit this approach and propose several techniques in order to improve the message throughput per ciphertext. Furthermore, we present a very efficient trapdoor construction of reduced storage size. More precisely, the secret and public key sizes are reduced to just 1 polynomial, as opposed to O(logq) polynomials following previous constructions. Finally, we give an efficient implementation of the scheme instantiated with the new trapdoor construction. In particular, we attest high message throughputs and low ciphertext expansion factors at efficient running times. Our scheme even ensures CCA (or RCCA) security, while entailing a great deal of flexibility to encrypt arbitrary large messages or signatures by use of the same secret key.
KonferenzFC 2019: 23rd International Conference on Financial Cryptography and Data Security