21-08-2012, 03:53 PM
Zero-Knowledge Proofs
Zero-KnowledgeProofsII.ppt (Size: 363.5 KB / Downloads: 94)
What is a Zero- Knowledge Proof?
A zero-knowledge proof is a way that a “prover” can prove possession of a certain piece of information to a “verifier” without revealing it.
This is done by manipulating data provided by the verifier in a way that would be impossible without the secret information in question.
A third party, reviewing the transcript created, cannot be convinced that either prover or verifier knows the secret.
Properties of Zero-Knowledge Proofs
Completeness – A prover who knows the secret information can prove it with probability 1.
Soundness – The probability that a prover who does not know the secret information can get away with it can be made arbitrarily small.
Complexity Theory
The last proof works because the problem of solving discrete logarithms is NP-complete (or is believed to be, at any rate).
It has been shown that all problems in NP have a zero-knowledge proof associated with them.
Bit Commitments
“Flipping a coin down a well”
“Flipping a coin by telephone”
A value of 0 or 1 is committed to by the prover by encrypting it with a one-way function, creating a “blob”. The verifier can then “unwrap” this blob when it becomes necessary by revealing the key.
Bit Commitments: An Example
Let n = pq, where p and q are prime. Let m be a quadratic nonresidue modulo n. The values m and n are public, and the values p and q are known only to Peggy.
Peggy commits to the bit b by choosing a random x and sending Vic the blob mbx2.
When the time comes for Vic to check the value of the bit, Peggy simply reveals the values b and x.
Since no known polynomial-time algorithm exists for solving the quadratic residues problem modulo a composite n whose factors are unknown, hence this scheme is computationally concealing.
On the other hand, it is perfectly binding, since if it wasn’t, m would have to be a quadratic residue, a contradiction.
Computational Assumptions
A zero-knowledge proof assumes the prover possesses unlimited computational power.
It is more practical in some cases to assume that the prover’s computational abilities are bounded. In this case, we have a zero-knowledge argument.
Zero-KnowledgeProofsII.ppt (Size: 363.5 KB / Downloads: 94)
What is a Zero- Knowledge Proof?
A zero-knowledge proof is a way that a “prover” can prove possession of a certain piece of information to a “verifier” without revealing it.
This is done by manipulating data provided by the verifier in a way that would be impossible without the secret information in question.
A third party, reviewing the transcript created, cannot be convinced that either prover or verifier knows the secret.
Properties of Zero-Knowledge Proofs
Completeness – A prover who knows the secret information can prove it with probability 1.
Soundness – The probability that a prover who does not know the secret information can get away with it can be made arbitrarily small.
Complexity Theory
The last proof works because the problem of solving discrete logarithms is NP-complete (or is believed to be, at any rate).
It has been shown that all problems in NP have a zero-knowledge proof associated with them.
Bit Commitments
“Flipping a coin down a well”
“Flipping a coin by telephone”
A value of 0 or 1 is committed to by the prover by encrypting it with a one-way function, creating a “blob”. The verifier can then “unwrap” this blob when it becomes necessary by revealing the key.
Bit Commitments: An Example
Let n = pq, where p and q are prime. Let m be a quadratic nonresidue modulo n. The values m and n are public, and the values p and q are known only to Peggy.
Peggy commits to the bit b by choosing a random x and sending Vic the blob mbx2.
When the time comes for Vic to check the value of the bit, Peggy simply reveals the values b and x.
Since no known polynomial-time algorithm exists for solving the quadratic residues problem modulo a composite n whose factors are unknown, hence this scheme is computationally concealing.
On the other hand, it is perfectly binding, since if it wasn’t, m would have to be a quadratic residue, a contradiction.
Computational Assumptions
A zero-knowledge proof assumes the prover possesses unlimited computational power.
It is more practical in some cases to assume that the prover’s computational abilities are bounded. In this case, we have a zero-knowledge argument.