UCL Discovery
UCL home » Library Services » Electronic resources » UCL Discovery

Using Fully Homomorphic Hybrid Encryption to Minimize Non-interative Zero-Knowledge Proofs

Gentry, C; Groth, J; Ishai, Y; Peikert, C; Sahai, A; Smith, A; (2015) Using Fully Homomorphic Hybrid Encryption to Minimize Non-interative Zero-Knowledge Proofs. Journal of Cryptology , 28 (4) pp. 820-843. 10.1007/s00145-014-9184-y. Green open access

[thumbnail of Groth_FHENIZK8(3).pdf]
Preview
Text
Groth_FHENIZK8(3).pdf - Accepted Version

Download (356kB) | Preview

Abstract

A non-interactive zero-knowledge (NIZK) proof can be used to demonstrate the truth of a statement without revealing anything else. It has been shown under standard cryptographic assumptions that NIZK proofs of membership exist for all languages in NP. While there is evidence that such proofs cannot be much shorter than the corresponding membership witnesses, all known NIZK proofs for NP languages are considerably longer than the witnesses. Soon after Gentry’s construction of fully homomorphic encryption, several groups independently contemplated the use of hybrid encryption to optimize the size of NIZK proofs and discussed this idea within the cryptographic community. This article formally explores this idea of using fully homomorphic hybrid encryption to optimize NIZK proofs and other related cryptographic primitives. We investigate the question of minimizing the communication overhead of NIZK proofs for NP and show that if fully homomorphic encryption exists then it is possible to get proofs that are roughly of the same size as the witnesses. Our technique consists in constructing a fully homomorphic hybrid encryption scheme with ciphertext size |m|+poly(k), where m is the plaintext and k is the security parameter. Encrypting the witness for an NP-statement allows us to evaluate the NP-relation in a communication-efficient manner. We apply this technique 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 or to minimize the communication in secure computation protocols.

Type: Article
Title: Using Fully Homomorphic Hybrid Encryption to Minimize Non-interative Zero-Knowledge Proofs
Open access status: An open access version is available from UCL Discovery
DOI: 10.1007/s00145-014-9184-y
Publisher version: http://dx.doi.org/10.1007/s00145-014-9184-y
Language: English
Additional information: The final publication is available at Springer via http://dx.doi.org/10.1007/s00145-014-9184-y.
Keywords: Non-interactive zero-knowledge proofs, Fully homomorphic encryption, Hybrid encryption, Secure function evaluation, Minimizing communication.
UCL classification: UCL
UCL > Provost and Vice Provost Offices > UCL BEAMS
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Computer Science
URI: https://discovery.ucl.ac.uk/id/eprint/1474844
Downloads since deposit
350Downloads
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item