zero knowledge proof - where do we use it?

Question

zero knowledge proof, Where do we use it online? I thought we mostly use the RSA algorithm.

Answer 1

Zero-knowledge proofs are components in some rather complex protocols, in particular electronic voting schemes, in which votes are encrypted, but the voter must be able to prove that the vote complies to a specific format (e.g. it is the encryption of "0" or of "1", but nothing else) without revealing it.

---

It is also possible to turn (generically) any zero-knowledge proof into a digital signature scheme. The idea is that in a ZK proof, the prover sends commitments, then the verifier sends a challenge to which the prover must respond; the involved mathematics ensure that a fake prover would not be able to respond correctly to all possible challenge values. What makes the proof "convincing" is that the verifier does not collude with the prover and really sends a random challenge, not just "easy challenge values". Thus, the ZK interactive proof is convincing only insofar as we trust the verifier for not colluding. The proof is turned non-interactive by computing the challenge with a hash function over the whole set of commitments from the prover (hash functions act "randomly" by construction). By including the message to sign in the hash function input, you get a digital signature scheme.

The Schnorr signature scheme is an application of this construction principle. It works in a group where discrete logarithm is hard; for instance, there are publicly known parameters p, q and g (p is a big prime, q is a smaller but still big prime which divides p-1, g is an integer modulo p such that g^q = 1 mod p). The signer knows a private value x, and the corresponding public key is y = g^x mod p. To sign message m, the signer does this:

• The signer generates a random value k in the 1..q-1 range, and computes r = g^k mod p.
• The signer computes e = H(m||r) where H is a hash function (e.g. SHA-256) and "||" denotes concatenation.
• The signer computes s = k - xe mod q

The signature is then the pair (r,s). Verification is done that way:

• The verifier recomputes e = H(m||r).
• The verifier computes r' = g^sy^e mod p.
• The verifier verifies that r' = r.

If we want to see it as an adapted ZK proof, then r is the commitment from the prover (the signer, who want to prove his knowledge of x); e is the challenge, and s is the response to the challenge. The response does not reveal anything on x as long as the prover responds to a single challenge value, for a given commitment (i.e. for each signature, the signer will generate a new k which must be random and uniform, and never revealed to anybody).

However, for a fake prover who does not know x, responding to the challenge with a value s which fits in the verifying equation is not feasible unless he can predict the challenge e and craft his fake commitment in accordance. For instance, if the challenge e is known in advance, then the fake prover can simply choose a random s and compute his fake commitment r = g^sy^e mod p. That's where the hash function H enters the scene: you cannot cheat with a hash function. If the hash function is a random oracle, then its output cannot be predicted in advance, and since the commitment r is used as input to the hash function, the prover is necessarily "committed" to his commitment.

In practice, the Schnorr signature scheme is very rarely used, but a variant known as DSA is rather widespread (along with its elliptic curve version ECDSA). DSA includes a few twists which make the signature shorter and make it sufficiently different from the Schnorr signature scheme to be out of the scope of Schnorr's patent (that patent is now expired anyway).

---

Most X.509 certificates in the wild, and thus SSL-enabled Web sites, use RSA, which is not built around a ZK proof. But ECDSA gains popularity because elliptic curves are highly fashionable.