**Self-Destruct Non-Malleability**

*Sandro Coretti and Yevgeniy Dodis and Björn Tackmann and Daniele Venturi*

**Abstract: **=== NOTE: This submission has been replaced by a corrected version (2015/772). ===

We introduce a new security notion for public-key encryption (PKE) that we dub non-malleability under (chosen-ciphertext) self-destruct attacks (NM-SDA), which appears to be the strongest natural PKE security notion below full-blown chosen-ciphertext (IND-CCA) security. In this notion, the adversary is allowed to ask many adaptive ``parallel'' decryption queries (i.e., a query consists of many ciphertexts) up to the point when the first invalid ciphertext is submitted. As such, NM-SDA security generalizes non-malleability against chosen plaintext attacks (NM-CPA, where only one parallel decryption query is allowed) and recently introduced indistinguishability against (chosen-ciphertext) self-destruct attacks (IND-SDA, where each adaptive query consists of a single ciphertext). After showing that NM-SDA is a {\em strict} strengthening of NM-CPA and IND-SDA and allows for more applications, we establish the following two results:

Domain Extension: For any $K > 1$, there is a black-box construction of a $K$-bit NM-SDA PKE scheme from a single-bit NM-SDA PKE scheme. Moreover, this can be done using only $O(\lambda)$ calls to the underlying single-bit NM-SDA scheme, where $\lambda$ is the security parameter. 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 ``expand-then-encrypt-bit-by-bit'' approach to work.

Black-Box Construction from IND-CPA: Prior work showed that NM-CPA secure PKE can be constructed from any IND-CPA secure PKE in a black-box way. Here we show that the same construction actually achieves our strictly stronger notion of NM-SDA security. (This requires a non-trivial extension of the original security proof to handle multiple parallel decryption queries.) Hence, the notions of IND-CPA, NM-CPA, IND-SDA and NM-SDA security are all equivalent, lying (plausibly, strictly?) below IND-CCA security. We also show how to improve the rate of the resulting NM-SDA scheme from quadratic to linear.

**Category / Keywords: **public-key cryptography / Pulbic-Key Encryption, Non-Malleable Codes, Domain-Extension

**Date: **received 21 Oct 2014, last revised 3 Aug 2015, withdrawn 3 Aug 2015

**Contact author: **corettis at inf ethz ch

**Available format(s): **(-- withdrawn --)

**Version: **20150803:154437 (All versions of this report)

**Short URL: **ia.cr/2014/866

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]