caa a22 4500 60614885X CHVBK 20210128100531.0 cr unu---uuuuu 210128e20151001xx s 000 0 eng 10.1007/s00145-014-9184-y doi (NATIONALLICENCE)springer-10.1007/s00145-014-9184-y Using Fully Homomorphic Hybrid Encryption to Minimize Non-interative Zero-Knowledge Proofs [Elektronische Daten] [Craig Gentry, Jens Groth, Yuval Ishai, Chris Peikert, Amit Sahai, Adam Smith] 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|+{\mathrm {poly}}(k)$$ | m | + poly ( k ) , where $$m$$ m is the plaintext and $$k$$ 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. International Association for Cryptologic Research, 2014 Non-interactive zero-knowledge proofs nationallicence Fully homomorphic encryption nationallicence Hybrid encryption nationallicence Secure function evaluation nationallicence Minimizing communication nationallicence Gentry Craig IBM T.J. Watson Research Center, Ossining, NY, USA aut Groth Jens University College London, London, UK aut Ishai Yuval Technion, Haifa, Israel aut Peikert Chris Georgia Institute of Technology, Atlanta, GA, USA aut Sahai Amit University of California Los Angeles, Los Angeles, CA, USA aut Smith Adam Pennsylvania State University, State College, PA, USA aut Journal of Cryptology Springer US; http://www.springer-ny.com 28/4(2015-10-01), 820-843 0933-2790 28:4<820 2015 28 145 https://doi.org/10.1007/s00145-014-9184-y text/html Onlinezugriff via DOI BK010053 XK010053 XK010000 Metadata rights reserved Springer special CC-BY-NC licence nationallicence 1 research-article jats NATIONALLICENCE NATIONALLICENCE NL-springer NATIONALLICENCE 856 40 https://doi.org/10.1007/s00145-014-9184-y text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Gentry Craig IBM T.J. Watson Research Center, Ossining, NY, USA aut NATIONALLICENCE 700 1- Groth Jens University College London, London, UK aut NATIONALLICENCE 700 1- Ishai Yuval Technion, Haifa, Israel aut NATIONALLICENCE 700 1- Peikert Chris Georgia Institute of Technology, Atlanta, GA, USA aut NATIONALLICENCE 700 1- Sahai Amit University of California Los Angeles, Los Angeles, CA, USA aut NATIONALLICENCE 700 1- Smith Adam Pennsylvania State University, State College, PA, USA aut NATIONALLICENCE 773 0- Journal of Cryptology Springer US; http://www.springer-ny.com 28/4(2015-10-01), 820-843 0933-2790 28:4<820 2015 28 145