# Zero knowledge set membership protocol

I read that paper Efficient Protocols for Set Membership and Range Proofs of Camenisch et. al that describes the zero knowledge range proof. The paper applications looks interesting like if you want to proof your age between a range without stating exactly what is the exact age?

But I read that a commitment (C) provided by the prover to the verifier should be first verified by a trusted party before it can be used in the zero-knowledge protocol? Is it just a signature on the C value?

I need a simple explanation of how such a commitment can be done. Since as far as I know about a commitment (C) that is only known for only one party.

• I haven't looked at that paper, but given your description it sounds like that you need some kind of proof (like from a trusted third party) that your commitment represents your actual age (in your example) before the the ZKP has any meaning. – VincBreaker Feb 1 at 10:33
• @VincBreaker: Yes. That is exactly what I want. How that commitment can be done? Please I am in a bad need to such solution. – Heba Mohsen Feb 1 at 20:57

A trivial approach would be to let the trusted party generate the commit and send the private vector along the signed commit to the proover, which should like this in your age range checking example:

Notation: $$P$$ is the proover, $$T$$ is the trusted party, $$V$$ is the verifier, $$a$$ is the information to convince $$T$$ of $$P$$'s age, $$A \rightarrow B: x$$ means that party $$A$$ send information $$x$$ to party $$B$$.

1. $$P \rightarrow T$$: $$a$$
2. $$T$$ generates chooses a random $$r$$, calculates $$C=rG+[age]H$$ and signs $$C$$ using his private key.
3. $$T \rightarrow P$$: $$r, C, signature$$
4. $$P \rightarrow V: C, signature, proof$$

Whilst straightforward, the trusted party get's to choose the commit which you may not want depending on how much you trust the trusted party, so here is another approach that allows the proover to choose $$C$$.

1. $$P$$ chooses a random $$r$$ and calculates the commit $$C = rG + [age]H$$.
2. $$P$$ signs $$a$$ with $$r$$ as private key
3. $$P \leftarrow T: C,a, signature_a$$
4. $$T$$ looks up $$P$$'s age, calculates $$R=C-[age]H$$, verifies $$signature_a$$ against $$R$$ and sign's $$C$$ using $$T$$'s private key.
5. $$T \rightarrow P: signature_c$$
6. $$P \rightarrow V: C, signature_c, proof$$

Of course, $$V$$ will have to verify the signature. Instead of a signature, $$V$$ could also make a request to $$T$$ to check whether it approves $$C$$ which allows $$T$$ to revoke easily but requires you put more trust into the trusted party.

Lastly, I'd like to mention a completely different approach used in Monero's RingCT which uses commits to represent balances and the blockchain to keep track of and to verify them.

• Where is the difference between the symbol “a” and “age” ? . Why the purpose of calculating R value in the second approach? Since the TP already knows “ age “ value – Heba Mohsen Feb 1 at 23:50
• $[age]$ is the actual age of $P$, while $a$ is the information to convince $T$ of $P$'s age, for example a photocopy of $P$'s passport. You can't stop $T$ from knowing $P$'s age since he needs it to verify the commitment, but you can stop $T$ from knowing and controllong $r$ using the second scheme. – VincBreaker Feb 2 at 18:03
• @VibcBreaker if the commitment in the form of $C=g^{[age]} g^r$. How to reconstruct the second protocol so $T$ can verify the commitment without knowing $r$ – Heba Mohsen Feb 3 at 0:44
• @Heba Mohnsen 1. Your commitment should be in the form of $C=h^{[age]}g^r$ or $C=g^{[age]}h^r$ with the discrete logarithm of $h$ to $g$ unkown or your commitment scheme is broken. 2. You need to change from a additive to multiplicative notion, $xG$ becomes $g^x$ and $C-[age]H$ becomes $C / h^{[age]}$. – VincBreaker Feb 3 at 9:46