Non-malleable Encryption: Simpler, Shorter, Stronger
- PDF / 1,297,992 Bytes
- 50 Pages / 439.37 x 666.142 pts Page_size
- 63 Downloads / 214 Views
Non-malleable Encryption: Simpler, Shorter, Stronger∗ Sandro Coretti IOHK, Zurich, Switzerland [email protected]
Yevgeniy Dodis New York University, New York, USA [email protected]
Ueli Maurer ETH Zurich, Zurich, Switzerland [email protected]
Björn Tackmann DFINITY Foundation, Zurich, Switzerland [email protected]
Daniele Venturi Sapienza University of Rome, Rome, Italy [email protected] Communicated by Eike Kiltz Received 7 September 2016 / Revised 21 June 2020
Abstract. One approach toward 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 ∗ This paper is the full version of the papers “From Single-Bit to Multi-bit Public-Key Encryption via Nonmalleable Codes” (appeared in TCC 2015, LNCS 9014, pp. 532–560, Springer, 2015) and “Non-Malleable Encryption: Simpler, Shorter, Stronger” (appeared in TCC 2016-A, LNCS 9562, pp. 306–335, Springer, 2016). S. Coretti: Supported by SNF Project No. 200020-132794. Work done while author was at ETH Zurich. Y. Dodis: Partially supported by gifts from VMware Labs and Google, and NSF Grants 1319051, 1314568, 1065288, 1017471. U. Maurer: Supported by SNF Project No. 200020-132794. B. Tackmann: Work done while author was at ETH Zurich and UC San Diego. Author was partially supported by the SNF Fellowship P2EZP2_155566 and NSF Grants CNS-1228890 and CNS-1116800. U. Maurer: Supported by SNF Project No. 200020-132794.
© International Association for Cryptologic Research 2020
S. Coretti et al. 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 indistinguishability under self-destruct attacks (IND-SDA) 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 IND-SDA-secure PKE, provided that the underlying code is continuously non-malleable against (a reduced form of) bit-wise
Data Loading...
