You are looking at a specific version 20150107:132527 of this paper. See the latest version.

Paper 2014/324

From Single-Bit to Multi-Bit Public-Key Encryption via Non-Malleable Codes

Sandro Coretti and Ueli Maurer and Björn Tackmann and Daniele Venturi

Abstract

One approach towards basing public-key encryption (PKE) schemes on weak and credible assumptions is to build ``stronger'' or more general schemes generically from ``weaker'' or more restricted ones. One particular line of work in this context was initiated by Myers and shelat (FOCS '09) and continued by Hohenberger, Lewko, and Waters (Eurocrypt '12), who provide constructions of multi-bit CCA-secure PKE from single-bit CCA-secure PKE. It is well-known that encrypting each bit of a plaintext string independently is not CCA-secure---the resulting scheme is *malleable*. We therefore investigate whether this malleability can be dealt with using the conceptually simple approach of applying a suitable non-malleable code (Dziembowski et al., ICS '10) to the plaintext and subsequently encrypting the resulting codeword bit-by-bit. We find that an attacker's ability to ask multiple decryption queries requires that the underlying code be *continuously* non-malleable (Faust et al., TCC '14). Since, as we show, this flavor of non-malleability can only be achieved if the code is allowed to ``self-destruct,'' the resulting scheme inherits this property and therefore only achieves a weaker variant of CCA security. We formalize this new notion of so-called *self-destruct CCA security (SD-CCA)* as CCA security with the restriction that the decryption oracle stops working once the attacker submits an invalid ciphertext. We first show that the above approach based on non-malleable codes yields a solution to the problem of domain extension for SD-CCA-secure PKE, provided that the underlying code is continuously non-malleable against a *reduced* form of bit-wise tampering. Then, we prove that the code of Dziembowski et al.\ is actually already continuously non-malleable against (even *full*) bit-wise tampering; this constitutes the first *information-theoretically* secure continuously non-malleable code, a technical contribution that we believe is of independent interest. Compared to the previous approaches to PKE domain extension, our scheme is more efficient and intuitive, at the cost of not achieving full CCA security. Our result is also one of the first applications of non-malleable codes in a context other than memory tampering.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Contact author(s)
corettis @ inf ethz ch
History
2015-08-03: last of 10 revisions
2014-05-10: received
See all versions
Short URL
https://ia.cr/2014/324
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.