Party A has a ciphertext $c = (g^r, g^2 h^r)$, which is an encryption of the integer 2 under A's public key, $h$. The encryption scheme used is the additively homomorphic variant of El Gamal. This ciphertext has been homomorphically modified by other parties, so A does not know the randomness $r$.

Is there a way for A to prove that $c$ is an encryption of a non-negative integer? All of the range proof schemes I have found seem to use commitments, which require A to know the randomness in the ciphertext.


First (just to be sure): $(g^r, g^2h^r)$ is not an encryption of $2$ but of $g^2$ (because decryption in general will only give you $g^2$, then you are left solving the DLOG. I'll assume this is not a problem in your scheme (e.g,. there are only polynomially many valid values that may ever be encrypted).

Second: it is unclear what you mean by "non-negative integer". All exponents of $g$ can be interpreted as a non-negative integers. So what would ne negative integer be? I'll assume you have some range of numbers inside $\mathbb{Z}_{|\mathbb{G}|}$ that you interpret as "non-negative". I won't mess with your desired range proof, just give you an idea for the ElGamal part.

I'll call the integer you want to range-proof $z$ and your ciphertext $(x,y) := (g^r, g^zh^r)$ (in your example, $z = 2$). You commit to $z$ with whatever commitment your range proof needs. Send the commitment and the ciphertext to the verifier. Then you should prove (e.g., with a Schnorr-like protocol, see Construction 2.5 here) that there exists a secret key $a$ (the ElGamal secret key) and that you know $z$ such that:

  • $h = g^a$ (i.e. $a$ is indeed the ElGamal key)
  • $(x^{-1})^a\cdot y = g^z$ (the ciphertext decrypts to $z$)
  • that your commitment opens to $z$.

Then, using the commitment to $z$, you run your range proof.

Another route may be to omit the extra commitment and just integrate the range proof into the same Sigma protocol, where $z$ is already a part of. My guess is that the range proofs you found only require you to commit to the value so that the statement is nontrivial ("I know some integer in this range" is not a particularly interesting statement by itself), but can probably be used in conjunction with other statements in the same protocol without an extra commitment (effectively, the ElGamal ciphertext would be your commitment to $z$).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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