Relations Among Notions of Non-malleability for Encryption
Since its introduction in the early 90’s, the notion of non-malleability for encryption schemes has been formalized using a number of conceptually different definitional approaches—most notably, the “pragmatic” indistinguishability-based approach and the
- PDF / 590,413 Bytes
- 17 Pages / 430 x 660 pts Page_size
- 49 Downloads / 145 Views
2
Cornell U. Virginia 3 MIT
Abstract. Since its introduction in the early 90’s, the notion of nonmalleability for encryption schemes has been formalized using a number of conceptually different definitional approaches—most notably, the “pragmatic” indistinguishability-based approach and the “semantical” simulation-based approach. We provide a full characterization of these approaches and consider their robustness under composition. Keywords: Public-key Encryption, Non-malleability.
1
Introduction
The basic goal of an encryption scheme is to guarantee the privacy of data. A good formalization of privacy is the notion of semantic security as defined by Goldwasser and Micali [GM84]. Intuitively, semantic security guarantees that “whatever a polynomial-time machine can learn about a message given its encryption, it can learn even without seeing the encryption.” When encryption schemes are deployed in more complex environments, the demands for security of encryption grow beyond just the basic privacy requirement. Motivated by practical security requirements, the seminal work of Dolev, Dwork and Naor [DDN00] defined the notion of non-malleability—a qualitatively stronger notion of security for encryption schemes. In addition to the normal “privacy” guarantee, non-malleability ensures that it is infeasible for an adversary to modify a vector of ciphertexts α1 , . . . , αn into other ciphertexts of messages which are related to the decryption of α1 , . . . , αn . This stronger notion of security is critical for many practical applications. Two Formalizations. The notion of non-malleability for encryption schemes has been formalized using two different approaches: – The “Semantical” Simulation-based Approach. The definition presented in the original work of [DDN00] is a so-called “simulation-based” one. The main idea is to capture the requirement that an adversary having access to ciphertexts (and potentially a decryption oracle in case of CCA1/CCA2 attacks), will not be able to “cause more harm” than a simple adversary K. Kurosawa (Ed.): ASIACRYPT 2007, LNCS 4833, pp. 519–535, 2007. c International Association for Cryptology Research 2007
520
R. Pass, A. Shelat, and V. Vaikuntanathan
that does not see any ciphertexts and does not have access to a decryption oracle. This simulation-based definition of non-malleability is denoted SIM-NME, and like semantic security, the goal of this definition is to capture the “meaning” of non-malleability. As a result, it is often harder to directly prove that a scheme meets the simulation-based definition. – The “Pragmatic” Indistinguishability-based Approach. Bellare et.al. present a “comparison-based” formalization of non-malleability [BDPR98]. This notion does away with the “simulator” used in [DDN00] and instead captures non-malleability through an indistinguishability-style definition. Other indistinguishability-based definitions appear in [BS99, PSV06]. We denote by IND-NME the indistinguishability-based approach to defining nonmalleability. The goal of this indistinguishability-base
Data Loading...
