2
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ The Pedersen commitment should be of the form $mG+r_2H$, not $(mG,\ r_2H)$ $\endgroup$
    – knaccc
    Dec 25, 2022 at 21:56
  • $\begingroup$ @knaccc I edit them. $\endgroup$
    – midmotor
    Dec 25, 2022 at 22:17
  • $\begingroup$ 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? $\endgroup$
    – knaccc
    Dec 26, 2022 at 1:48
  • $\begingroup$ @knaccc yes, this provides homomorphic property. $m$ is a small number $\endgroup$
    – midmotor
    Dec 26, 2022 at 5:33

2 Answers 2

2
$\begingroup$

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$.

$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$
    – midmotor
    Dec 30, 2022 at 13:14
  • $\begingroup$ @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? $\endgroup$
    – knaccc
    Dec 31, 2022 at 6:49
  • $\begingroup$ It was a mistake, I fixed it as the public key of the prover. $\endgroup$
    – midmotor
    Jan 2, 2023 at 5:51
  • $\begingroup$ @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? $\endgroup$
    – knaccc
    Jan 2, 2023 at 6:54
  • $\begingroup$ 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. $\endgroup$
    – midmotor
    Jan 2, 2023 at 10:42
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking โ€œPost Your Answerโ€, you agree to our terms of service and acknowledge you have read our privacy policy.

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