TY - GEN
T1 - Non-malleable encryption
T2 - 13th International Conference on Theory of Cryptography, TCC 2016
AU - Coretti, Sandro
AU - Dodis, Yevgeniy
AU - Tackmann, Björn
AU - Venturi, Daniele
N1 - Funding Information:
Sandro Coretti was supported by SNF project no. 200020-132794. Björn Tackmann was supported by the SNF Fellowship P2EZP2_155566 and NSF grants CNS-1228890 and CNS-1116800. Daniele Venturi was partially supported by the European Commission (Directorate-General Home Affairs) under the GAINS project HOME/2013/CIPS/AG/4000005057, and by the European Union’s Horizon 2020 research and innovation programme under grant agreement No 644666.
Publisher Copyright:
© International Association for Cryptologic Research 2016.
PY - 2016
Y1 - 2016
N2 - In a seminal paper, Dolev et al. [15] introduced the notion of non-malleable encryption (NM-CPA). This notion is very intriguing since it suffices for many applications of chosen-ciphertext secure encryption (IND-CCA), and, yet, can be generically built from semantically secure (IND-CPA) encryption, as was shown in the seminal works by Pass et al. [29] and by Choi et al. [9], the latter of which provided a black-box construction. In this paper we investigate three questions related to NM-CPA security: 1. Can the rate of the construction by Choi et al. of NM-CPA from IND-CPA be improved? 2. Is it possible to achieve multi-bit NM-CPA security more efficiently from a single-bit NM-CPA scheme than from IND-CPA? 3. Is there a notion stronger than NM-CPA that has natural applications and can be achieved from IND-CPA security? We answer all three questions in the positive. First, we improve the rate in the scheme of Choi et al. by a factor O(λ), where λ is the security parameter. Still, encrypting a message of size O(λ) would require ciphertext and keys of size O(λ2) times that of the IND-CPA scheme, even in our improved scheme. Therefore, we show a more efficient domain extension technique for building a λ-bit NM-CPA scheme from a single-bit NM-CPA scheme with keys and ciphertext of size O(λ) times that of the NM-CPA one-bit scheme. To achieve our goal, we define and construct a novel type of continuous non-malleable code (NMC), called secret-state NMC, as we show that standard continuous NMCs are not enough for the natural “encode-then-encrypt-bit-by-bit” approach to work. Finally, we introduce a new security notion for public-key encryption that we dub non-malleability under (chosen-ciphertext) self-destruct attacks (NM-SDA). After showing that NM-SDA is a strict strengthening of NM-CPA and allows for more applications, we nevertheless show that both of our results—(faster) construction from IND-CPA and domain extension from one-bit scheme—also hold for our stronger NM-SDA security. In particular, the notions of IND-CPA, NM-CPA, and NM-SDA security are all equivalent, lying (plausibly, strictly?) below IND-CCA security.
AB - In a seminal paper, Dolev et al. [15] introduced the notion of non-malleable encryption (NM-CPA). This notion is very intriguing since it suffices for many applications of chosen-ciphertext secure encryption (IND-CCA), and, yet, can be generically built from semantically secure (IND-CPA) encryption, as was shown in the seminal works by Pass et al. [29] and by Choi et al. [9], the latter of which provided a black-box construction. In this paper we investigate three questions related to NM-CPA security: 1. Can the rate of the construction by Choi et al. of NM-CPA from IND-CPA be improved? 2. Is it possible to achieve multi-bit NM-CPA security more efficiently from a single-bit NM-CPA scheme than from IND-CPA? 3. Is there a notion stronger than NM-CPA that has natural applications and can be achieved from IND-CPA security? We answer all three questions in the positive. First, we improve the rate in the scheme of Choi et al. by a factor O(λ), where λ is the security parameter. Still, encrypting a message of size O(λ) would require ciphertext and keys of size O(λ2) times that of the IND-CPA scheme, even in our improved scheme. Therefore, we show a more efficient domain extension technique for building a λ-bit NM-CPA scheme from a single-bit NM-CPA scheme with keys and ciphertext of size O(λ) times that of the NM-CPA one-bit scheme. To achieve our goal, we define and construct a novel type of continuous non-malleable code (NMC), called secret-state NMC, as we show that standard continuous NMCs are not enough for the natural “encode-then-encrypt-bit-by-bit” approach to work. Finally, we introduce a new security notion for public-key encryption that we dub non-malleability under (chosen-ciphertext) self-destruct attacks (NM-SDA). After showing that NM-SDA is a strict strengthening of NM-CPA and allows for more applications, we nevertheless show that both of our results—(faster) construction from IND-CPA and domain extension from one-bit scheme—also hold for our stronger NM-SDA security. In particular, the notions of IND-CPA, NM-CPA, and NM-SDA security are all equivalent, lying (plausibly, strictly?) below IND-CCA security.
UR - http://www.scopus.com/inward/record.url?scp=84952683015&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84952683015&partnerID=8YFLogxK
U2 - 10.1007/978-3-662-49096-9_13
DO - 10.1007/978-3-662-49096-9_13
M3 - Conference contribution
AN - SCOPUS:84952683015
SN - 9783662490952
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 306
EP - 335
BT - Theory of Cryptography - 13th International Conference, TCC 2016-A, Proceedings
A2 - Kushilevitz, Eyal
A2 - Malkin, Tal
PB - Springer Verlag
Y2 - 10 January 2016 through 13 January 2016
ER -