On Zero-Testable Homomorphic Encryption and Publicly Verifiable Non-interactive Arguments
We define and study zero-testable homomorphic encryption (ZTHE) – a semantically secure, somewhat homomorphic encryption scheme equipped with a weak zero test that can identify trivial zeros. These are ciphertexts that result from homomorphically evaluati
- PDF / 419,592 Bytes
- 33 Pages / 439.37 x 666.142 pts Page_size
- 75 Downloads / 164 Views
2
MIT, Cambridge, USA [email protected] Weizmann Institute of Science, Rehovot, Israel
Abstract. We define and study zero-testable homomorphic encryption (ZTHE) – a semantically secure, somewhat homomorphic encryption scheme equipped with a weak zero test that can identify trivial zeros. These are ciphertexts that result from homomorphically evaluating an arithmetic circuit computing the zero polynomial over the integers. This is a relaxation of the (strong) zero test provided by the notion of graded encodings, which identifies all encodings of zero. We show that ZTHE can suffice for powerful applications. Based on any ZTHE scheme that satisfies the additional properties of correctness on adversarial ciphertexts and multi-key homomorphism, we construct publicly verifiable non-interactive arguments for delegating computation. Such arguments were previously constructed from indistinguishability obfuscation or based on so-called knowledge assumptions. The arguments we construct are adaptively sound, based on an efficiently falsifiable assumption, and only make black-box use of the underlying cryptographic primitives. We also show that a ZTHE scheme that is sufficient for our application can be constructed based on an efficiently-falsifiable assumption over so-called “clean” graded encodings.
1
Introduction
Recent breakthroughs in the study of fully homomorphic encryption [Gen09] and program obfuscation [GGH+13b] have revolutionized the foundations of cryptography. Fully homomorphic encryption (FHE) allows arbitrary polynomialtime computations to be performed “homomorphically” on encrypted data, while This work subsumes an earlier report posted on the Cryptology ePrint Archive [PR14]. The current version features new results and addresses correctness issues with the earlier report. O. Paneth—Research supported in part by NSF Grants CNS-1350619, CNS-1414119 and CNS-1413920, by the Defense Advanced Research Projects Agency (DARPA) and the U.S. Army Research Office under contracts W911NF-15-C-0226 and W911NF-15C-0236 and by Simons Investigator Award Agreement Dated 6-5-12. c International Association for Cryptologic Research 2017 Y. Kalai and L. Reyzin (Eds.): TCC 2017, Part II, LNCS 10678, pp. 283–315, 2017. https://doi.org/10.1007/978-3-319-70503-3_9
284
O. Paneth and G.N. Rothblum
ensuring that semantic security is maintained and nothing about the data can be learned. While this powerful security guarantee enables important applications, other scenarios require more fine-grained control: allowing some information about the data to be exposed, while other information remains hidden. Multilinear maps [BS02] and graded encodings [GGH13a] are basic building blocks that have proven to be incredibly useful in such scenarios. Intuitively, a graded encoding scheme is a somewhat homomorphic encryption, supporting homomorphic evaluation of low-degree algebraic computations, with an additional capability: an efficient zero test procedure that publicly identifies encodings of zero. Graded encodings cannot be semantically secure: the zero te
Data Loading...
