Zero knowledge proofs
The zero knowledge proofs, ZKPs, becomes a buzz-word recently due to its magic application: to prove a secret to someone without leaking out the secret?! It sounds a bit abstract, powerful , even contrary. Let’s come up with the following scenarios for better understanding.
In the upper case, Alice can convince others that she has the knowledge of her password (secret) for the bank account by withdrawing money from the ATM. In the second case, Bob makes retailers convinced he’s older than 20 by showing his driving license while keeping his age secret. Although theoretically these two cases do not satisfy the definition of cryptographic zero-knowledge proof, they are still referable for easily realizing.
Definition.
Informally, zero knowledge proof is a two-men game that a prover tries to convince a verifier that the prover knows a secret, without leaking any clue of the secret.
Commit phase
The syntax of zero-knowledge proofs is shown in above picture. Similar to the commit-open-verify process in the commitment, the zero-knowledge process is commit-(request-challenge-response-verify) * n. It firstly generates a cryptographic commitment in the commit phase. The hiding property of commitments ensure the verifier acquires no information from the commitment; the binding property of commitments guarantees that the prover will not change his / her mind after the commit phase. Then, the open operation is obviously not the next step since the secret should been kept private in the zero-knowledge proofs.
Challenge phase
Rather than opening the commit, the challenge phase works as follows: the prover sends a request to the verifier on demand and the verifier can challenge depending on the commitment and the request. On receiving a challenge chg, the prover replies a corresponding response res and the verifier can verify the validity through verify(com, req, chg, res). After many times of the challenge series request-challenge-response-verify, the verifier believes the fact that the prover owns the secret if the prover always passes the verifications.
Properties
In principle, a proof process is called zero-knowledge proof if all these three properties hold.
Completeness
The honest prover always convinces the verifier.
Soundness
The dishonest prover fails in overwhelming probability.
Zero-knowledge
The verifier acquires nothing but the fact the prover knows the secret.
The correctness is usually intuitive; while the zero-knowledge property is a bit too sophisticated to be described. Hence, let’s dive a bit deeper to the soundness of those ZKP protocols.
Proofs or arguments
- Zero-knowledge proof:if the soundness hold and the prover has unbounded computational ability.
- Zero-knowledge argument: if the soundness hold and the prover has only bounded computational power.The false-positive probabilities
In some special cases, a dishonest prover who does not own the secret may probabilistically pass the verification. To discuss about this, some knowledge of the challenge phase has to be clarified.
The challenge
The challenge is issued by the verifier to ensure the prover knows the secret, such as a random examination. However, if the challenge is predictable for the prover, it is not hard for the prover to fake a valid pair of (request, response) that pass the verification without knowing the secret.
For a commitment com = Commit(secret) where the secret is unknown to the prover, if the prover can predict the challenge chg of the verifier, it is easy to find a pair (req, res) = fake(com, chg) that verify(com, req, chg, res} = True.
The dishonest prover may guess the challenge
This condition happens probabilistically depends on the domain size of chg. In short, the prover may guess the challenge. Take the Fiat-Shamir ZKP for example, which is designed to proof the knowledge of a square root of a commitment com, the dishonest who doesn’t knows the secret x can still pass the verification if he / she successfully guesses the challenge chg. Here n is a public parameter, and the square root of values in the mod n environment is difficult due to some mathematic issues.
Why should the challenge be executed many times?
It is trivially observed that the domain size of challenges is too small to guarantee the fact that the prover is honest. In above Fiat-Shamir case, each time the prover pass the the verification, there is only half probability that he / she really knows the secret x. Thus, many interactions are executed to avoid the probabilistically guessing. For instance, if the prover successfully passes the verification for 128 times and none of them fails; then, the verifier may be convinced because 2^(-128) is negligible.
The order of request, challenge and response
Definitely, aforementioned Fiat-Shamir square root ZKP is a special case whose challenge space is quite small so that malicious prover might success. Assume the challenge space is big, there is another factor that matters: the order. We could easily observe that
The honest prover generates a request, receives a challenge and returns a response (req - chg - res).
The dishonest prover predicts a challenge, generates the response and finally computes the request (chg - res - req).An intuitive solution is to import some one-way functions to guarantee the orders. For example, the Fiat-Shamir transfer adopted the hash functions as the one-way functions which makes order as wish. The detail description will be discuss in the next phase.
Interactions
It is obvious that the proof needs many times of interactions between the prover and the verifier; however, the interaction on one hand costs much computational and communicational resources; and on the other hand may not be applicable if the prover and the verifier are not online at the same time. So, users may think about one problem that may we deal with the challenges and those interactions in a non-interactive manner? The answer is YES.
ZKP vs NIZK
We already know the zero-knowledge proofs (ZKP). The non-interactive zero-knowledge proofs (NIZK) is also a ZKP which adopts cryptographic transfers that makes challenges non-interactive. As aforementioned, the challenges should be unpredictable and the order (req - chg - res) does matter. For those ZKP algorithms whose challenge space are big, a famous Fiat-Shamir transfer that adopts hash functions as the challenge generator makes NIZK possible.
ZKP: (1) the prover generates a request req, (2) the verifier chooses a challenge chg, (3) the prover replies a response res = response(secret, req, chg).
NIZK: (1) the prover generates a request req, computes the challenge chg = hash(com, req) and the response res = response(secret, req, chg)The first difference is the challenge is computed by the hash function rather than randomly chosen by the verifier; and the second difference is it is only executed once. Then, how does the properties satisfied in this transfer?
Unpredictable
In the random oracle model, the hash value acts like a random number since it is uniformly-distributed.
Correct order
The one-wayness of hash function ensures that the challenge is generated after both the commitment and the request are chosen and inputted. The (chg - res - req) cheating will definitely not work.
The verification of NIZK is simply modified as follow:
verify_NIZK(com, req, chg, res):
return (chg == hash(com, req) && verify_ZKP(com, req, chg, res))Due to the non-interactive requirement and the cryptographic properties of hash functions, the challenge phase is executed only once in NIZK protocols, which the strength equals to the ZKP protocols based on the assumption of the common reference string (CRS) model and the random oracle (RO) model. At the end of this story, we ignore these theoretical models for better concentrating on the zero-knowledge proofs.
