Score:1

# Σ-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?

Score:1

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.

See this answer for an explanation of how to construct a simple range proof.

Probably more complex than that. For example you have $y=1$ from $Z_5$, you can prove $y= 4+2 = 1 \bmod 5$.
@ChangyuDong the range proof prevents that overflow. You would not allow the range to exceed the group size of the generator.
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.
@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}$.
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$.
@ChangyuDong yes, I was proceeding on the assumption that it would be meaningless for $y$ not to be restricted, given that there are infinite values of $y$ that would result in the same $A$, and the group size will probably be prime. And btw slightly cleverer range proof constructions can hit an exact upper range limit, even if that upper limit is not a power of 2.