Paper 2011/012

Minimizing Non-interactive Zero-Knowledge Proofs Using Fully Homomorphic Encryption

Jens Groth

Abstract

A non-interactive zero-knowledge proof can be used to demonstrate the truth of a statement without revealing anything else. It has been shown under standard cryptographic assumptions that non-interactive zero-knowledge proofs of membership exist for all languages in NP. However, known non-interactive zero-knowledge proofs of membership of NP-languages yield proofs that are larger than the corresponding membership witnesses. We investigate the question of minimizing the communication overhead involved in making non-interactive zero-knowledge proofs and show that if fully homomorphic encryption exists then it is possible to minimize the size of non-interactive zero-knowledge proofs and get proofs that are of the same size as the witnesses. Our technique is applicable to many types of non-interactive zero-knowledge proofs. We apply it to both standard non-interactive zero-knowledge proofs and to universally composable non-interactive zero-knowledge proofs. The technique can also be applied outside the realm of non-interactive zero-knowledge proofs, for instance to get witness-size interactive zero-knowledge proofs in the plain model without any setup.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. Unknown where it was published
Keywords
Non-interactive zero-knowledge proofsfully homomorphic encryption
Contact author(s)
j groth @ ucl ac uk
History
2011-01-08: received
Short URL
https://ia.cr/2011/012
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2011/012,
      author = {Jens Groth},
      title = {Minimizing Non-interactive Zero-Knowledge Proofs Using Fully Homomorphic Encryption},
      howpublished = {Cryptology ePrint Archive, Paper 2011/012},
      year = {2011},
      note = {\url{https://eprint.iacr.org/2011/012}},
      url = {https://eprint.iacr.org/2011/012}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.