Paper 2014/733

Augmented Learning with Errors: The Untapped Potential of the Error Term

Rachid El~Bansarkhani, Özgür Dagdelen, and Johannes Buchmann


The Learning with Errors (LWE) problem has gained a lot of attention in recent years leading to a series of new cryptographic applications. Specifically, it states that it is hard to distinguish random linear equations disguised by some small error from truly random ones. Interestingly, cryptographic primitives based on LWE often do not exploit the full potential of the error term beside of its importance for security. To this end, we introduce a novel LWE-close assumption, namely Augmented Learning with Errors (A-LWE), which allows to hide auxiliary data injected into the error term by a technique that we call message embedding. In particular, it enables existing cryptosystems to strongly increase the message throughput per ciphertext. We show that A-LWE is for certain instantiations at least as hard as the LWE problem. This inherently leads to new cryptographic constructions providing high data load encryption and customized security properties as required, for instance, in economic environments such as stock markets resp. for financial transactions. The security of those constructions basically stems from the hardness to solve the A-LWE problem. As an application we introduce (among others) the first lattice-based replayable chosen-ciphertext secure encryption scheme from A-LWE.

Note: Only acknowledgements added.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. Financial Cryptography and Data Security 2015
Lattice-Based CryptographyEncryption SchemeLattice-Based Assumptions
Contact author(s)
elbansarkhani @ cdc informatik tu-darmstadt de
2017-02-26: last of 5 revisions
2014-09-19: received
See all versions
Short URL
Creative Commons Attribution


      author = {Rachid El~Bansarkhani and Özgür Dagdelen and Johannes Buchmann},
      title = {Augmented Learning with Errors: The Untapped Potential of the Error Term},
      howpublished = {Cryptology ePrint Archive, Paper 2014/733},
      year = {2014},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.