Zero-knowledge proofs explained: Part 1

Zero-knowledge proofs explained Part 2: Non-interactive zero-knowledge proofs

Cryptography mostly concerns itself with secure communications and includes hiding information from adversaries and authentication of individuals.

Hashes, asymmetric encryption, and symmetric encryption are often used together to allow for secure communications. In popular cryptographic systems, like PGP, OTR, and VPNs, different algorithms are often used together, including:

• Hash functions that allow us to identify files, text, and keys conveniently
• Asymmetric encryption functions to securely exchange encryption keys over insecure channels
• Symmetric encryption functions to efficiently encrypt large amounts of data
• Key exchange functions to securely negotiate encryption keys over insecure channels

Zero-knowledge proofs are encryption schemes used to prove that you know something without revealing what it is. For example, you can show without a doubt that you know the answer to a puzzle without actually disclosing the solution.

Zero-knowledge proofs are still relatively new and have only found a common use-case recently in cryptocurrencies.

Interactive zero-knowledge proofs

Interactive zero-knowledge proofs require interaction between the individual (or computer system) proving their knowledge and the individual validating the proof.

The system creates one additional interesting characteristic for a zero-knowledge proof: Not only are you proving you know something without disclosing what you know, but you are also just revealing it to the individual with which you interact. Somebody who merely observes you will not be able to verify your claim.

Though this is good for additional privacy, it can also come with considerable extra effort and cost when trying to prove something to multiple individuals.

How zero-knowledge proofs work

The situation:

Imagine an odorless, tasteless, and colorless poisonous liquid that looks and feels exactly like water. What if someone places this glass next to an identical glass full of water? You have no way of distinguishing the two liquids from each other. Indeed, you may not even know they are different from each other.

The claim:

Somebody claims they have an extraordinary vision that allows them to tell the two glasses apart. They do not want to tell you which is which, though. How can you verify their claim without finding out which glass is poison, and which is water?

The proof:

You (the verifier) blindfold the person that claims to tell the two glasses apart (the prover) and randomly decide to switch the glasses or not. After the removing the blindfold, you ask the prover if the glasses have changed position.

If they really can easily tell the two liquids apart, they will be able to tell you if they have switched places. Otherwise, they will be wrong with a 50% chance.

If you then repeat the experiment, the prover(if they are only guessing) will be wrong with a cumulative 75% chance.

After repeating the test 10 times, if the prover is correct each time, there is already a 99.9% chance they did not guess, and it’s likely that they do indeed have a way to distinguish the two glasses. After repeating the test n times:

1 – 0.5^n *100%

Of course, our example here has a few practical weaknesses. They could be security cameras or motion sensors installed, but in the abstract world of mathematics, we can be sure.

Why zero-knowledge proofs work

You, the verifier, can now be convinced with 99.9% certainty that the other person really does have a way of identifying the glasses, though you still don’t know which glass is full of poison, and which one is full of water.

Somebody who observed you and the prover, however, is not convinced. In theory, the verifier and the prover could have colluded with each other and put on a show with predetermined moves.