Homomorphic Encryption - Shai Halevi

1 Homomorphic EncryptionShai Halevi (IBM Research)April 2017 AbstractFully Homomorphic Encryption (FHE) has been called the Swiss Army knife of cryptog-raphy , since it provides a single tool that can be uniformly applied to many cryptographicapplications. In this tutorial we study FHE and describe its different properties, relations withother concepts in cryptography, and constructions. We briefly discuss the three generations ofFHE constructions since Gentry s breakthrough result in 2009, and cover in detail the third-generation scheme of Gentry, Sahai, and Waters (GSW).

2 Tutorial was written in honor of Oded Goldreichs 60th birthday, and waspublished (with minor changes) as part of the book Tutorials on the Foundations of Cryptography ,edited by Yehuda Lindell [67]. I owe special thanks to Yehuda for the initiative to write drew on many sources for this tutorial, most extensively on Craig Gentry s PhD thesis [37], asurvey by Vinod Vaikuntanathan [88], and a blog by Boaz Barak and Zvika Brakerski [6]. I wouldlike to thank Craig Gentry for teaching me most of what I know about FHE. I also thank the manyother people with whom I collaborated on work in this Computing on Encrypted Applications of Homomorphic Encryption .

3 Beyond Homomorphic Encryption .. Abridged History .. Generations of FHE .. Organization of This Tutorial ..72 Defining Homomorphic Notations and Basic Definitions .. Encryption .. Homomorphic Encryption .. Properties of Homomorphic Encryption Schemes .. Homomorphism .. Privacy .. Private Homomorphic Encryption Versus Two-Message SFE .. hop Homomorphic Encryption .. Secret-Key to Public-Key Homomorphic Encryption .. 163 Realizing Leveled Homomorphic Tools .. with Errors (LWE).

4 Encryption from LWE .. Flattening Gadget .. and Key Switching .. The GSW Encryption Scheme .. Try .. Try .. Try .. GSW Leveled Scheme .. 254 Realizing Fully Homomorphic Bootstrapping .. Homomorphic Encryption .. The GSW Scheme Is Bootstrappable .. Complexity .. Homomorphic Encryption Under Polynomial DLWE .. Realizing Strong Homomorphism .. 345 Advanced Faster Homomorphic Encryption .. Other Attempts at Realizing Homomorphic Encryption .

5 Hidden-Ideal Paradigm .. Encryption from Binary Codes .. Encryption from Group Theory .. Homomorphic Encryption for Other Models of Computation .. Beyond Homomorphic Encryption .. Homomorphic Encryption .. Commitments and Signatures .. Encryption , Obfuscation, and Multilinear Maps .. 426 Suggested Reading431 Computing on Encrypted DataSecure multi party computation epitomizes the promise of cryptography, performing the seeminglyimpossible magic trick of processing data without having access to it.

6 One simple example featuresa client holding an inputxand a server holding a functionf, the client wishing to learnf(x) withoutgiving away information about its input. Similarly, the server may want to hide information aboutthe functionffrom the client (except, of course, the valuef(x)). This situation arises in manypractical scenarios, most notably in the context of secure cloud computing; For example, the clientmay want to get driving directions without revealing their location to the have devised multiple solutions to this problem over the last 40 years, butnone simpler (conceptually) than the paradigm ofcomputing on encrypted data.

7 This paradigmwas suggested by Rivest et al. [82] in the very early days of public-key cryptography, under thename privacy homomorphisms : The client simply encrypts its inputxand sends the ciphertextto the server, who can evaluate the functionfon the encrypted input . The server returns theevaluated ciphertext to the client, who decrypts it and recovers the result. Of course, it takesa special Encryption method to allow such processing of encrypted data; for example, Rivest etal. observed in [82] that raw RSA (wherexis encrypted asxemodN) enables multiplicationof encrypted values.

8 They asked whether it was possible to compute more general functions onencrypted data, and what one can do with an Encryption scheme that enables such [82], Encryption schemes that support computation on encrypted data came to beknown ashomomorphic Encryption (HE). In addition to the usual Encryption and decryption pro-cedures, these schemes have anevaluation procedurethat takes ciphertexts encryptingxand adescription of a functionf, and returns an evaluated ciphertext that can be decrypted to obtainthe valuef(x).

9 A salient non triviality property of such scheme iscompactness, requiring thatthe complexity of decrypting an evaluated ciphertext does not depend on the functionfthat wasused in the evaluation. Another desirable security property isfunction-privacy, requiring that theevaluated ciphertext does not reveal the functionf, even to the owner of the secret cryptosystems that support computation ofsomefunctions on encrypted data have beenproposed over the years, but it seemed much harder to construct a compactfully homomorphicencryption(FHE), namely a compact scheme that can evaluateall(efficient) functions.

10 It was notuntil 2009 that the watershed work of Gentry [38] established for the first time a blueprint for con-structing such schemes and described a viable candidate. That work was followed by a sequence ofrapid advancements, resulting in much more efficient FHE schemes under well established hardnessassumptions, and better understanding of the relations between FHE and other branches of securecomputation. The goal of this tutorial is to present an overview of that line of paradox and its ability to compute on encrypted data may seem para-doxical at first glance.