Imagine if you had a secret recipe or key to a cipher. Is it possible to prove to a friend that you know that? A zero-knowledge proof was used to prove that you could.
For a simple way to understand this idea, suppose you want to show your friend how to get through a maze, without divulging any information about the path. While your friend was not allowed to watch, you could simply go through the maze. Given enough time, anyone can eventually find their way out. They wouldn't know how to do it, but you could.
Cryptographers, who work with secret information, and researchers of computational complexity, who deal with classifying the difficulty of different problems, use zero-knowledge proof. There have always been some connections between the two worlds due to the fact that a lot of modern cryptography relies on complex assumptions. These proof have created a world of connection.
Zero-knowledge proofs are part of a category known as interactive proof. The interactive proof works like an interrogation, with one party trying to convince the other that a given statement is true. The proof needs to satisfy two things. True statements will eventually convince an honest verifier. No prover can convince the verifier if the statement is false.
There are interactive proof. It takes a lot of challenges for the verifier to be confident that the prover knows the statement is true.
Micali and Goldwasser were graduate students at the University of California, Berkeley, and were playing poker over a network. When a player gets a card from the virtual deck, how can they make sure it's random? The way could be led by interactive proof. How can players verify that the entire protocol was followed correctly without revealing any of their teammates?
The third property added to the two needed for an interactive proof is that the proof should only reveal the truth of the statement. The poker players don't know anything more than what they're supposed to know according to Goldwasser.
The classic example is worth considering. Alice wants to show Bob that a particular graph G has a Hamiltonian cycle. The graph has a path that goes from one dot to the next and back again. It is possible for Alice to show Bob the path that leads to this, but he would know the path as well.
It is possible for Alice to convince Bob that there is a path that exists. A new graph, H, that doesn't look like G but is similar in some ways, is drawn by her. If G has a Hamiltonian cycle, H will as well. After covering every edge in H with masking tape, she locked it up and gave it to Bob. She can't change it, but he can't see it directly. Bob can either ask Alice to show him that H is similar to G or he can ask her to show him the Hamiltonian cycle in H.
Alice can try to fool Bob by drawing graphs that aren't similar to G or by submitting graphs she doesn't know the path for. They have played many rounds and the chance of Alice deceiving Bob is diminishing. Bob will be convinced that Alice knows a Hamiltonian cycle if she gets everything right.
A consequence with far-reaching effects was discovered after the initial paper that described such proof. It has to do with a category of problems called NP. The solutions are easy to verify. A zero-knowledge proof can be used to prove the solution to every problem in NP if truly secure encryption is possible. Multi-prover interactive proof is a type of zero-knowledge proof that doesn't require a password.
If a prover and verifier share a small amount of random bits, no interaction is necessary. Constant communication between two parties isn't necessary because zero-knowledgeproofs don't have to be interactive. It wasn't until after the 21st century that such proof took off.
The evolution of efficient techniques for building zero-knowledge proof began in the late 2000s. There might be a way to use this in practice.
A prover can send a single message to a verifier without both of them having to be online, and researchers can create a very short proof that can be verified quickly. This has led to a number of practical uses, such as the ability to quickly verify the block after a transaction. A group of physicists showed in 2016 how zero-knowledge proof can be used to show if a warhead is active or not.
Advances in quantum computing have made it necessary for Crépeau to stress-test past research to make sure zero-knowledge protocols are still viable. He helped demonstrate that multi-prover interactive proof retain their secrecy even when quantum computers are involved, but achieving the same level of security slows the protocol down. He said that the finding was good, but that there would be new concerns as technology advances.
The future of computation will involve quantum computers. Whenever we assess the security of a system, we want to make sure that it's safe.
This editorially independent publication is funded by the Simons Foundation. The funding decisions of the Simons Foundation don't affect our coverage.
All Rights Reserved © 2024
