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).

  • $\begingroup$ @SEJPM there is nothing exotic just a simple list of public keys that represnts all the users, so i dotn want people to have transactions that lead back to their real identity using zero knwoledge proof bu in the same time anyone can verify that this transaction is made by someone who belongs to that list of accepted users $\endgroup$ – ezio Jun 4 '20 at 12:55

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.

  • $\begingroup$ you have a wonderful brain sir ,your answer is clear and obvious and understandable ,thank you so much , but i have a question , it looks like ring signature is the answer to my problem ,so from what you said zknarks and starks are protocols that can also solve my problem but are too complex unlike ring signatures which is easier to undersand and implement for someone who is new to cryptography? $\endgroup$ – ezio Jun 12 '20 at 9:59
  • $\begingroup$ @ezio yes, you got it right: zksnarks works for many problems, so they are universal but very complex. For your specific problem, you could use simpler solutions: 1) Schnorr-like ZKP protocol 2) Ring signatures. Complexity of these 2 solutions are pretty similar, you can choose either of them. $\endgroup$ – Mikhail Koipish Jun 13 '20 at 10:18
  • $\begingroup$ thank you so much $\endgroup$ – ezio Jun 13 '20 at 21:32

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).

  • $\begingroup$ sir you are very generous and helpfull , but i think it will take me years and studie to understand your answer because im noob i just know that there is a curve and there is a public and a private key and a random genrator point thats all i know in elliptic curve cryptography , but really thank you , you really really made my day even tho i feel very bad about myself , you are awesome $\endgroup$ – ezio Jun 4 '20 at 14:10
  • 2
    $\begingroup$ Fantastic answer @SEJPM $\endgroup$ – Woodstock Jun 4 '20 at 16:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.