Score:2

Proving same value in ciphertext and Pedersen commitment Using Sigma Zero Knowledge

cn flag

Let we have 2 generator $G$ and $H$ in any elliptic curve.

A prover creates a ciphertext with Homomorphic ElGamal, $(r_1G,\;mG + r_1P)$ such that $r_1$ is random and $P$ is public key of the prover.

Then the prover creates a Pedersen commitment $(mG + r_2H)$ or $(mH + r_2G)$ if it makes the proof easier.

The prover wants to make a proof that the encrypted message and the message hidden in the commitment are the same.

I think there are 3 things that need to be proven in this proof.

  • has $r_1$ information
  • has $r_2$ information
  • m is the same

The first two are easy. The third one was confusing. How can we create such a proof using sigma protocols?

knaccc avatar
es flag
The Pedersen commitment should be of the form $mG+r_2H$, not $(mG,\ r_2H)$
mathd avatar
cn flag
@knaccc I edit them.
knaccc avatar
es flag
Your protocol means that the verifier cannot decrypt the ciphertext to learn $m$, the verifier can only decrypt it to learn $mG$ (unless $m$ is of low entropy and can be brute forced). Was this your intention?
mathd avatar
cn flag
@knaccc yes, this provides homomorphic property. $m$ is a small number
Score:2
es flag

The prover provides the ciphertext $(A,B) = (r_1G,\ M+r_1P)$ and the Pedersen commitment $C = M + R_2$, where $M=mG$ and $R_2=r_2H$.

The prover also provides the verifier with a simple Schnorr signature for the public key $R_2$ on the generator point $H$, thus proving knowledge of $r_2$:

$(c,s)=(\texttt{hash}(kG),\ k-c\cdot r_2)$, where $k$ is a uniformly random nonce scalar, and $\texttt{hash}$ is a cryptographically secure hash function that returns a scalar value.

Note that the prover does not provide the $R_2$ point, only the signature $(c,s)$.

The verifier decrypts the message:

$M'= B - xA$, where $x$ is the verifier's public key such that $P=xG$

The verifier then uses brute force to recover the value $m'$ such that $M'=m'G$ (since the questioner has explicitly stated that $m$ is a small number).

This proves that $M'$ was created as a multiple of $G$, and that $M'$ is not composite (not created as a multiple of $H$ or by adding a multiple of $H$).

The verifier then calculates $R_2'=C-M'$

The verifier checks the Schnorr signature: $c\overset{?}{=} \texttt{hash}(sH+cR_2')$

If the signature verifies, it proves that $R_2'$ must have been constructed purely as a multiple of $H$, since $r_2'$ such that $R_2=r_2H$ is unknowable if $R_2'$ is composite (was constructed as a multiple of $G$ or by adding a multiple of $G$).

In conclusion, the verifier has been able to decrypt $M'$, and is satisfied that the Pedersen commitment must have also been a commitment to $M'$, because when we subtract $M'$ from the commitment, the result is proven to have been constructed purely as a multiple of $H$.

mathd avatar
cn flag
In this proof, the scenario of someone with secret value $x$ is considered. But I need a proof that someone with no secret value can verify.
knaccc avatar
es flag
@midmotor In your question, when you said "$P$ is public key of verifier", you meant that $P$ is the public key of the recipient and intended decryptor of the ciphertext, and the recipient is a different person than the verifier? Can you describe more about your scenario? How many possible values of $m$ are there?
mathd avatar
cn flag
It was a mistake, I fixed it as the public key of the prover.
knaccc avatar
es flag
@midmotor how many possible values of $m$ are there? And to confirm, are you saying that the prover will always know the private key associated with $P$? So the prover is never encrypting for a public key where the prover does not know the associated private key?
mathd avatar
cn flag
firstly, $m$ is between 0 - $2^{32}$ to do brute-force. Yes, prover know the private key associated with $P$ or depending on the situation, he may also not know (he can also encrypt with another public key), but it is certain that the verifier does not know the private key corresponding to the public key.
knaccc avatar
es flag
@midmotor I'm not sure that what you're asking is possible. Perhaps if you elaborated on the problem you're trying to solve, there could be a different approach that could work
Score:1
in flag

To achieve "the same $m$", use the same Schnorr-like response for the secret $m$ both for commitment and for ciphertext.

Use 3 responses: for $m$, $r_1$, $r_2$, all produced with the same challenge $c$. If you want your proof to be non-interactive, produce the challenge as a hash of group generators, commitment, ciphertext, and proper group elements - the first message of Schnorr protocol for 3 secrets.

The last part requires 3 group elements for $( + _2 )$ commitment variant, and 4 elements for $( + _2 )$. This difference comes from using the same group element associated with message for proof verification and hashing to challenge in case of using the same generator for both commitment and ciphertext.

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.