Open main menu
Home
Random
Recent changes
Special pages
Community portal
Preferences
About Wikipedia
Disclaimers
Incubator escapee wiki
Search
User menu
Talk
Dark mode
Contributions
Create account
Log in
Editing
Zero-knowledge proof
(section)
Warning:
You are not logged in. Your IP address will be publicly visible if you make any edits. If you
log in
or
create an account
, your edits will be attributed to your username, along with other benefits.
Anti-spam check. Do
not
fill this in!
== History == Zero-knowledge proofs were first conceived in 1985 by [[Shafi Goldwasser]], [[Silvio Micali]], and [[Charles Rackoff]] in their paper "The Knowledge Complexity of Interactive Proof-Systems".<ref name="knowledgecomplexity" /> This paper introduced the IP hierarchy of interactive proof systems (''see [[interactive proof system]]'') and conceived the concept of ''knowledge complexity'', a measurement of the amount of knowledge about the proof transferred from the prover to the verifier. They also gave the first zero-knowledge proof for a concrete problem, that of deciding [[quadratic residue|quadratic nonresidues]] mod {{var|m}}. Together with a paper by [[László Babai]] and [[Shlomo Moran]], this landmark paper invented interactive proof systems, for which all five authors won the first [[Gödel Prize]] in 1993. In their own words, Goldwasser, Micali, and Rackoff say: <blockquote> Of particular interest is the case where this additional knowledge is essentially 0 and we show that [it] is possible to interactively prove that a number is quadratic non residue mod ''m'' releasing 0 additional knowledge. This is surprising as no efficient algorithm for deciding quadratic residuosity mod ''m'' is known when ''m''’s factorization is not given. Moreover, all known ''NP'' proofs for this problem exhibit the prime factorization of ''m''. This indicates that adding interaction to the proving process, may decrease the amount of knowledge that must be communicated in order to prove a theorem. </blockquote> The quadratic nonresidue problem has both an [[NP (complexity)|NP]] and a [[co-NP]] algorithm, and so lies in the intersection of NP and co-NP. This was also true of several other problems for which zero-knowledge proofs were subsequently discovered, such as an unpublished proof system by Oded Goldreich verifying that a two-prime modulus is not a [[Blum integer]].<ref>{{cite journal |first=Oded |last=Goldreich |title=A zero-knowledge proof that a two-prime moduli is not a Blum integer |journal=Unpublished Manuscript |year=1985 }}</ref> [[Oded Goldreich]], [[Silvio Micali]], and [[Avi Wigderson]] took this one step further, showing that, assuming the existence of unbreakable encryption, one can create a zero-knowledge proof system for the NP-complete [[graph coloring problem]] with three colors. Since every problem in NP can be efficiently reduced to this problem, this means that, under this assumption, all problems in NP have zero-knowledge proofs.<ref>{{cite journal |first1=Oded |last1=Goldreich |first2=Silvio |last2=Micali |first3=Avi |last3=Wigderson |title=Proofs that yield nothing but their validity |journal=Journal of the ACM |volume=38 |issue=3 |pages=690–728 |doi=10.1145/116825.116852 |year=1991 |citeseerx=10.1.1.420.1478 |s2cid=2389804 }}</ref> The reason for the assumption is that, as in the above example, their protocols require encryption. A commonly cited sufficient condition for the existence of unbreakable encryption is the existence of [[one-way function]]s, but it is conceivable that some physical means might also achieve it. On top of this, they also showed that the [[graph nonisomorphism problem]], the [[complement (complexity)|complement]] of the [[graph isomorphism problem]], has a zero-knowledge proof. This problem is in co-NP, but is not currently known to be in either NP or any practical class. More generally, [[Russell Impagliazzo]] and [[Moti Yung]] as well as Ben-Or et al. would go on to show that, also assuming one-way functions or unbreakable encryption, there are zero-knowledge proofs for ''all'' problems in IP = PSPACE, or in other words, anything that can be proved by an interactive proof system can be proved with zero knowledge.<ref>Russell Impagliazzo, Moti Yung: Direct Minimum-Knowledge Computations. CRYPTO 1987: 40–51</ref><ref>{{cite book |first1=Michael |last1=Ben-Or |first2=Oded |last2=Goldreich |first3=Shafi |last3=Goldwasser |first4=Johan |last4=Hastad |first5=Joe |last5=Kilian |first6=Silvio |last6=Micali |first7=Phillip |last7=Rogaway |chapter=Everything provable is provable in zero-knowledge |editor-first=S. |editor-last=Goldwasser |title=Advances in Cryptology – CRYPTO '88 |volume=403 |series=Lecture Notes in Computer Science |pages=37–56 |publisher=Springer-Verlag |year=1990 }}</ref> Not liking to make unnecessary assumptions, many theorists sought a way to eliminate the necessity of [[one way function]]s. One way this was done was with ''multi-prover interactive proof systems'' (see [[interactive proof system]]), which have multiple independent provers instead of only one, allowing the verifier to "cross-examine" the provers in isolation to avoid being misled. It can be shown that, without any intractability assumptions, all languages in NP have zero-knowledge proofs in such a system.<ref>{{cite book | chapter-url=https://doi.org/10.1145/62212.62223 | doi=10.1145/62212.62223 | chapter=Multi-prover interactive proofs: How to remove intractability | title=Proceedings of the twentieth annual ACM symposium on Theory of computing - STOC '88 | date=1988 | last1=Ben-Or | first1=Michael | last2=Goldwasser | first2=Shafi | last3=Kilian | first3=Joe | last4=Widgerson | first4=Avi | pages=113–131 | isbn=0-89791-264-0 }}</ref> It turns out that, in an Internet-like setting, where multiple protocols may be executed concurrently, building zero-knowledge proofs is more challenging. The line of research investigating concurrent zero-knowledge proofs was initiated by the work of [[Cynthia Dwork|Dwork]], [[Moni Naor|Naor]], and [[Amit Sahai|Sahai]].<ref>{{cite journal |first1=Cynthia |last1=Dwork |first2=Moni |last2=Naor |first3=Amit |last3=Sahai |title=Concurrent Zero Knowledge |journal=Journal of the ACM |volume=51 |issue=6 |pages=851–898 |year=2004 |doi=10.1145/1039488.1039489 |citeseerx=10.1.1.43.716 |s2cid=52827731 }}</ref> One particular development along these lines has been the development of [[witness-indistinguishable proof]] protocols. The property of witness-indistinguishability is related to that of zero-knowledge, yet witness-indistinguishable protocols do not suffer from the same problems of concurrent execution.<ref>{{cite book |first1=Uriel |last1=Feige |first2=Adi |last2=Shamir |title=Proceedings of the twenty-second annual ACM symposium on Theory of computing - STOC '90 |chapter=Witness indistinguishable and witness hiding protocols |date=1990 |pages=416–426 |doi=10.1145/100216.100272 |isbn=978-0897913614 |citeseerx=10.1.1.73.3911 |s2cid=11146395 }}</ref> Another variant of zero-knowledge proofs are [[non-interactive zero-knowledge proof]]s. Blum, Feldman, and Micali showed that a common random string shared between the prover and the verifier is enough to achieve computational zero-knowledge without requiring interaction.<ref name="noninteractive" /><ref name="noninteractive2" />
Edit summary
(Briefly describe your changes)
By publishing changes, you agree to the
Terms of Use
, and you irrevocably agree to release your contribution under the
CC BY-SA 4.0 License
and the
GFDL
. You agree that a hyperlink or URL is sufficient attribution under the Creative Commons license.
Cancel
Editing help
(opens in new window)