Paper 2014/866
SelfDestruct NonMalleability
Sandro Coretti, Yevgeniy Dodis, 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 publickey encryption (PKE) that we dub nonmalleability under (chosenciphertext) selfdestruct attacks (NMSDA), which appears to be the strongest natural PKE security notion below fullblown chosenciphertext (INDCCA) 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, NMSDA security generalizes nonmalleability against chosen plaintext attacks (NMCPA, where only one parallel decryption query is allowed) and recently introduced indistinguishability against (chosenciphertext) selfdestruct attacks (INDSDA, where each adaptive query consists of a single ciphertext). After showing that NMSDA is a {\em strict} strengthening of NMCPA and INDSDA and allows for more applications, we establish the following two results: Domain Extension: For any $K > 1$, there is a blackbox construction of a $K$bit NMSDA PKE scheme from a singlebit NMSDA PKE scheme. Moreover, this can be done using only $O(\lambda)$ calls to the underlying singlebit NMSDA scheme, where $\lambda$ is the security parameter. To achieve our goal, we define and construct a novel type of continuous nonmalleable code (NMC), called secretstate NMC, as we show that standard continuous NMCs are not enough for the natural ``expandthenencryptbitbybit'' approach to work. BlackBox Construction from INDCPA: Prior work showed that NMCPA secure PKE can be constructed from any INDCPA secure PKE in a blackbox way. Here we show that the same construction actually achieves our strictly stronger notion of NMSDA security. (This requires a nontrivial extension of the original security proof to handle multiple parallel decryption queries.) Hence, the notions of INDCPA, NMCPA, INDSDA and NMSDA security are all equivalent, lying (plausibly, strictly?) below INDCCA security. We also show how to improve the rate of the resulting NMSDA scheme from quadratic to linear.
Metadata
 Available format(s)
  withdrawn 
 Category
 Publickey cryptography
 Publication info
 Preprint. MINOR revision.
 Keywords
 PulbicKey EncryptionNonMalleable CodesDomainExtension
 Contact author(s)
 corettis @ inf ethz ch
 History
 20150803: withdrawn
 20141022: received
 See all versions
 Short URL
 https://ia.cr/2014/866
 License

CC BY