You are looking at a specific version 20170226:142325 of this paper. See the latest version.

Paper 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.

Note: Only acknowledgements added.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Financial Cryptography and Data Security 2015
Keywords
Lattice-Based CryptographyEncryption SchemeLattice-Based Assumptions
Contact author(s)
elbansarkhani @ cdc informatik tu-darmstadt de
History
2017-02-26: last of 5 revisions
2014-09-19: received
See all versions
Short URL
https://ia.cr/2014/733
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.