# Zero Knowledge Set Membership proof

ZK set membership:

I am trying to create my own zero knowledge set membership proof for a commitment to an element in the set for small sets. I am a beginner in such works, so can someone help me find if there are some flaws.

It goes like this: Public parameters (p,q,s,g,m): p,q and s are prime numbers such that p-1 has a large prime factor q, and q-1 has a large prime factor s. Likewise, g and m are generators of groups modulo p and q, order q and s respectively. Set S = {e1,e2,..en} for some small n (like 100). We have one-way function f：S ->{1,q}, which transforms each set element into a number between 1 and q-1. Of course, a verifier can calculate a set T, such that T = {vi | 1 <= i <= n,vi = gf (ei) }.

The process goes like:

Commitment: c = gf(ek)mr is a commitment for element ek in S, where r is a random number in {1,s-1},

ZK Interaction: Prover calculates a set A = {ai | i <= 1 <= n, ai = gf(ek)mri} where ri is generated randomly between 1 and s-1 Generates a random permutation function, Permn and sends Permn(A) to verifier

verifier calculates b randomly in {0,1} and sends b to prover

Here: 0 and 1, respectively mean "prove that A is a transformation of T" and "Show me where c is in A" respectively. If b = 0，prover sends to verifier, Permn(R), where R = {ri | 1 <= i <= n}, what we calculated earlier. Verifier verifies that vimri = ai for each vi in T0<=i<=n, If b = 1, prover sends to verifier r ' = rk-r and the location of ak in Permn(A). Verifier verifies that cmr ' = ai. [Note: This is r ' at the very top. Very small so might be confusing]

The same process is repeated many times until the verifier is convinced

Proof of ZK: Simulator first calculates b.

If b = 0, the process is same as normal interaction above.

if b = 1, The simulator creates n - 1 random ej and rj, and calculates aj = gf(ej)mrj}. It then also calculates sk = cmrk where rk is randomly in {1,s-1}. At first,it sends Permn({sk} U {aj | 1 <= j <= n-1}). Simulated verifier then releases the b above. Then the simulated prover sends location of sk in the original set as well as rk. They must be distinguishable from real interaction if

This is the part I am least confident about. The commitment c must be indistinguishable from the aj produced by the simulator in case of b = 1 as stated above. Not just the committed element but it should apply to all elements in the original set S. That is the part I am least confident about is the hiding part of commitment, I am fairly confident about the binding part, which does seem to require solving DL problem, if you want to switch the element. I don't know much about Legendre symbol, and I would be happy if anyone can tell me if there is a way to rule out some elements in the set from the commitment using Legendre symbol or something, which is of course unacceptable.

One solution might be to use f that transform each element ei to either only odd or even number between 1 and q-1. Of course, it should not generate it as some power of m, otherwise the binding property of commitment will be lost.

EDIT: it is proof for HVZK and not for ZK. But we can still make it a proof of ZK by tweaking the random numbers ri in the prover's commit phase until the challenge by the verifier, (which may be calculated from the set A deterministically) matches the simulator's original prediction which should succeed with high probability in polynomial time since it is a single bit challenge. On the other hand, for small challenges like this, verifier actually sending random numbers honestly is the best bid for him, because prover realizing that the challenge bit is actually calculated from the committed set will allow her to cheat the verifier easily.

EDIT： Well,well, well. I maybe don't need double exponentiation at all. The commitment for element ei can just be f(ei)gr with random unknown r. As long as the function f maps an element to pseudo-randomly generated number from Z*p. Maybe works better with some sort of random oracle in Z*p. But for that we use whole of group Z*p and not some order q subgroup. But for better confidence, we might as well use the order q subgroup (Group of quadratic residues). But for that, elements ei in the set should either all map to quadratic residues or to quadratic non-residues modulo p by the function f, so that Lagrange symbol cannot be used to rule out any element. Only thing to be careful about now is that function f should be well tested and its calculation should not in any way reveal the discrete logarithm of f(ei) in base g modulo p, otherwise the binding property of the commitment will be lost.

• I don't want to post this as an answer, since I like to be able to actually explain why things are as I claim, but from looking at your proof it seems to rely on solving discrete logarithm. I'm sorry I don't have a proper explanation prepared but this is the best I can do at the moment. – Serpent27 Sep 7 '20 at 6:02
• @Serpent27 Yes, it relies mostly on solving discrete log. The biggest concern is the indistinguishability (hiding part) of the commitment c. That is, someone with no knowledge of r should not be able to efficiently tell, if given two commitments c1 and c2, whether they are commitment for same element of the set or not. Nor, should they be able to rule out any element of the set from the commitment alone. I am actually fairly confident about the zero knowledge part – Manish Adhikari Sep 7 '20 at 7:54