Zero Knowledge

• Surveys and tutorials
  • Zero Knowledge Protocols and Small Systems (Hannu A. Aronsson, Helsinki UT)
  • bsy's Explanation of Zero Knowledge Proofs
  • Foundations of Cryptography (Oded Goldreich)
  • Zero-Knowledge: a tutorial by Oded Goldreich
  • Lecture Notes on Cryptography (Shafi Goldwasser, Mihir Bellare, 1996-2001)
  • Zero-Knowledge twenty years after its invention (Oded Goldreich, 2002)
• Examining Certain (Zero-knowledge based) Cryptographic Protocols (Václav Matyás Jr)
• Zero-Knowledge and Secure Computation (Oded Goldreich)
• Papers
  • 1985
    • The knowledge complexity of interactive proof systems (Goldwasser, Micali, Rackoff, 1985)
  • 1986
    • How to Prove All NP-Statements in Zero-Knowledge and a Methodology of Cryptographic Protocol Design (Goldreich, Micali, Wigderson, 1986)
    • Non-transitive transfer of confidence: A perfect zero-knowledge interactive protocol for SAT and beyond (G. Brassard and C. Crépeau, FOCS 86)
    • Non-transitive transfer of confidence: A perfect zero-knowledge interactive protocol for SAT and beyond (Brassard, Crépeau, 1986)
    • Zero-knowledge simulation of boolean circuits (G. Brassard and C. Crépeau, Crypto 86)
    • [scholar]Minimum Disclosure Proofs of Knowledge (Guilles Brassard and David Chaum and Claude Crépeau, JCSS 1986)
  • 1987
    • Direct Minimum-Knowledge Computations (Russell Impagliazzo and Moti Yung, CRYPTO 87)
    • How to Solve any Protocol Problem (Goldreich, Micali, Wigderson, 1987)
    • [scholar]Random Self-Reducibility and Zero-Knowledge Interactive Proofs of Possession of Information (Tompa, Woll, 1987)
    • The complexity of perfect zero-knowledge (Fortnow, 1987)
    • Zero-Knowledge Proofs of Identity (Feige, Fiat, Shamir, STOC 1987)
    • All-or Nothing Disclosure of Secrets (Gilles Brassard, Claude Crépeau, Jean-Marc Robert, Crypto 1987)
    • Non-interactive zero-knowledge proof systems (A De Santis, S Micali, G Persiano, Crypto 1987)
  • 1988
    • Everything Provable is Provable in Zero-Knowledge (Michael Ben-Or, Oded Goldreich, Shafi Goldwasser, Johan Håstad, Joe Kilian, Silvio Micali, and Phillip Rogaway, CRYPTO 88)
    • A Practical Zero-Knowledge Protocol Fitted to Security Microprocessor Minimizing Both Transmission and Memory (Guillou, Quisquater, Eurocrypt 88)
    • Non-interactive zero-knowledge and its applications (Manuel Blum, Paul Feldman and Silvio Micali, STOC 88)
    • Minimum Disclosure Proofs of Knowledge (Brassard, Chaum, Crepeau, 1988)
  • 1989
    • Everything in NP can be argued in perfect zero-knowledge in a constant number of rounds (Guilles Brassard, Claude Crépeau, Moti Yung, 1989)
    • Practical Zero-Knowledge Proofs: Giving Hints and Using Deficiencies ( Joan Boyar, Katalin Friedl, Carsten Lund, 1989)
  • 1990
    • Multiple non-interactive zero knowledge proofs based on a single random string (Feige, Lapidot, Shamir, FOCS 90)
  • 1991
    • Statistical Zero-Knowledge Languages Can Be Recognized in Two Rounds (William Aiello, Johan Haståd, 1991)
    • Proofs that Yield Nothing But Their Validity or All Languages in NP Have Zero-Knowledge Proof Systems (Goldreich, Micali, Wigderson, JACM 1991)
    • [scholar]Noninteractive zero-knowledge proof of knowledge and chosen ciphertext attack (Rackoff, Simon, Crypto 91)
    • [scholar]Non-Interactive Zero-Knowledge Proof Systems (Blum, De Santis, Micali, Persiano, SIAM Comp, 1991)
    • [scholar]Perfect Zero-Knowledge Computationally Convincing Proofs for NP in Constant Rounds (Brassard, Crepeau, Yung, TCS 1991)
  • 1992
    • [scholar]Non-interactive Circuit Based Proofs and Non-Interactive Perfect Zero-Knowledge with Preprocessing (Ivan Damgaard, Eurocrypt 1992)
    • Perfect Zero-Knowledge Arguments for NP Can Be Based on General Complexity Assumptions (Moni Naor, Rafail Ostrovsky, Ramarathnam Venkatesan, Moti Yung, 1992)
    • An Efficient Non-Interactive Zero-Knowledge Proof System for NP with General Assumptions (Joe Kilian, Erez Petrank, 1995)
    • // See the later journal version of the previous paper
    • A Note on Efficient Zero-Knowledge Proofs and Arguments (Joe Kilian, STOC 1992)
  • 1993
    • One-way functions are essential for non-trivial zero-knowledge ( R Ostrovsky, A Wigderson, 1993)
  • 1995
    • Improved Efficient Arguments (Joe Kilian, CRYPTO 1995)
    • Zero-Knowledge Arguments and Public-Key Cryptography (Alfredo De Santis, Giovanni Di Crescenzo, Giuseppe Persiano, 1995)
  • 1996
    • The Power of Preprocessing in Zero-Knowledge Proofs of Knowledge (Alfredo De Santis and Giuseppe Persiano, JoC 1996)
    • How To Construct Constant-Round Zero-Knowledge Proof Systems for NP (Oded Goldreich and Ariel Kahan, JoC 1996)
    • Zero Knowledge and the Chromatic number (Feige, Kilian, 1996)
    • Certifying permutations: Non-interactive zero-knowledge based on any trapdoor permutation (M. Bellare and M. Yung, JoC 1996)
    • Proving Without Knowing (Markus Jakobsson, Moti Yung, Crypto 1996)
    • Linear Zero-Knowledge - A Note on Efficient Zero-Knowledge Proofs and Arguments (Ivan Damgård, Ronald Cramer, TR 1996 (later published in STOC 1997))
    • Adaptive zero knowledge and computational equivocation (Donald Beaver, STOC 1996)
  • 1997
    • Locally Random Reductions: Improvements and Applications (D. Beaver, J. Feigenbaum, J. Kilian, and P. Rogaway, JoC 1997)
    • A Language-Dependent Cryptographic Primitive (Toshiya Itoh, Yuji Ohta and Hiroki Shizuya, JoC 1997)
    • An Efficient Noninteractive Zero-Knowledge Proof System for NP with General Assumptions (Joe Kilian, Erez Petrank, JoC 1997)
      • Alternative download
    • Perfect Zero-Knowledge Arguments for NP Using Any One-Way Permutation (Moni Naor, Rafail Ostrovsky, Ramarathnam Venkatesan, Moti Yung, JoC 1998)
    • Round-optimal zero-knowledge arguments based on any one-way function (Mihir Bellare, Markus Jakobsson, Moti Yung, 1997)
  • 1998
    • Zero-Knowledge Proofs for Finite Field Arithmetic (Ronald Cramer, Ivan Damgaard)
    • Zero-Knowledge for Finite Field Arithmetic. Or: Can Zero-Knowledge be for Free? (Ronald Cramer, Ivan Damgård, 1998)
  • 1999
    • Non-Malleable Non-Interactive Zero Knowledge and Adaptive Chosen-Ciphertext Security (Amit Sahai, FOCS 1999)
    • On the Existence of 3-Round Zero-Knowledge Protocols (Satoshi Hada, Toshiaki Tanaka, 1999)
    • Divertible and Subliminal-Free Zero-Knowledge Proofs for Languages ( Mike Burmester, Yvo G. Desmedt, Toshiya Itoh, Kouichi Sakurai, Hiroki Shizuya, J Crypt 1999)
    • Non-interactive Zero-Knowledge: A Low-Randomness Characterization of NP (A. De Santis, G. Di Crescenzo, and G. Persiano, ICALP 99)
    • Multiple Non-Interactive Zero-Knowledge Proofs Under General Assumptions (U Feige, D Lapidot, A Shamir, SIAMCOMP 1999)
  • 2000
    • Efficient Zero-Knowledge Proofs of Knowledge Without Intractability Assumptions (Ronald Cramer, Ivan Damgård and Phil MacKenzie, PKC 2000)
    • Efficient Concurrent Zero-Knowledge in the Auxiliary String Model (Ivan Damgård, Eurocrypt 2000)
    • A note on the round-complexity of Concurrent Zero-Knowledge (Alon Rosen, 2001)
  • 2001
    • On Interactive Proofs with a Laconic Prover (O. Goldreich, S. Vadhan, and A. Wigderson, 2001)
    • On the Existance of 3-Round Zero-Knowledge Proof Systems (Matthew Lepinski, Silvio Micali, 2001)
    • Responsive Round Complexity and Concurrent Zero-Knowledge (Tzafrir Cohen, Joe Kilian, Erez Petrank, 2001)
    • Robust Non-Interactive Zero Knowledge (Alfredo De Santis, Giovanni Di Crescenzo, Rafail Ostrovsky, Giuseppe Persiano, Crypto 2001)
    • How To Go Beyond the Black-Box Simulation Barrier (Boaz Barak, FOCS 2001)
  • 2002
    • Universal Arguments and their Applications (Boaz Barak and Oded Goldreich, CCC 2002)
    • Strict Polynomial-time in Simulation and Extraction (Boaz Barak, Yehuda Lindell, ECCC TR02-026)
    • Concurrent Zero Knowledge Proofs with Logarithmic Round-Complexity (Manoj Prabhakaran, Amit Sahai, 2002)
    • 2-Round Zero-Knowledge and Proof Auditors (Cynthia Dwork, Larry Stockmeyer, 2000)
    • Randomness-Optimal Characterization of Two NP Proof Systems (Alfredo De Santis, Giovanni Di Crescenzo, Giuseppe Persiano, RANDOM 2002)
  • 2003
    • Lower Bounds for Non-Black-Box Zero-Knowledge (Boaz Barak, Yehuda Lindell and Salil Vadhan, FOCS 2003)
  • 2004
    • Secret-Key Zero-Knowlegde and Non-interactive Verifiable Exponentiation (Ronald Cramer and Ivan Damgård, TCC 2004)
    • List-Decoding of Linear Functions and Analysis of a Two-Round Zero-Knowledge Argument Cynthia Dwork, Ronen Shaltiel, Adam Smith, and Luca Trevisan, TCC 2004 (08.05.04)
    • Lower Bounds for Non-Black-Box Zero Knowledge (iBoaz Barak and Yehuda Lindell and Salil Vadhan, eprint 2004/226)
    • Universally Composable Protocols with Relaxed Set-Up Assumptions (Boaz Barak, Ran Canetti, Jesper Buus Nielsen, Rafael Pass, FOCS 2004)
    • Overcoming the Obstacles of Zero-Knowledge Watermark Detection (André Adelsbach, Markus Rohe, Ahmad-Reza Sadeghi, 2004)
  • 2005
    • Constant-Round Concurrently-Secure rZK in the (Real) Bare Public-Key Model (Moti Yung, Yunlei Zhao, ECCC TR05-048)
    • Concurrent Zero Knowledge without Complexity Assumptions (Daniele Micciancio, Shien Jin Ong, Amit Sahai, Salil Vadhan, ECCC TR05-093)
    • New and Improved Constructions of Non-Malleable Cryptographic Protocols (Rafael Pass and Alon Rosen, STOC 2005)
    • Concurrent Non-Malleable Commitments (Rafael Pass and Alon Rosen, FOCS 2005)
    • On Round-Efficient Argument Systems (Hoeteck Wee, ICALP 2005)
    • Practical Zero-Knowledge Arguments from \Sigma-Protocols (Yunlei Zhao, Robert H. Deng, Binyu Zang, Yiming Zhao, WINE 2005)
    • Generic yet Practical ZK Arguments from any Public-Coin HVZK (Yunlei Zhao, Jesper Buus Nielsen, Robert H. Deng, Feng Dengguo, ECCC 2005/162)
  • 2006
    • Perfect Non-Interactive Zero Knowledge for NP (Jens Groth, Rafail Ostrovsky, Amit Sahai, ECCC TR05-097)
    • [scholar]Non-interactive Zaps and New Techniques for NIZK (Jens Groth, Rafail Ostrovsky and Amit Sahai, Crypto 2008)
    • Simulation-sound NIZK Proofs for a Practical Language and Constant Size Group Signatures (Jens Groth, Asiacrypt 2006)
  • 2007
    • Efficient Non-interactive Proof Systems for Bilinear Groups (Jens Groth, Amit Sahai, 2007)
    • Non-Interactive Proofs for Integer Multiplication (Ivan Damgard and Rune Thorbek, eprint 2007/086)
  • 2008
    • [scholar]Which Languages have 4-Round Zero-Knowledge Proofs? (Jonathan Katz, TCC 2008)
    • [scholar]General Properties of Quantum Zero-Knowledge Proofs (Hirotada Kobayashi, TCC 2008)
    • [scholar]Interactive and Noninteractive Zero Knowledge are Equivalent in the Help Model (Andre Chailloux, Dragos Florin Ciocan, Iordanis Kerenidis and Salil Vadhan, TCC 2008)
    • [scholar]How to Achieve Perfect Simulation and a Complete Problem for Non Interactive Perfect Zero Knowledge (Lior Malka, TCC 2008)
    • [scholar]On Constant-Round Concurrent Zero-Knowledge (Rafael Pass and Muthuramakrishnan Venkitasubramaniam, TCC 2008)
    • [scholar]An Equivalence between Zero Knowledge and Commitments (Shien Jin Ong and Salil Vadhan, TCC 2008)
    • [scholar]The Round-Complexity of Black-Box Zero-Knowledge: A Combinatorial Characterization (Daniele Micciancio and Scott Yilek)
  • 2011
    • [scholar]Progression-Free Sets and Sublinear Pairing-Based Non-Interactive Zero-Knowledge Arguments (Helger Lipmaa)
  • Non-interactive Zero-knowledge []
    • Non-interactive zero-knowledge proof systems (A De Santis, S Micali, G Persiano, Crypto 1987)
    • Non-interactive zero-knowledge and its applications (Manuel Blum, Paul Feldman and Silvio Micali, STOC 88)
    • Multiple non-interactive zero knowledge proofs based on a single random string (Feige, Lapidot, Shamir, FOCS 90)
    • An Efficient Noninteractive Zero-Knowledge Proof System for NP with General Assumptions (Joe Kilian, Erez Petrank, JoC 1997)
      • Alternative download
    • Non-interactive Zero-Knowledge: A Low-Randomness Characterization of NP (A. De Santis, G. Di Crescenzo, and G. Persiano, ICALP 99)
    • Non-Malleable Non-Interactive Zero Knowledge and Adaptive Chosen-Ciphertext Security (Amit Sahai, FOCS 1999)
    • Multiple Non-Interactive Zero-Knowledge Proofs Under General Assumptions (U Feige, D Lapidot, A Shamir, SIAMCOMP 1999)
    • Randomness-Optimal Characterization of Two NP Proof Systems (Alfredo De Santis, Giovanni Di Crescenzo, Giuseppe Persiano, RANDOM 2002)
    • Efficient NIZK in CRS or weaker models
      • An Efficient Noninteractive Zero-Knowledge Proof System for NP with General Assumptions
        (Joe Kilian, Erez Petrank, JoC 1997)
        • Alternative download
      • Robust Non-Interactive Zero Knowledge
        (Alfredo De Santis, Giovanni Di Crescenzo, Rafail Ostrovsky, Giuseppe Persiano, Crypto 2001)
      • Universally Composable Protocols with Relaxed Set-Up Assumptions
        (Boaz Barak, Ran Canetti, Jesper Buus Nielsen, Rafael Pass, FOCS 2004)
      • Secret-Key Zero-Knowlegde and Non-interactive Verifiable Exponentiation
        (Ronald Cramer and Ivan Damgård, TCC 2004)
      • Perfect Non-Interactive Zero Knowledge for NP
        (Jens Groth, Rafail Ostrovsky, Amit Sahai, ECCC TR05-097)
      • [scholar]Non-interactive Zaps and New Techniques for NIZK
        (Jens Groth, Rafail Ostrovsky and Amit Sahai, Crypto 2008)
      • Simulation-sound NIZK Proofs for a Practical Language and Constant Size Group Signatures
        (Jens Groth, Asiacrypt 2006)
      • Efficient Non-interactive Proof Systems for Bilinear Groups
        (Jens Groth, Amit Sahai, 2007)
      • [scholar]Progression-Free Sets and Sublinear Pairing-Based Non-Interactive Zero-Knowledge Arguments
        (Helger Lipmaa)
  • Concurrent Zero-knowledge []
    • Concurrent Zero-Knowledge: Reducing the Need for Timing Constraints (Cynthia Dwork, Amit Sahai, CRYPTO '98)
    • Concurrent Zero-Knowledge (Dwork, Naor, Sahai, STOC '98)
    • On Concurrent Zero-Knowledge with Pre-Processing (Giovanni Di Crescenzo, Rafail Ostrovsky, 1999)
    • Joe Kilian, Erez Petrank, 2000 (20.09.01)
    • Efficient and Concurrent Zero-Knowledge from any public coin HVZK protocol (Daniele Micciancio, Erez Petrank, ECCC TR02-045)
    • A note on the round-complexity of Concurrent Zero-Knowledge (Alon Rosen, 2001)
    • Responsive Round Complexity and Concurrent Zero-Knowledge (Tzafrir Cohen, Joe Kilian, Erez Petrank, 2001)
    • Concurrent Zero Knowledge Proofs with Logarithmic Round-Complexity (Manoj Prabhakaran, Amit Sahai, 2002)
    • Concurrent Zero Knowledge without Complexity Assumptions (Daniele Micciancio, Shien Jin Ong, Amit Sahai, Salil Vadhan, ECCC TR05-093)
  • Resettable Zero-knowledge []
    • Resettable Zero-Knowledge (Ran Canetti, Oded Goldreich, Shafi Goldwasser and Silvio Micali, 2000)
    • Min-Round Resettable Zero-Knowledge in the Public-Key Model (Silvio Micali, Leonid Reyzin, 2000)
    • Resettably-Sound Zero-Knowledge and its Applications (Boaz Barak and Oded Goldreich and Shafi Goldwasser and Yehuda Lindell, eprint 2001/063)
    • Constant-Round Concurrently-Secure rZK in the (Real) Bare Public-Key Model (Moti Yung, Yunlei Zhao, ECCC TR05-048)
  • Non-Malleable Zero-knowledge []
    • Non-Malleable Non-Interactive Zero Knowledge and Adaptive Chosen-Ciphertext Security (Amit Sahai, FOCS 1999)
    • Robust Non-Interactive Zero Knowledge (Alfredo De Santis, Giovanni Di Crescenzo, Rafail Ostrovsky, Giuseppe Persiano, Crypto 2001)
    • New and Improved Constructions of Non-Malleable Cryptographic Protocols (Rafael Pass and Alon Rosen, STOC 2005)
    • Concurrent Non-Malleable Commitments (Rafael Pass and Alon Rosen, FOCS 2005)
  • Non-Interactive Zero Knowledge (Blum, De Santis, Micali, Persiano)
  • Statistical ZK proofs
    • Can Statistical Zero Knowledge be made Non-Interactive? or On the Relationship of SZK and NISZK ( Oded Goldreich, Amit Sahai, Salil Vadhan, 1998)
    • A Complete Problem for Statistical Zero Knowledge (Amit Sahai, Salil Vadhan, eprint 2000/056)
  • (Statistical) zero-knowledge arguments []
    • Potential PZK argument in the shared string model for a NP-complete language (based on DL)
      • [scholar]Non-interactive Circuit Based Proofs and Non-Interactive Perfect Zero-Knowledge with Preprocessing
        (Ivan Damgaard, Eurocrypt 1992)
    • Every language in NP has a PZK argument
      • Perfect Zero-Knowledge Computationally Convincing Proofs for NP in Constant Rounds
        (Brassard, Crepeau, Yung, TCS 1991)
    • Public-key public-randomness SZK arguments for every NP language
      • Zero-Knowledge Arguments and Public-Key Cryptography
        (Alfredo De Santis, Giovanni Di Crescenzo, Giuseppe Persiano, 1995)
    • Non-black-box arguments for every NP language (based on CRHF)
      • How To Go Beyond the Black-Box Simulation Barrier
        (Boaz Barak, FOCS 2001)
      • Universal Arguments and their Applications
        (Boaz Barak and Oded Goldreich, CCC 2002)
    • Efficient HVSZK arguments for bounded arithmetic
      • On Diophantine Complexity and Statistical Zero-Knowledge Arguments
        (Helger Lipmaa, ASIACRYPT 2003)
    • On Round-Efficient Argument Systems (Hoeteck Wee, ICALP 2005)
    • Generic yet Practical ZK Arguments from any Public-Coin HVZK (Yunlei Zhao, Jesper Buus Nielsen, Robert H. Deng, Feng Dengguo, ECCC 2005/162)
• Constant-round zero-knowledge proofs/arguments, round complexity
  • Everything in NP can be argued in perfect zero-knowledge in a constant number of rounds (Guilles Brassard, Claude Crépeau, Moti Yung, 1989)
  • How To Construct Constant-Round Zero-Knowledge Proof Systems for NP (Oded Goldreich and Ariel Kahan, JoC 1996)
  • Round-optimal zero-knowledge arguments based on any one-way function (Mihir Bellare, Markus Jakobsson, Moti Yung, 1997)
  • On the Existence of 3-Round Zero-Knowledge Protocols (Satoshi Hada, Toshiaki Tanaka, 1999)
  • On the Existance of 3-Round Zero-Knowledge Proof Systems (Matthew Lepinski, Silvio Micali, 2001)
  • A note on the round-complexity of Concurrent Zero-Knowledge (Alon Rosen, 2001)
  • Responsive Round Complexity and Concurrent Zero-Knowledge (Tzafrir Cohen, Joe Kilian, Erez Petrank, 2001)
  • Concurrent Zero Knowledge Proofs with Logarithmic Round-Complexity (Manoj Prabhakaran, Amit Sahai, 2002)
  • On Round-Efficient Argument Systems (Hoeteck Wee, ICALP 2005)
  • Constant-Round Concurrently-Secure rZK in the (Real) Bare Public-Key Model (Moti Yung, Yunlei Zhao, ECCC TR05-048)
• Combining practical ZK proofs
  • Proof Systems for General Statements about Discrete Logarithms (Jan Camenisch, Markus Stadler, 1997)
• PhD Theses
  • A Study of Statistical Zero-Knowledge Proofs (Salil Pravin Vadhan, 1999)
  • Zero-Knowledge with Public Keys (Leonid Reyzin, MIT 2001)
• Seminars, lecture courses
  • Interactive Proofs (Club for TCS, JHU, Spring 2001 (good source for papers))
  • Zero-knowledge (Helger Lipmaa, seminar at Helsinki UT, 2001)
  • Interactive Proofs, Zero-Knowledge and Secure Computation (Mihir Bellare, UCSD)
• @Proofs of Knowledge
• @Witness Hiding and Witness Indistinguishable Protocols

---

Cryptology Pointers by Helger Lipmaa
Got any suggestions or additional links? Mail to <helger.lipmaa>gmail.com
NB! If you find any broken links, please be kind and report them to me together with their current location!

(C) Helger Lipmaa 1997-2009.