2

Alice has an ElGamal public key $y=g^x$. Bob encrypts a value $g^b$ based on Alice's Elgamal public key and he ends up with a ciphertext $(g^by^r, g^r)$. Can Bob prove that the value $b$ is in some range without revealing it or do you need to be the "owner" of the ElGamal secret key $x$ to create such proofs?

If $g^b$ is confusing then ignore it and consider a value $b$, I just need to know if I can create a range proof without knowing the $x$.

Maarten Bodewes
  • 92,551
  • 13
  • 161
  • 313
Μενέλαος Κοκάρας
  • 31
  • 3

1 Answers1

2

If your method of mapping your value $b$ to a group element is $g^b$, then creating a range proof for an El Gamal encryption is exactly the same as creating a range proof for a Pedersen commitment.

With El Gamal, you have $g^by^r$ where $b$ is the value, $r$ is the sender's ephemeral private key, and $y$ is the recipient public key.

Interpreted as a Pedersen commitment, you have $g^by^r$ where $b$ is the value, $r$ is the blinding factor, and $y$ is the alternative base point for which the discrete log w.r.t. $g$ (i.e. $x$) is unknowable to the committer/sender.

Note that since the recipient knows $x$, they can forge range proofs.

Details of how to create a simple range proof are here.

knaccc
  • 4,732
  • 1
  • 16
  • 30
  • So only the recipient who knows $x$ can forge a range proof for $b$ in $g^{b}y^{r}$?If for example I encrypt a value $b$ based on someone else's $y$ which of course I dont know the $x$ can I generate a range proof for $g^b$? – Μενέλαος Κοκάρας May 12 '22 at 09:17
  • 1
    Only someone that knows $x$ can forge it, and yes you can generate a range proof without knowing $x$. – knaccc May 12 '22 at 09:29