2
$\begingroup$

Question: How is it possible to adapt a ZKP for a homomorphic ciphertext to still be valid after said ciphertext has been re-randomized?

Context: In a lot of e-voting systems homomorphic encryption is used to tally the individual votes preserving the privacy of the individual voters as only the total tally is revealed. Each voter must provide valid ZKP's proving that their vote is correctly formed and one of the possible values.

A way to achieve privacy is to re-randomize the ciphertext as well as the corresponding ZKP. This seems to be possible using Groth-Sahai proofs though I do not understand how as the ZKP somehow has to be bound to the ciphertext.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

First (if it's not the case) you have to read carefully the original Groth-Sahai paper.

We can focus on a concrete example to understand why it's possible: in the "SXDH" setting for example (page 24); Let suppose we have a commit $\vec{c_1}$ for a vector of elements of $G_1$ and a commit $\vec{c_2}$ for a vector of elements of $G_2$. And a proof $(\vec \pi, \vec \theta) $

You can change randomize the commitment $c_2$ (by adding $R'\vec{u}$ to $\vec{c}$ for example), but if you do this the proof will be no more valid.

Then you have to add also the corresponding randomness to the proof, here it means you have to add to $\vec\pi$ $R'\Gamma c_2$.

More generally you have to randomize the commitment and the proof in the same time (Notice that in the groth sahai model commits are not considered as cipher but as part of the proof).

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks, the notion of the commitment being part of the proof allowing both to be re-randomized at the same time makes sense to me. I have only looked at the paper quickly and gathered that the proof itself is quite expressive instead of multiple simple proofs which answers an unstated question of mine though the paper itself is too advanced for me to understand without some pre-reading. There does not seem to be a practical implementation of the proof system. Are you aware of any other (maybe simpler) system that solves it or is this only possible with bilinear groups? $\endgroup$
    – Mibokess
    Sep 19, 2019 at 16:30
  • $\begingroup$ I don't know exactly how to dolve your problem, but it will be hard to find something with the same power and more simple than Groth-Sahai. I advise you to think if you really need this, or if a rerandomizable ciphertext/signature scheme is not enough for your problem. $\endgroup$
    – Ievgeni
    Sep 23, 2019 at 13:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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