Zero Disclosure Proof
Evidence with zero disclosure (knowledge) ( Zero-knowledge proof ) is a cryptographic protocol that allows one of the parties (the verifier, party B) to verify that the second party (the proving party, A) knows any statement, while verifying get no other information about the statement itself. In other words, A proves the knowledge of a secret, without disclosing the secret itself.
The use of zero knowledge evidence to prove identity was first proposed by Uriel Feig, Amos Fiat and Adi Shamir. In this case, the user proves knowledge of his private key, which in this case acts as a secret, without revealing it. Thus, he proves his identity.
The zero disclosure proof has three main properties:
1. Completeness. If the prover knows the statement, he can convince the verifier of this.
2. Correctness. If the prover does not know the statement, then he can deceive the verifier only with negligible probability.
3. Zero disclosure. The verifier, even if he behaves dishonestly, does not know anything except the fact that the statement is known to the prover.
')
The proof is in the form of an interactive protocol. This means that side B asks a series of questions proving that if he knows the secret, he will answer all the questions correctly. If the secret to side A is unknown, but she wants to convince the opposite verifier, she has some probability (maybe 50%, as in the examples in this topic) to answer the question correctly. However, after a certain number of questions (10–20), the verifier is quite likely to ascertain that the prover does not know the secret. At the same time, none of the answers provide any information about the secret itself.
Jean-Jacques Quisquere and Louis Gillu's zero-knowledge proof is well explained by the story of Ali Baba’s cave (see figure). To pass through the cave, you need to open the door between C and D. The door opens only when someone utters magic words. Let Peggy know the magic words and want to prove it to Victor without revealing the words themselves.
Here is how the proof with zero knowledge occurs in this case:
1. Victor is at point A.
2. Peggy goes all the way through the cave to the door, either on passage C or on passage D. Victor does not see which way Peggy has gone. After Peggy disappears into the cave, Victor moves to point B.
3. Victor shouts to Peggy to leave the cave from either the left aisle or the right aisle.
4. Peggy, if necessary, using magic words to unlock the door, leaves the cave from the passage from which Victor asked her to leave.
5. Peggy and Victor repeat steps 1-4 a number of times.
In the case when Peggy does not know the secret, she will not be able to deceive Victor if the stages of the proof (accreditation) are repeated several times in a row. Since she can only get out of the passage into which she entered, in each round of the protocol the probability to guess which side Victor will ask her to leave is 50%. Accordingly, its probability to deceive Victor is also equal to 50%. However, the probability of deceiving him in two rounds will be 25% already, and in n rounds she has only one chance out of 2 ^ n. Victor can confidently assume that if Peggy’s all n (n = 10–20) proof rounds are correct, then she really knows the secret words that open the door between points C and D.
If Victor records everything that happens on a video camera, then this video is not proof for a third party. Peggy and Victor could agree in advance on where Victor would ask her to leave. Then she will each time leave the place indicated by Victor, without knowing the magic words. On the other hand, Victor can fake a video recording, leaving only Peggy's successful attempts in it, cutting out everything else.
It should be noted that the analogy with the cave is not entirely true. Since, to prove her knowledge of words, Peggy can simply enter on one side, while Victor sees which way she went and exit on the other. However, this protocol perfectly describes a zero-knowledge proof from a mathematical point of view.
One of the most well-known identity identification protocols using zero-knowledge proof is the protocol proposed by Amos Fiat and Adi Shamir, whose stability is based on the difficulty of extracting the square root modulo a sufficiently large composite number n, the factorization of which is unknown.
Previously, before the proof itself, the trusted center T selects and publishes a module of a sufficiently large number n = p * q, which is difficult to factor into. Moreover, p, q are prime numbers and are kept secret. Each user A chooses a secret s from the interval (1, n − 1) mutually simple with n. Then the public key v = s ^ 2 (mod n) is calculated.
The obtained v is registered by the trust center as the public key of user A, and the value of s is secret A. It is the knowledge of this secret s that is necessary to prove A to party B without disclosing it for t rounds. Each accreditation consists of the following stages:
1. A selects a random r from the interval (1, n − 1) and sends x = r ^ 2 (mod n) to side B.
2. B randomly selects the e bit (0 or 1) and sends it to A.
3. A computes y = r * s ^ e (mod n) and sends it back to B.
4. Party B checks the equality y ^ 2 ≡ x * v ^ e (mod n). If it is true, then the transition to the next round of the protocol takes place, otherwise the evidence is not accepted.
The choice of e from the set implies that if side A really knows the secret, then she will always be able to answer correctly, regardless of the e selected. Suppose that A wants to deceive B, chooses a random r and sends x = r ^ 2 / v, then if = 0, then A successfully returns B y = r, in the case e = 1, A cannot answer correctly, t .to. does not know s, and it is rather difficult to extract the square root of v modulo n.
The probability that user A does not know the secret s, but convinces the opposite of verifying B will be estimated by probability equal to p = = 2 ^ (- t), where t is the number of accreditations. To achieve high reliability, it is chosen sufficiently large (t = 20-40). Thus, B is certified in knowledge of A if and only if all t rounds were successful.
In order for this protocol to run correctly, Side A must never reuse the value of x. If A had acted in this way, and B had sent another random bit r to A in another cycle, then B would have both answers A. Then B can calculate the value of s, and Alice’s secret key will be known to him.
For implementations such as smart cards, the Fiat-Shamir protocol described is not very suitable, as exchanges with the outside world take time, and storing data for each accreditation can quickly exhaust the card’s limited capabilities. Therefore, Gillu and Kiskatr developed an identification algorithm with zero knowledge, more suitable for such applications. The exchanges between Peggy and Victor, as well as parallel accreditations in each exchange are reduced to the absolute minimum: for each proof there is only one exchange, in which there is only one accreditation. There is also the Schnorr scheme, which is an alternative to the Gill-Kiscatra and Fiat-Shamir schemes. If you like the topic, I will write about them in my next topic.
The use of zero knowledge evidence to prove identity was first proposed by Uriel Feig, Amos Fiat and Adi Shamir. In this case, the user proves knowledge of his private key, which in this case acts as a secret, without revealing it. Thus, he proves his identity.
The zero disclosure proof has three main properties:
1. Completeness. If the prover knows the statement, he can convince the verifier of this.
2. Correctness. If the prover does not know the statement, then he can deceive the verifier only with negligible probability.
3. Zero disclosure. The verifier, even if he behaves dishonestly, does not know anything except the fact that the statement is known to the prover.
')
The proof is in the form of an interactive protocol. This means that side B asks a series of questions proving that if he knows the secret, he will answer all the questions correctly. If the secret to side A is unknown, but she wants to convince the opposite verifier, she has some probability (maybe 50%, as in the examples in this topic) to answer the question correctly. However, after a certain number of questions (10–20), the verifier is quite likely to ascertain that the prover does not know the secret. At the same time, none of the answers provide any information about the secret itself.
Cave zero knowledge
Jean-Jacques Quisquere and Louis Gillu's zero-knowledge proof is well explained by the story of Ali Baba’s cave (see figure). To pass through the cave, you need to open the door between C and D. The door opens only when someone utters magic words. Let Peggy know the magic words and want to prove it to Victor without revealing the words themselves.
Here is how the proof with zero knowledge occurs in this case:
1. Victor is at point A.
2. Peggy goes all the way through the cave to the door, either on passage C or on passage D. Victor does not see which way Peggy has gone. After Peggy disappears into the cave, Victor moves to point B.
3. Victor shouts to Peggy to leave the cave from either the left aisle or the right aisle.
4. Peggy, if necessary, using magic words to unlock the door, leaves the cave from the passage from which Victor asked her to leave.
5. Peggy and Victor repeat steps 1-4 a number of times.
In the case when Peggy does not know the secret, she will not be able to deceive Victor if the stages of the proof (accreditation) are repeated several times in a row. Since she can only get out of the passage into which she entered, in each round of the protocol the probability to guess which side Victor will ask her to leave is 50%. Accordingly, its probability to deceive Victor is also equal to 50%. However, the probability of deceiving him in two rounds will be 25% already, and in n rounds she has only one chance out of 2 ^ n. Victor can confidently assume that if Peggy’s all n (n = 10–20) proof rounds are correct, then she really knows the secret words that open the door between points C and D.
If Victor records everything that happens on a video camera, then this video is not proof for a third party. Peggy and Victor could agree in advance on where Victor would ask her to leave. Then she will each time leave the place indicated by Victor, without knowing the magic words. On the other hand, Victor can fake a video recording, leaving only Peggy's successful attempts in it, cutting out everything else.
It should be noted that the analogy with the cave is not entirely true. Since, to prove her knowledge of words, Peggy can simply enter on one side, while Victor sees which way she went and exit on the other. However, this protocol perfectly describes a zero-knowledge proof from a mathematical point of view.
Protocol Fiat-Shamir
One of the most well-known identity identification protocols using zero-knowledge proof is the protocol proposed by Amos Fiat and Adi Shamir, whose stability is based on the difficulty of extracting the square root modulo a sufficiently large composite number n, the factorization of which is unknown.
Previously, before the proof itself, the trusted center T selects and publishes a module of a sufficiently large number n = p * q, which is difficult to factor into. Moreover, p, q are prime numbers and are kept secret. Each user A chooses a secret s from the interval (1, n − 1) mutually simple with n. Then the public key v = s ^ 2 (mod n) is calculated.
The obtained v is registered by the trust center as the public key of user A, and the value of s is secret A. It is the knowledge of this secret s that is necessary to prove A to party B without disclosing it for t rounds. Each accreditation consists of the following stages:
1. A selects a random r from the interval (1, n − 1) and sends x = r ^ 2 (mod n) to side B.
2. B randomly selects the e bit (0 or 1) and sends it to A.
3. A computes y = r * s ^ e (mod n) and sends it back to B.
4. Party B checks the equality y ^ 2 ≡ x * v ^ e (mod n). If it is true, then the transition to the next round of the protocol takes place, otherwise the evidence is not accepted.
The choice of e from the set implies that if side A really knows the secret, then she will always be able to answer correctly, regardless of the e selected. Suppose that A wants to deceive B, chooses a random r and sends x = r ^ 2 / v, then if = 0, then A successfully returns B y = r, in the case e = 1, A cannot answer correctly, t .to. does not know s, and it is rather difficult to extract the square root of v modulo n.
The probability that user A does not know the secret s, but convinces the opposite of verifying B will be estimated by probability equal to p = = 2 ^ (- t), where t is the number of accreditations. To achieve high reliability, it is chosen sufficiently large (t = 20-40). Thus, B is certified in knowledge of A if and only if all t rounds were successful.
In order for this protocol to run correctly, Side A must never reuse the value of x. If A had acted in this way, and B had sent another random bit r to A in another cycle, then B would have both answers A. Then B can calculate the value of s, and Alice’s secret key will be known to him.
Conclusion
For implementations such as smart cards, the Fiat-Shamir protocol described is not very suitable, as exchanges with the outside world take time, and storing data for each accreditation can quickly exhaust the card’s limited capabilities. Therefore, Gillu and Kiskatr developed an identification algorithm with zero knowledge, more suitable for such applications. The exchanges between Peggy and Victor, as well as parallel accreditations in each exchange are reduced to the absolute minimum: for each proof there is only one exchange, in which there is only one accreditation. There is also the Schnorr scheme, which is an alternative to the Gill-Kiscatra and Fiat-Shamir schemes. If you like the topic, I will write about them in my next topic.
Source: https://habr.com/ru/post/94901/
All Articles