Editing Zero-knowledge proof (section)

{{Short description|Proving validity without revealing other data}}

In [[cryptography]], a '''zero-knowledge proof''' (also known as a '''ZK proof''' or '''ZKP''') is a protocol in which one party (the prover) can convince another party (the verifier) that some given statement is true, without conveying to the verifier any information ''beyond'' the mere fact of that statement's truth.<ref>{{Citation |last=Aad |first=Imad |title=Zero-Knowledge Proof |date=2023 |work=Trends in Data Protection and Encryption Technologies |pages=25–30 |editor-last=Mulder |editor-first=Valentin |place=Cham |publisher=Springer Nature Switzerland |language=en |doi=10.1007/978-3-031-33386-6_6 |isbn=978-3-031-33386-6 |editor2-last=Mermoud |editor2-first=Alain |editor3-last=Lenders |editor3-first=Vincent |editor4-last=Tellenbach |editor4-first=Bernhard|doi-access=free }}</ref> The intuition underlying zero-knowledge proofs is that it is trivial to prove possession of the relevant information simply by revealing it; the hard part is to prove this possession without revealing this information (or any aspect of it whatsoever).<ref>{{cite book |last=Goldreich |first=Oded |author-link= |title=Foundations of Cryptography Volume I |year=2001 |url=https://www.cambridge.org/core/books/foundations-of-cryptography/B61B6AD235D2034D511A5FF740415166 |location= |publisher=Cambridge University Press |page=184 |doi=10.1017/CBO9780511546891 |isbn= 9780511546891}}</ref>

In light of the fact that one should be able to generate a proof of some statement ''only'' when in possession of certain secret information connected to the statement, the verifier, even after having become convinced of the statement's truth, should nonetheless remain unable to prove the statement to further third parties.

Zero-knowledge proofs can be interactive, meaning that the prover and verifier exchange messages according to some protocol, or noninteractive, meaning that the verifier is convinced by a single prover message and no other communication is needed. In the [[Standard model (cryptography)|standard model]], interaction is required, except for trivial proofs of [[BPP (complexity)|BPP]] problems.<ref>{{cite book |last=Goldreich |first=Oded |author-link= |title=Foundations of Cryptography Volume I |year=2001 |url=https://www.cambridge.org/core/books/foundations-of-cryptography/B61B6AD235D2034D511A5FF740415166 |location= |publisher=Cambridge University Press |page=247 |doi=10.1017/CBO9780511546891 |isbn= 9780511546891}}</ref> In the [[Common random string model|common random string]] and [[random oracle]] models, [[non-interactive zero-knowledge proof]]s exist. The [[Fiat–Shamir heuristic]] can be used to transform certain interactive zero-knowledge proofs into noninteractive ones.<ref>{{cite book |last=Goldreich |first=Oded |author-link= |title=Foundations of Cryptography Volume I |year=2001 |url=https://www.cambridge.org/core/books/foundations-of-cryptography/B61B6AD235D2034D511A5FF740415166 |location= |publisher=Cambridge University Press |page=299 |doi=10.1017/CBO9780511546891 |isbn= 9780511546891}}</ref><ref name="noninteractive">{{cite book |first1=Manuel |last1=Blum |first2=Paul |last2=Feldman |first3=Silvio |last3=Micali |title=Proceedings of the twentieth annual ACM symposium on Theory of computing - STOC '88 |chapter=Non-interactive zero-knowledge and its applications |date=1988 |pages=103–112 |doi=10.1145/62212.62222 |url=https://apps.dtic.mil/sti/pdfs/ADA222698.pdf |archive-url=https://wayback.archive-it.org/all/20181214020301/https://apps.dtic.mil/dtic/tr/fulltext/u2/a222698.pdf |url-status=live |archive-date=December 14, 2018 |isbn=978-0897912648 |s2cid=7282320 |access-date=June 2, 2022 }}</ref><ref name=noninteractive2>{{cite journal|last1=Wu|first1=Huixin|last2=Wang|first2=Feng|title=A Survey of Noninteractive Zero Knowledge Proof System and Its Applications|journal=The Scientific World Journal|date=2014|volume=2014|pages=560484|doi=10.1155/2014/560484|pmid=24883407|pmc=4032740|doi-access=free }}</ref>