3-Message Zero Knowledge Against Human Ignorance
The notion of Zero Knowledge has driven the field of cryptography since its conception over thirty years ago. It is well established that two-message zero-knowledge protocols for NP do not exist, and that four-message zero-knowledge arguments exist under the minimal assumption of one-way functions....
| Main Authors: | , , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Springer-Verlag
2017
|
| Online Access: | http://hdl.handle.net/1721.1/111007 https://orcid.org/0000-0001-8361-6035 https://orcid.org/0000-0002-2666-0045 |
| _version_ | 1826209084140945408 |
|---|---|
| author | Bitansky, Nir Brakerski, Zvika Kalai, Yael Paneth, Omer Vaikuntanathan, Vinod |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Bitansky, Nir Brakerski, Zvika Kalai, Yael Paneth, Omer Vaikuntanathan, Vinod |
| author_sort | Bitansky, Nir |
| collection | MIT |
| description | The notion of Zero Knowledge has driven the field of cryptography since its conception over thirty years ago. It is well established that two-message zero-knowledge protocols for NP do not exist, and that four-message zero-knowledge arguments exist under the minimal assumption of one-way functions. Resolving the precise round complexity of zero-knowledge has been an outstanding open problem for far too long.
In this work, we present a three-message zero-knowledge argument system with soundness against uniform polynomial-time cheating provers. The main component in our construction is the recent delegation protocol for RAM computations (Kalai and Paneth, TCC 2016B and Brakerski, Holmgren and Kalai, ePrint 2016). Concretely, we rely on a three-message variant of their protocol based on a key-less collision-resistant hash functions secure against uniform adversaries as well as other standard primitives.
More generally, beyond uniform provers, our protocol provides a natural and meaningful security guarantee against real-world adversaries, which we formalize following Rogaway’s “human-ignorance” approach (VIETCRYPT 2006): in a nutshell, we give an explicit uniform reduction from any adversary breaking the soundness of our protocol to finding collisions in the underlying hash function. |
| first_indexed | 2024-09-23T14:17:00Z |
| format | Article |
| id | mit-1721.1/111007 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T14:17:00Z |
| publishDate | 2017 |
| publisher | Springer-Verlag |
| record_format | dspace |
| spelling | mit-1721.1/1110072022-10-01T20:21:43Z 3-Message Zero Knowledge Against Human Ignorance Bitansky, Nir Brakerski, Zvika Kalai, Yael Paneth, Omer Vaikuntanathan, Vinod Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Bitansky, Nir Vaikuntanathan, Vinod The notion of Zero Knowledge has driven the field of cryptography since its conception over thirty years ago. It is well established that two-message zero-knowledge protocols for NP do not exist, and that four-message zero-knowledge arguments exist under the minimal assumption of one-way functions. Resolving the precise round complexity of zero-knowledge has been an outstanding open problem for far too long. In this work, we present a three-message zero-knowledge argument system with soundness against uniform polynomial-time cheating provers. The main component in our construction is the recent delegation protocol for RAM computations (Kalai and Paneth, TCC 2016B and Brakerski, Holmgren and Kalai, ePrint 2016). Concretely, we rely on a three-message variant of their protocol based on a key-less collision-resistant hash functions secure against uniform adversaries as well as other standard primitives. More generally, beyond uniform provers, our protocol provides a natural and meaningful security guarantee against real-world adversaries, which we formalize following Rogaway’s “human-ignorance” approach (VIETCRYPT 2006): in a nutshell, we give an explicit uniform reduction from any adversary breaking the soundness of our protocol to finding collisions in the underlying hash function. National Science Foundation (U.S.) (Award CNS-1350619) National Science Foundation (U.S.) (Award CNS-1413964) 2017-08-23T19:25:34Z 2017-08-23T19:25:34Z 2016-10 Article http://purl.org/eprint/type/ConferencePaper 978-3-662-53640-7 978-3-662-53641-4 0302-9743 1611-3349 http://hdl.handle.net/1721.1/111007 Bitansky, Nir et al. “3-Message Zero Knowledge Against Human Ignorance.” Hirt, M. and Smith, A., editors. Theory of Cryptography. TCC 2016. Lecture Notes in Computer Science 9985 (2016): 57–83 © 2016 International Association for Cryptologic Research https://orcid.org/0000-0001-8361-6035 https://orcid.org/0000-0002-2666-0045 en_US http://dx.doi.org/10.1007/978-3-662-53641-4_3 Theory of Cryptography Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Springer-Verlag MIT Web Domain |
| spellingShingle | Bitansky, Nir Brakerski, Zvika Kalai, Yael Paneth, Omer Vaikuntanathan, Vinod 3-Message Zero Knowledge Against Human Ignorance |
| title | 3-Message Zero Knowledge Against Human Ignorance |
| title_full | 3-Message Zero Knowledge Against Human Ignorance |
| title_fullStr | 3-Message Zero Knowledge Against Human Ignorance |
| title_full_unstemmed | 3-Message Zero Knowledge Against Human Ignorance |
| title_short | 3-Message Zero Knowledge Against Human Ignorance |
| title_sort | 3 message zero knowledge against human ignorance |
| url | http://hdl.handle.net/1721.1/111007 https://orcid.org/0000-0001-8361-6035 https://orcid.org/0000-0002-2666-0045 |
| work_keys_str_mv | AT bitanskynir 3messagezeroknowledgeagainsthumanignorance AT brakerskizvika 3messagezeroknowledgeagainsthumanignorance AT kalaiyael 3messagezeroknowledgeagainsthumanignorance AT panethomer 3messagezeroknowledgeagainsthumanignorance AT vaikuntanathanvinod 3messagezeroknowledgeagainsthumanignorance |