2
$\begingroup$

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

$\endgroup$
2
  • 1
    $\begingroup$ Hi! I answered variants of this questions several time on this website, see for example this thread. If this does not answer your question, could you specify where you are stuck? $\endgroup$ May 11, 2022 at 21:34
  • $\begingroup$ @GeoffroyCouteau Hello,I was more spefic in a comment on the answer below. $\endgroup$ May 12, 2022 at 9:19

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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$? $\endgroup$ May 12, 2022 at 9:17
  • 1
    $\begingroup$ Only someone that knows $x$ can forge it, and yes you can generate a range proof without knowing $x$. $\endgroup$
    – knaccc
    May 12, 2022 at 9:29

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.