1
$\begingroup$

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?

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.