how do i implement zero knowledge proof?

Question

I am new to this concept of zero knewledge proofs, from what I understand it is not a mathematical general equation like RSA or ECC cryptography has, but its a methodology that varies from problem to problem.

What I want to do is to let a prover prove that his public key belongs and exists in a known public bulletin board that contains a list of public ECC keys without revealing the public key so it should be encrypted (the public key should be encrypted for privacy reasons).

Answer 1

There're different approaches to build ZKP for different statements. E.g., there'e ad-hoc protocols: Schnorr protocol allows you to build a proof of knowledge of discrete logarithm of some group element. There're also universal ZKP protocols, which allows you to build a proof for any statement, formulated as a computational circuit. This is a relatively new field of research, and examples of efficient protocols are STARKs, Bulletproofs, ZkSNARKS. You can google for them, but I should warn you in advance that unlike ad-hoc solutions, all these universal protocols are pretty complex and not-easy to understand.

If your goal is only to proof that you know discrete logarithm of some of ECC points from the list, you can use this simple ad-hoc solution, a modification of well-known Schnorr protocol: https://www.cs.au.dk/~ivan/Sigma.pdf (search for OR-proof there).

Also, as I understand, you're looking for solution to prove membership of party in some group, and make it anonymously. For this goal, there's a crypto-primitive called "group signatures", or "ring signature", and "linkable group/ring signatures". E.g., ring signature allows you to sign a message with your secret key, so that everybody can see that the signature is correct and belong to some member of the group, and at the same time, nobody knows who exactly signed it (so, it's anonymous). Linkable group signature scheme allows detecting of 2 signatures of the the person (e.g. it could be useful for voting, in order to prevent a person to vote twice).

Depending on your basic signature scheme and using keys, you should look for corresponding signature schemes with additional features. E.g., if you're using elliptic curve crypto, so that your public keys are points on elliptic curve, you could look into Schnorr Ring Signature Scheme.

Answer 2

Theoretically speaking it's rather easy.

You simply have the key owner (the prover) perform a proof that they have the private exponent for at least one of the public keys on the list. This is a standard OR-proof which composes multiple (Sigma) Zero-Knowledge proofs. As you're using standard elliptic curve crypto the public keys will be of the form $P_i=[x_i]G$ for a private key $x_i$ and the public key $P_i$ and some curve-defined generator $G$, this allows you do use a standard Schnorr-proof.

Prover (knowing $x_i, P_1,\ldots, P_N$):

1. Randomly choose $r\stackrel{\$}{\gets}\mathbb Z_q$ that is an integer in $[0,q)$.
2. Compute $a_i=[r]G$
3. Choose random $c_1,\ldots,c_{i-1},c_{i+1},\ldots,c_N\stackrel{\$}{\gets}\{0,1\}^h$ for $h$ being the output length in bits of your favourite hash function, e.g. SHA-256.
4. Randomly choose $z_1,\ldots,z_{i-1},z_{i+1},\ldots,z_N\stackrel{\$}{\gets}\mathbb Z_q$ and set $a_j=[z_j]G-[c_j]P_j$ for all $j\neq i$.
5. Compute your favourite hash function $c=H(a_1\|\ldots\|a_N)$ or alternatively receive a random $h$-bit string from an interactive verifier after sending them the $a_1,\ldots,a_N$ or if you have some context $m$ to the proof, append it at the end of the hash input.
6. Compute $c_i=c\oplus c_1\oplus\ldots\oplus c_{i-1}\oplus c_{i+1}\oplus\ldots\oplus c_N$
7. Compute $z_i=r+x_i\cdot c_i\bmod q$
8. Output (c_1,\ldots,c_N,z_1,\ldots,z_N) as the proof along with $m$ if any. For the interactive case outputting the $z$s suffices.

Verifier (knowing $P_1,\ldots,P_N$ and receiving $(c_1,\ldots,c_N,z_1,\ldots,z_N)$ as well as the optional $m$):

1. In the interactive case: Output a random string $c$ of length $h$-bit after getting the $a$s, then receive the proof.
2. Compute all the $a$s: $a_i=[z_i]G-[c_i]P$
3. In the interactive case: Check that $c_1\oplus\ldots\oplus c_N=c$ and that the $a$s computed in step 2 match those received before step 1.
4. In the non-interactive case: Check that $c_1\oplus\ldots\oplus c_N=H(a_1\|\ldots\|a_N)$ or with the context appended as specified.
5. If no check failed so far, accept the proof, otherwise reject it.

Of course the issue with the above protocol is that the proof scales linearly with the number of public keys on the board, but you'd need more sophisticated approaches to solve that (e.g. Ring Signatures).