Zero-Knowledge Proofs (ZKPs)

Zero-knowledge proof systems that have received a lot of attention since their introduction are those that use a single message, such as proof of the existence of zero-knowledge or proof against a certain type of proof.

Ensar Seker
Apr 10 · 5 min read

What is it?

A zero-knowledge proof protocol is a way for a prover to convince a verifier that a statement containing classified information is true without revealing even a single bit of information (or a fraction thereof) about that knowledge. This is because the prover can prove the accuracy of the claim to the verifier without providing them with additional information. As a consequence, the verifier nor any passive eavesdropper gains any information from taking part in any number of executions of the protocol. To this end, a non-interactive zero-knowledge proof system contains only one message sent by the prover to the verifier.

What are the must-have properties?

The zero-knowledge protocol must have three properties.

· Completeness: if the statement is true, the honest verifier (that is, one following the protocol properly) will be convinced of this fact by an honest prover.

· Soundness: if the statement is false, no cheating prover can convince the honest verifier that it is true, except with some small probability.

· Zero-knowledge: if the statement is true, no verifier learns anything other than the fact that the statement is true. In other words, just knowing the statement (not the secret) is sufficient to imagine a scenario showing that the prover knows the secret. This is formalized by showing that every verifier has some simulator that, given only the statement to be proved (and no access to the prover), can produce a transcript that “looks like” an interaction between the honest prover and the verifier in question.

In other words, the zero-knowledge proof is probabilistic rather than deterministic. However, there are techniques that reduce the defect resistance to negligible values.

How does it work?

Peggy proves to know the value of x (for example her password).

  1. Peggy and Victor agree on a prime p and a generator g of the multiplicative group of the field Zp
  2. Peggy calculates the value y=g^x mod p and transfer the value to Victor.
  3. The following two steps are repeated a (large) number of times;

I. Peggy repeatedly picks a random value r € U(0,p-1] and calculates C = g^r mod p. She transfers the value C to Victor.

II. Victor asks Peggy to calculate and transfer either the value (x+r) mod (p-1) or the value r. In the first case Victor verifies (C . y) mod p g^(x+r)mod(p-1) mod p. In the second case he verifies C g^r mod p.

The value (x+r) mod (p-1) can be seen as the encrypted value of x mod (p-1). If r is truly random, equally distributed between zero and (p-1), this does not leak any information about x.

What are the zero-knowledge types?

· Proof of knowledge: the knowledge is hidden in the exponent like in the example shown above.

· Pairing-based cryptography: given f(x) and f(y), without knowing x and y, it is possible to compute f(x.y).

· Witness indistinguishable proof: verifiers cannot know which witness is used for producing the proof.

· Multi-party computation: while each party can keep their respective secret, they together produce a result.

· Ring signature: outsiders have no idea which key is used for signing.

What are the real-life implementations?

Blockchain: Zcash is the first widespread application of zk-SNARKs, a novel form of zero-knowledge cryptography. The fact that the information is disclosed arose from a private conversation between two people, not from a public one. Zcash’s strong privacy guarantees are due to the fact that all of the shielded transactions contained in it can be fully encrypted on the blockchain and verified as valid with zk-SNARK proofs.

A zero-knowledge protocol is one where the applicant’s verifier typically depends on random events. The interactive evidence must be complete for the protocol to succeed, regardless of the number of claimants or the amount of information available. If M is a polynomial in time and there is an algorithm with the following properties for it, then the interactive proof is valid.

Authentication Systems: Research on zero-proof knowledge was motivated by an authentication system in which one party wants to prove its identity to a second party with secret information (such as a password) but does not want the second party to know about the secret. The second part is called Verification and you give away zero information about your secrets. There is a need to enforce honest behavior while respecting privacy so that zero-knowledge password proof is able to address the limited size of passwords.

The zero-knowledge protocol is used to enable a party to know something such as a certificate of authentication without having to provide the certificate. In the ZKP no passwords or access data are transmitted or stored on the authentication server. This is because authentication is done by exchanging passwords, which means that they cannot be stolen.

Nuclear Disarmament: It was demonstrated experimentally at the U.S. Department of Energy’s (DOE) Princeton Plasma Physics Laboratory (PPPL) in 2016. It was the first experimental demonstration of physical zero-knowledge proof. The experiment allows inspectors to confirm whether or not an object is indeed a nuclear weapon without recording, sharing, or revealing the internal workings which might be secret.

Cited Sources

· https://www.cse.scu.edu/~tschwarz/coen350/zkp.html

· https://z.cash/technology/zksnarks/

· https://hackernoon.com/eli5-zero-knowledge-proof-78a276db9eff

· https://academy.bit2me.com/en/zkp-zero-knowledge-protocol/

· https://www.hindawi.com/journals/tswj/2014/560484/

· https://sedicii.com/news/Zero-Knowledge-Authentication/index.html

· https://doubleoctopus.com/security-wiki/protocol/zero-knowledge-proof/

· https://en.wikipedia.org/wiki/Zero-knowledge_proof

· https://www.altoros.com/blog/zero-knowledge-proof-improving-privacy-for-a-blockchain/

· http://www.tml.hut.fi/Opinnot/Tik-110.501/1995/zeroknowledge.html

· https://en.wikipedia.org/wiki/Zero-knowledge_proof

· https://www.pppl.gov/news/2016/09/pppl-and-princeton-demonstrate-novel-technique-may-have-applicability-future-nuclear

· https://en.wikipedia.org/wiki/Non-interactive_zero-knowledge_proof

· https://z.cash/technology/zksnarks/

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store