3
$\begingroup$

I was wondering whether there exists randomizable zero-knowledge proofs. What I mean by randomizable is that assume I have a zero-knowledge proof of knowledge $\pi$, stating that I know $x \in \mathbb{Z}_q$ for a prime $q$, such that $Q = g^x$, and I randomize $Q$ as $Q' = Q^r$ for a random $r \in \mathbb{Z}_q$. Then, I wish to prove that $Q'$ is a randomized version of $Q$. So, is it possible to somehow also randomize the proof $\pi$ into $\pi'$ for this?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
8
$\begingroup$

Yes there are. I guess you're looking into non-interactive zero-knowledge (NIZK) proofs, since you're assuming that you have at hand a proof $\pi$. A common approach for building NIZKs in crypto is to rely on the Groth-Sahai methodology, which produces highly structured NIZKs using elliptic curves equipped with a bilinear maps. It was first observed in this paper that Groth-Sahai proofs can be randomized - i.e., you can randomize a statement together with its proof so that the randomized proof is indistinguishable from an honest proof computed on the randomized statement. This was used to build anonymous credentials with strong properties, and had many other applications in subsequent works.

Improve this answer
$\endgroup$
3
  • $\begingroup$ What's the current state-of-the-art in this? I mean the paper seems a bit old already. Are there any newer papers about the same/similar topic? $\endgroup$
    – user4936
    Feb 3, 2020 at 9:51
  • 2
    $\begingroup$ As far as I know, the randomization method in itself is still state of the art - it works fine and it is not clear whether one can have much more efficient randomizations. Recent works have mainly shown more applications of this randomization method rather than improving the method itself. There is also a very recent work on getting a stronger fully homomorphic randomization property, given in this nice paper. $\endgroup$
    – Geoffroy Couteau
    Feb 3, 2020 at 10:27
  • 2
    $\begingroup$ A last important recent work: SAVER is a system which consists of an encryption scheme with nice properties, together with a very efficient proof system for proving properties of this encryption scheme. It allows in particular to rerandomize ciphertexts together with their associated proof very efficiently; this gives a rerandomization method for the more modern SNARK-style NIZKs. $\endgroup$
    – Geoffroy Couteau
    Feb 3, 2020 at 10:29

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.