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 T, 0<=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.