Score:1

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

pk flag

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
es flag

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.

Changyu Dong avatar
cn flag
Probably more complex than that. For example you have $y=1$ from $Z_5$, you can prove $y= 4+2 = 1 \bmod 5$.
knaccc avatar
es flag
@ChangyuDong the range proof prevents that overflow. You would not allow the range to exceed the group size of the generator.
Changyu Dong avatar
cn flag
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.
knaccc avatar
es flag
@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}$.
Changyu Dong avatar
cn flag
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$.
knaccc avatar
es flag
@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.
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.