Cryptology ePrint Archive: Report 2014/733

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

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

Abstract: 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.

Category / Keywords: public-key cryptography / Lattice-Based Cryptography, Encryption Scheme, Lattice-Based Assumptions

Original Publication (in the same form): Financial Cryptography and Data Security 2015

Date: received 19 Sep 2014, last revised 26 Feb 2017

Contact author: elbansarkhani at cdc informatik tu-darmstadt de

Available format(s): PDF | BibTeX Citation

Note: Only acknowledgements added.

Version: 20170226:142325 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]