# Σ-protocol that proves an even number was committed using Pedersen commitment scheme

I need to design a Σ-protocol ZKP using Pedersen commitment scheme that proves knowledge of a, y such that statement A = h^y * g^a only holds for even y (y=2x).

Of course, the protocol needs to be sound, special-sound, and honest-verifier zero-knowledge.

Any suggestions?

A standard Pedersen commitment range proof will demonstrate that $$y$$ is constructed from the addition of a series of powers of 2.
All you have to do is slightly modify the range proof so that you do not include $$2^0=1$$ as one of the powers of 2.
• Probably more complex than that. For example you have $y=1$ from $Z_5$, you can prove $y= 4+2 = 1 \bmod 5$. May 16 at 14:10
• Is that done by restricting the maximum power? If so, there needs to have a constraint that the bit length of $y$ is at least 1 bit shorter than that of the group size. But this could be satisfiable in the original question. May 17 at 11:21
• @ChangyuDong With range proofs, the prover and verifier are agreeing on the list of powers of 2 (or 3, or otherwise). Then the prover creates a Pedersen commitment for each item in that list, and provides proof that each commitment is either to zero or to that power of 2. They also provide a signature showing their commitments sum to the correct total. In Monero, for example, powers used are $2^0...2^{63}$, and that proves $0\leq amount<2^{64}$. If the protocol was that the list would not contain $2^0$, then it would be impossible to construct an odd number less than $2^{64}$. May 17 at 12:23
• Yes that is exactly what I meant -- if $y\in Z_q$ and $|q|=l$, then the maximum power you can allow in the range proof is $2^{l-1}$, so you have to make sure $|y|\le l-1$. May 17 at 12:37