Zero-knowledge proof

Zero-knowledge proof

Zero-knowledge proofs are a class of cryptographic protocol that confirms knowledge without revealing excess data, with applications in cybersecurity, financial transactions and blockchain technology.

Overview

Zero-knowledge proofs (or ZKP) are a class of cryptographic protocols for one party (the prover) to prove to another party (the verifier) that they know specific information, usually a value “x” or “secret”, without expressing any other information besides the fact they know the value. Zero-knowledge proofs are proofs that are both convincing, but do not yield anything beyond the validity of the assertion being proven.

Zero-knowledge proofs (or protocols) are important because they do not require the party to reveal extra key information or any other information in order to prove that they know a specific value. This security has made ZKPs important in cryptography, private information security, financial transactions and blockchain applications.

Zero-knowledge proof protocols originally required interactive input from the verifier and prover, whether that be a people or computers. These inputs are challenges to the verifier to prove they do in fact know the claimed knowledge, without actually revealing it.

Zero-knowledge protocols are probabilistic assessments, meaning they don’t prove with complete certainty. While zero-knowledge proofs can enable almost complete assuredness the prover knows the value, it is not a mathematical proof because of the small probability (the soundness error) that the cheating prover is able to convince the verifier of a false statement. An example of the soundness error would be if the prover was somehow able to guess the correct answer 1000 times in a row.

The generality of these methods are important, because almost all statements can in practice be encoded as claims concerning membership in languages in NP, the basis of cryptography.

Non-interactive zero-knowledge proofs were published in 2003 by Goldwasser and Yael Tauman Kalai. These non-interactive ZKPs do not require an interaction between the prover and verifier and are capable of impossibility results, but the validity relies on computational assumptions. Typical assumptions are reliant on assumptions of an ideal hash function or blockchain framework.

These proofs are used in many different industries, including but limited to cyber security, cryptography, commerce transactions and blockchain. Researchers have also looked to apply zero-knowledge proofs to digital identification mechanisms for e-voting.

General application uses for zero-knowledge proofs include but are not limited to minimum age verification in online transactions, anonymous credentials use, mortgage risk assessment, investment rating, e-voting and electronic auctions and procurement. All of these uses are also applicable in distributed ledger technology (DLT) and blockchain technology, with the rise of these technologies contributing to the increased research in zero-knowledge proofs.

History
1985-2010

Zero-knowledge proofs were first devised by MIT researchers Shafi Goldwasser, Silvio Mical and Charles Rackoff in a 1985 paper, “The Knowledge Complexity of Interactive Proof-Systems. The paper introduced key concepts including an interactive proof (IP) hierarchy and conceived the concept of knowledge complexity, a measure to see how much proof is transferred from the prover to the verifier. Perhaps most importantly, they gave the first zero-knowledge proof for a concrete problem when they demonstrated how to construct ZKPs for any NP-set, with any commitment scheme.

Two other researchers at the University of Chicago and Eötvös Loránd University in Budapest, László Babai and Shlomo Moran, also published a paper on the topic, “Arthur-Merlin Games: A Randomized Proof System and a Hierarchy of Complexity Classes,” in 1993. These two papers earned all five researchers the 1993 Gödel Prize, an annual award for outstanding papers in the area of theoretical computer science.

Feige, Lapidot and Shamir introduced the factor of witness indistinguishability in 1999, which added an important design technique for zero-knowledge proofs. Oded Goldreich has contributed knowledge and foundations to the study of sequention, parallel and concurrent composition of ZKPs at the Weizmann Institute of Science. Russell Impagliazzo and Moti Yung proved that assuming unbreakable encryption, that anything that can be proved by an interactive proof system can be proved with zero-knowledge.

2011-Present

zk-SNARK, a non-interactive zero-knowledge protocol was published in January 2012 by Nir Bitansky, Ran Canetti, Alessandro Chiesa and Erin Tromer. zk-SNARK provided the computational framework for the Zcash blockchain protocol, showing capabilities of combining ZKP protocols to cryptocurrency.

Bulletproofs were released in 2017 by Benedikt Bunz, Jonathan Bootle, Dan Boneh, Andrew Poesltra, Peter Wuille and Greg Maxwell. The research proved that a committed value is in a range using a logarithmic number of field and group, increasing the security and efficiency of non-interactive zero-knowledge proofs.

zk-STARK protocol was introduced in 2018, proving a non-interactive ZKP that requires no trusted setup. The lack of a trusted setup eliminates the chance sources can work together to undermine protocol and access hidden information in the protocol. The release of zk-STARK made the technology more secure, scalable and useful for larger institutions interested in utilizing blockchain.

As cybersecurity, cryptocurrency and blockchain technology has advanced and entered mainstream markets and perception, zero-knowledge proof technology has become heavily funded and researched by state entities and global corporations. QED-IT announced its participation in a US government-funded research project with DARPA (Defense Advanced Research Projects Agency), receiving $2 million USD of the $12.6 million allocated to the project. QED-IT joined R&D specialist firm Galois in the initiative, Project Fromager, on September 16, 2020. Project Fromager is one of 12 projects to be funded through DARPA's Securing Information for Encrypted Verification and Evaluation (SIEVE) program, which aims to enable verification of security and defense capabilities without revealing sensitive information involved.

Definition

In order for a proof, problem or protocol to be a zero-knowledge proof it must satisfy three properties.

Completeness

If the statement is true, the verifier must follow the protocol properly and accept the fact as true.

Soundness

If the statement is false, no cheating prover can convince the verifier that it is true, with the exception of a small probability outlined in the protocol.

Zero-knowledge

If the statement is true, the verifier does not learn anything other than the fact the statement is true. The prover knowing the value must be sufficient to show the prover knows the secret.

Example

A common way of explaining zero-knowledge proofs is The Ali Baba cave, first published by Jean-Jacques Quisquater in a paper, “How to Explain Zero-Knowledge Protocols to Your Children.” One child, usually called Peggy (for Prover), finds a cave with two tunnels (A and B) leading to a magic door which connects the two sides of the tunnels and is unlocked only by codeword. Peggy tells Victor (for Verifier) she knows the magic word, but won’t tell him what it is.

Peggy (or Prover) randomly takes path A or B, unseen.

Victor (or Verifier) chooses an exit path.

Peggy appears down the path Victor had named.

Victor wants to see if she really does know the word, so tells Peggy to go into the cave without him seeing. When she gets to the door, he yells inside which tunnel he wants her to return by. If she does in fact know the word, she could open the door and return by whichever tunnel he instructed. If Peggy does not know the word, she could only return by the tunnel she originally chose.

Although Victor does not know which tunnel Peggy originally chose, if she returns down the wrong tunnel he will know she does not know the value or “secret” to the door. If she does return down the right tunnel, either she knows the codeword if truthful, or a 50% chance it was by chance. It is up to him to either believe or not believe she is telling the truth, but the two could repeat this experiment until Victor believes her.

It is not possible for Peggy to 100% prove she knows the word without saying the magic codeword in front of Victor, but if she repeatedly comes back down the correct tunnel, the chances she does would become increasingly probable (and her chance of lying would get closer to zero).

Companies working on or with zero-knowledge proof systems

Zero-knowledge proofs are used in multiple industries and services, mostly alongside blockchain technology in cryptography, cryptocurrency, identity authorization and financial.

Companies using zero-knowledge proofs in cryptocurrency

The invention and adoption of cryptocurrency has revolutionized transactions in the modern age, enabling transparent, independent and decentralized financial movement. Although this transparency is optimal for auditing and tracking, it doesn't lend itself to sensitive transaction information like an employee's paycheck, the price a manufacturing company pays for its raw materials or the cost of a recent medical procedure. Cryptocurrency companies research and utilize zero-knowledge proof concepts to encrypt and limit certain information on the blockchain.

Companies using zero-knowledge proofs in cybersecurity

Cryptology and cybersecurity were the first to use zero-knowledge proof and protocols, conceiving ZKPs and utilizing them to secure privileged information. While original zero-knowledge proofs required interactive input and a trusted setup, new technology has reduced the chance for leaked data and excess information exchange.

Companies using zero-knowledge proofs in identity authentication and management

Identity authentication and management are a focus for zero-knowledge proof technology, due to their ability to limit private information between sources. Companies apply ZKPs to new and existing privacy frameworks to ensure authorization while still keeping anonymity for users and a safeguard for sensitive information.

Companies using zero-knowledge proofs in financial transactions and accounting

Companies using zero-knowledge proofs in financial transactions and accounting

Financial institutions, enterprises and investors struggle to adopt blockchain in its basic format, due to the public and transparent nature of the technology. As a result, research and integration of ZKP frameworks industry leaders focus is aimed at finding secure and scalable solutions for confidential transaction and accounting data.

Timeline

March 6, 2018
zk-STARK protocol is introduced, offering no trusted setup, quasi-linear proving time and poly-logarithmic verification time.
November 1, 2017
"Bulletproofs: Short Proofs for Confidential Transactions and More", is published, highlighting a more efficient ZKP construction for DLT and blockchain.
January 2012
zk-SNARK, a non-interactive zero-knowledge argument of knowledge is released, providing the computing framework for the Zcash blockchain protocol.
1985
Goldwasser, Micali and Rackoff publish the first conception of zero-knowledge proofs in, "The Knowledge Complexity of Interactive Proof-Systems."

People

Name
Role
LinkedIn

Avi Wigderson

Benedikt Bunz

Charles Rackoff

Cynthia Dwork

Dan Boneh

Jonathan Bootle

László Babai

Moni Naor

Oded Goldreich

Safi Goldwasser

Shlomo Moran

Silvio Micali

Further reading

Title
Author
Link
Type
Date

Arthur-Merlin Games: A Randomized Proof System and a Hierarchy of Complexity Classes

László Babai, Shlomo Moran

August 3, 1987

Bulletproofs: Short Proofs for Confidential Transactions and More

Benedikt Bünz, Jonathan Bootle, Dan Boneh, Andrew Poelstra, Pieter Wuille and Greg Maxwell

November 1, 2017

Homepage | ZKProof Standards

ZKProof

Web

How to Explain Zero-Knowledge Protocols to Your Children

Jean-Jacques Quisquater, Muriel Myziam, Louis Michael Guillou, Annick Marie, Anna Gaid, Soazig Gwenole, Tom Berson

1990

ING Bank Is Bringing Bitcoin 'Bulletproofs' to Private Blockchains - CoinDesk

Ian Allison

Web

April 15, 2019

Introduction to zk-SNARKS | ConsenSys

ConsenSys

Web

March 27, 2017

Multiple NonInteractive Zero Knowledge Proofs Under General Assumptions

Uriel Feige, Dror Lapidot, Adi Shamir

1999

QEDIT Joins Forces with Galois as Part of US Government-Funded Initiative to Advance Zero-Knowledge Proof Cryptography

QEDIT

Web

September 16, 2020

The Knowledge Complexity of Interactive Proof Systems

Shafi Goldwasser, Silvio Micali, Charles Rackoff

February 1989

Zero-Knowledge twenty years after its invention

Oded Goldreich

December 3, 2002

Documentaries, videos and podcasts

Title
Date
Link

Companies

Company
CEO
Location
Products/Services

QED-IT

References

Page 1 of 3
Golden logo
Text is available under the Creative Commons Attribution-ShareAlike 4.0; additional terms apply. By using this site, you agree to our Terms & Conditions.