2
$\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$
  • $\begingroup$ How is $v$ "given"? The verifier must know something about it, otherwise there is nothing to prove. $\endgroup$ – fkraiem Aug 25 '18 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 '18 at 6:31
  • $\begingroup$ @fkraiem I have reworded the question following Yehuda Lindell remark below $\endgroup$ – BGR Aug 25 '18 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 '18 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 '18 at 6:07
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$
  • $\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 '18 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 motib1mod@gmail.com thanks $\endgroup$ – Moti Aug 27 '18 at 7:25
  • $\begingroup$ For ElGamal, not that I know of. For Paillier, yes. Just Google and you'll find some. $\endgroup$ – Yehuda Lindell Aug 27 '18 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$ – Yehuda Lindell Aug 28 '18 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 '18 at 19:01

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.