Score:1

Range proof for elgamal ciphertext

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

Geoffroy Couteau avatar
cn flag
Hi! I answered variants of this questions several time on this website, see for example [this thread](https://crypto.stackexchange.com/questions/53745/is-it-possible-to-create-a-zero-knowledge-proof-that-a-number-is-more-than-zero/53762#53762). If this does not answer your question, could you specify where you are stuck?
@GeoffroyCouteau Hello,I was more spefic in a comment on the answer below.
Score:0
es flag

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.

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$?
knaccc avatar
es flag
Only someone that knows $x$ can forge it, and yes you can generate a range proof without knowing $x$.
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.