3
$\begingroup$

Given $v \in Z$, a prover knows $v$ and the verifier knows an encryption of $v$.

The prover provides the verifier with the encryptions of two values $m$ and $n$

How can the verifier verify that $m+n=v$ ?

I cannot find any scheme/algorithm in the literature I have searched, other than range proofs, and I am looking for pointers.

To illustrate, here is a naive (and wrong) approach to the problem.

Assuming a generator $g$ in a group of order $p$, co-primes.

The verifier knows $g^v$, the prover can provide $g^m$ and $g^n$. The verifier then verifies that $g^mg^n=g^{m+n}=g^v \pmod p$.

However if the prover provides $m'$ and $n'$ such that $m'+n'=m+n+k(p-1), k \in Z^*$ then the equation above verifies although $m'+n'> v$

(according to Fermat little's theorem $g^{k(p-1)}=(g^{p-1})^k \equiv 1 \pmod p$)

$\endgroup$
5
  • $\begingroup$ How is $v$ "given"? The verifier must know something about it, otherwise there is nothing to prove. $\endgroup$
    – fkraiem
    Aug 25, 2018 at 6:29
  • $\begingroup$ @fkraiem The verifier knows a "blinded" $v$ whatever the encryption/blinding scheme is. In the naive scheme above, the verifier knows $g^v$ $\endgroup$
    – BGR
    Aug 25, 2018 at 6:31
  • $\begingroup$ @fkraiem I have reworded the question following Yehuda Lindell remark below $\endgroup$
    – BGR
    Aug 25, 2018 at 22:27
  • 1
    $\begingroup$ Seems that selecting a certain homomorphic (partial) encryption algorithm will do - crypto.stackexchange.com/questions/3626/… may be limiting v? $\endgroup$
    – Moti
    Aug 26, 2018 at 2:40
  • $\begingroup$ @Moti thanks. Building a ZKP around an additive homomorphic encryption scheme is likely the right direction. Will give it a try (but I would still prefer a reviewed existing formalization rather than "building" my own) $\endgroup$
    – BGR
    Aug 26, 2018 at 6:07

1 Answer 1

5
$\begingroup$

For this, it suffices to use additively homomorphic encryption. There are two possibilities for this: Paillier and ElGamal in the exponent.

For Paillier, given an encryption of $v$, $m$ and $n$, one can compute an encryption of zero by $v - m - n$. In the Damgard-Jurik paper, there is a very efficient zero-knowledge proof for proving that a ciphertext is an encryption of 0. So, this solves your problem.

For ElGamal, typical encryption is $(g^r,h^r\cdot m)$ where $h$ is the public-key. This is not additively homomorphic. However, you can change this to $(g^r,h^r\cdot g^m)$ and now you can add and subtract ciphertexts. With the same method as above, one can compute $v-m-n$ inside the ciphertext and then get an encryption of 0 which is just $(g^r,h^r)$. This implies that $(g,h,g^r,h^r)$ is a Diffie-Hellman tuple and this can be easily proved using known techniques for Sigma protocols. Note that this scheme is not efficiently decryptable, since decrypting only gives $g^m$ and you need to solve the discrete log problem to find $m$. Thus, if $m$ is from a small range, you can do this. Otherwise you cannot. However, it is an additively homomorphic commitment scheme, which may suffice for your application.

$\endgroup$
5
  • $\begingroup$ Thank you. I am going through the Damgard-Jurik Paper. For ElGamal, I do not understand how the additive version does not suffer from the same flaw as my naive scheme above i.e. assuming $p$ is the order of the group, an encryption of $v-m'-n'$ with $m'+n'=m+n+k(p-1)$ is also an encryption of zero but $m'+n'$ is not equal to $v$ $\endgroup$
    – BGR
    Aug 27, 2018 at 5:32
  • $\begingroup$ @Yehuda I am looking into the encryption used for bitcoin. Is there an application/program that allow experimenting with this encryption (basically ElGamal). My email [email protected] thanks $\endgroup$
    – Moti
    Aug 27, 2018 at 7:25
  • $\begingroup$ For ElGamal, not that I know of. For Paillier, yes. Just Google and you'll find some. $\endgroup$ Aug 27, 2018 at 7:41
  • $\begingroup$ @BrunoGrieder Your solution is not secure since $g^v$ does not fully hide $v$. That’s why you need ElGamal in the exponent. Nevertheless, note that both for ElGamal in the exponent and Paillier, equality is only modulo the group order. If you want equality over the integers, then you need the numbers to be small relative to the modulus, and you need to add range proofs to prove that v,m,n are all “small”. This will guarantee no modulo operation. $\endgroup$ Aug 28, 2018 at 9:33
  • $\begingroup$ @YehudaLindell Sure my solution is not secure; it was noted as a "wrong" scheme. I will check what is best for my application between range proofs and enforcing, if I can, that numbers remains at least twice smaller than the modulus. Thanks again. $\endgroup$
    – BGR
    Aug 28, 2018 at 19:01

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.