Name
Abstract | ||
|---|---|---|
Non-malleability is an interesting and useful property which ensures that a cryptographic protocol preserves the independence of the underlying values: given for example an encryption ${\cal E}(m)$ of some unknown message m , it should be hard to transform this ciphertext into some encryption ${\cal E}(m^*)$ of a related message m *. This notion has been studied extensively for primitives like encryption, commitments and zero-knowledge. Non-malleability of one-way functions and hash functions has surfaced as a crucial property in several recent results, but it has not undergone a comprehensive treatment so far. In this paper we initiate the study of such non-malleable functions. We start with the design of an appropriate security definition. We then show that non-malleability for hash and one-way functions can be achieved, via a theoretical construction that uses perfectly one-way hash functions and simulation-sound non-interactive zero-knowledge proofs of knowledge (NIZKPoK). We also discuss the complexity of non-malleable hash and one-way functions. Specifically, we show that such functions imply perfect one-wayness and we give a black-box based separation of non-malleable functions from one-way permutations (which our construction bypasses due to the "non-black-box" NIZKPoK based on trapdoor permutations). We exemplify the usefulness of our definition in cryptographic applications by showing that (some variant of) non-malleability is necessary and sufficient to securely replace one of the two random oracles in the IND-CCA encryption scheme by Bellare and Rogaway, and to improve the security of client-server puzzles. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1007/978-3-642-10366-7_31 | IACR Cryptology ePrint Archive |
Keywords | DocType | Volume |
random oracle,client server,hash function,proof of knowledge,zero knowledge,cryptographic protocol,one way function | Conference | 2009 |
ISSN | Citations | PageRank |
0302-9743 | 10 | 0.50 |
References | Authors | |
24 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Alexandra Boldyreva | 1 | 2297 | 114.80 |
| David Cash | 2 | 1289 | 43.10 |
| Marc Fischlin | 3 | 1709 | 92.71 |
| Bogdan Warinschi | 4 | 1514 | 68.98 |