Paper 2017/049

LARA - A Design Concept for Lattice-based Encryption

El Bansarkhani Rachid

Abstract

Lattice-based encryption schemes still suffer from a low message throughput per ciphertext and inefficient solutions towards realizing enhanced security characteristics 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. In particular, many constructions still encrypt data in an one-time-pad manner considering LWE instances as random vectors added to a message, most often encoded bit vectors. 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. Combinations of both concepts are also possible. In this paper we revisit this approach and propose amongst others a standard model variant of the scheme as well as several techniques in order to improve the message throughput per ciphertext. Furthermore, we introduce a new discrete Gaussian sampler, that is inherently induced by the encryption scheme itself, and 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( \log q)$ polynomials following previous constructions. Finally, we give a security analysis as well as an efficient implementation of the scheme instantiated with the new trapdoor construction. In particular, we attest high message throughputs (message expansion factors close to 1-2) at running times comparable to the CPA-secure encryption scheme from Lindner and Peikert (CT-RSA 2011). 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. This feature is naturally induced by the characteristics of LWE.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Contact author(s)
elbansarkhani @ cdc informatik tu-darmstadt de
History
2017-01-30: revised
2017-01-24: received
See all versions
Short URL
https://ia.cr/2017/049
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/049,
      author = {El Bansarkhani Rachid},
      title = {LARA - A Design Concept for Lattice-based Encryption},
      howpublished = {Cryptology ePrint Archive, Paper 2017/049},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/049}},
      url = {https://eprint.iacr.org/2017/049}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.