1

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?

JayDew
  • 13
  • 3

1 Answers1

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.

knaccc
  • 4,732
  • 1
  • 16
  • 30
  • Probably more complex than that. For example you have $y=1$ from $Z_5$, you can prove $y= 4+2 = 1 \bmod 5$. – Changyu Dong May 16 '22 at 14:10
  • @ChangyuDong the range proof prevents that overflow. You would not allow the range to exceed the group size of the generator. – knaccc May 16 '22 at 14:42
  • 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. – Changyu Dong May 17 '22 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}$. – knaccc May 17 '22 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$. – Changyu Dong May 17 '22 at 12:37
  • @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. – knaccc May 17 '22 at 12:46