A FULLY HOMOMORPHIC ENCRYPTION SCHEME A …

1 A FULLY HOMOMORPHIC ENCRYPTION SCHEMEA DISSERTATIONSUBMITTED TO THE DEPARTMENT OF COMPUTER SCIENCEAND THE COMMITTEE ON GRADUATE STUDIESOF STANFORD UNIVERSITYIN PARTIAL FULFILLMENT OF THE REQUIREMENTSFOR THE DEGREE OFDOCTOR OF PHILOSOPHYC raig GentrySeptember 2009c Copyright by Craig Gentry 2009 All Rights ReservediiI certify that I have read this dissertation and that, in my opinion, it is fullyadequate in scope and quality as a dissertation for the degree of Doctor ofPhilosophy.(Dan Boneh) Principal AdviserI certify that I have read this dissertation and that, in my opinion, it is fullyadequate in scope and quality as a dissertation for the degree of Doctor ofPhilosophy.(John Mitchell)I certify that I have read this dissertation and that, in my opinion, it is fullyadequate in scope and quality as a dissertation for the degree of Doctor ofPhilosophy.(Serge Plotkin)Approved for the University Committee on Graduate propose the first FULLY HOMOMORPHIC ENCRYPTION SCHEME , solving a central open problemin cryptography.

2 Such a SCHEME allows one to compute arbitrary functions over encrypteddata without the decryption key , given encryptionsE(m1), .. , E(mt) ofm1, .. , mt,one can efficiently compute a compact ciphertext that encryptsf(m1, .. , mt) for any effi-ciently computable functionf. This problem was posed by Rivest et al. in HOMOMORPHIC ENCRYPTION has numerous applications. For example, it enablesprivate queries to a search engine the user submits an encrypted query and the searchengine computes a succinct encrypted answer without ever looking at the query in theclear. It also enables searching on encrypted data a user stores encrypted files on aremote file server and can later have the server retrieve only files that (when decrypted)satisfy some boolean constraint, even though the server cannot decrypt the files on its broadly, FULLY HOMOMORPHIC ENCRYPTION improves the efficiency of secure construction begins with a somewhat HOMOMORPHIC boostrappable encryptionscheme that works when the functionfisthe SCHEME s own decryption function.

3 We thenshow how, through recursive self-embedding, bootstrappable ENCRYPTION gives FULLY homo-morphic ENCRYPTION . The construction makes use of hard problems on ideal thesis would have been impossible without the support and mentoring of my advisor,Dan Boneh. Even after several years of working with him, I am constantly surprised by hisamazing intelligence, infinite energy, boundless optimism, and genuine friendliness. I wishI could incorporate more of his qualities. I have limited optimism about my a presentation to my fellow admits four years ago, Dan highlighted FULLY homo-morphic ENCRYPTION as an interesting open problem and guaranteed an immediate diplomato anyone who solved it. Perhaps I took him too literally. He certainly neglected to mentionhow much writing would be involved. But I have never gone wrong following his have also received a lot of input and support from my friends in the IBM CryptoGroup, where I ve interned for the past couple of summers, and where I will be workingpermanently namely, Ran Canetti (now at Tel Aviv University), Rosario Gennaro, ShaiHalevi, Charanjit Jutla, Hugo Krawczyk, Tal Rabin, and Vinod Vaikuntanathan (postdoc).

4 These discussions have led to significant performance optimizations. Also, Tal Rabin hasbeen particularly helpful in terms of optimizing my own performance, so that I could finallyfinish the have had helpful discussions and received comments and suggestions from many otherpeople, including (non-exhaustively): Boaz Barak, Marten van Dijk, Shafi Goldwasser,Iftach Haitner, Michael Hamburg, Susan Hohenberger, Yuval Ishai, Yael Tauman Kalai,Vadim Lyubashevsky, Daniele Micciancio, Chris Peikert, Oded Regev, Alon Rosen, AmitSahai, Adam Smith, Salil Vadhan, and Brent work was supported by the NSF, a Stanford Graduate Fellowship and an IBM A Very Brief and Informal Overview of Our Construction.. What is FULLY HOMOMORPHIC ENCRYPTION ?.. Bootstrapping a SCHEME that Can Evaluate its Own Decryption Circuit.. Ideal Lattices: Ideally Suited to Construct Bootstrappable ENCRYPTION .. Squashing the Decryption Circuit: The Encrypter Starts Decryption!

5 Security.. Performance.. Applications.. 212 Definitions related to HOMOMORPHIC Basic Definitions.. Computational Security Definitions.. 313 Previous HOMOMORPHIC ENCRYPTION Schemes344 Bootstrappable Leveled FULLY HOMOMORPHIC ENCRYPTION from Bootstrappable ENCRYPTION , Correctness, Computational Complexity and Security of the Generic FULLY HOMOMORPHIC ENCRYPTION from KDM-Secure Bootstrappable FULLY HOMOMORPHIC ENCRYPTION from Bootstrappable ENCRYPTION in the Random Oracle Model53vi5 An Abstract SCHEME Based on the Ideal Coset The Ideal Coset Problem.. An Abstract SCHEME .. Security of the Abstract SCHEME .. 626 Background on Ideal Lattices I: The Basic Background on Lattices.. Basic Background on Ideal Lattices.. Probability Background.. 687 A Somewhat HOMOMORPHIC ENCRYPTION Why Lattices?.. WhyIdealLattices?

6 A Geometric Approach to Maximizing the Circuit Depth that Can Be Instantiating the Ring: The Geometry of Polynomial Rings.. InstantiatingEncryptand MinimizingrEnc.. InstantiatingDecryptand MaximizingrDec.. Security of the Concrete SCHEME .. How Useful is the Somewhat HOMOMORPHIC SCHEME By Itself?.. 798 Tweaks to the Somewhat HOMOMORPHIC On the Relationship between the Dual and the Inverse of an Ideal Lattice. Transference Lemmas for Ideal Lattices.. Tweaking the Decryption Equation.. A Tweak to Reduce the Circuit Complexity of the Rounding Step in Decryption889 Decryption Complexity of the Tweaked Scheme9010 Squashing the Decryption A Generic Description of the Transformation.. How to Squash, Concretely.. Bootstrapping Achieved: The Decryption Circuit for the Transformed System10211 Regarding the Hint Given in Our Squashing Transformation.

7 Counterbalancing Assumptions.. 11312 Performance and Simple Optimizations.. Basic Performance.. More Optimizations.. 11713 Background on Ideal Lattices Overview of Gaussian Distributions over Lattices.. The Smoothing Parameter.. Sampling a Lattice According to a Gaussian Distribution.. Ideal Factorization in Polynomial Rings.. 12914 The Somewhat HOMOMORPHIC SCHEME Using Gaussian Sampling inEncrypt.. Generating an Ideal with Very Small Norm.. Proof of Security Based on the Inner Ideal Membership Problem (IIMP).. Success Amplification: Proof of Security Based on the Modified IIMP (MIIMP) Basing Security on a Search Problem: Bounded Distance Decoding Via Hensel Toward Reducing the SIVP to the BDDP: Regev s Quantum Reduction.. Summary of Security Results for this Construction So Far.. Looking Forward.. 14315 Background on Ideal Lattices Lemmata Regarding Vectors Nearly Parallel toe1.

8 Distribution of Prime Ideals.. 14816 Random Self-Reduction of Ideal Lattice A New Type of Worst-Case / Average-Case Connection for Lattices.. Our Average-Case Distribution.. How to Randomize a Worst-Case Ideal.. Why Does the Reduction Require a Factoring Oracle?.. Application to our FULLY HOMOMORPHIC ENCRYPTION SCHEME .. 159viii17 How to Randomize a Worst-Case TheRandomizeIdealAlgorithm.. Is the Ideal Random? The Proof of .. Reduction of WBDDP to HBDDP and Worst-case IVIP to Average-Case An Alternative Way to Randomize an Ideal.. 16618 KeyGenper the Average Case The Secret Key.. Adapting Kalai s Algorithm to Generate a Random Factored Ideal.. 17719 Basing Security on Worst-case SIVP in Ideal Relationship Among Instances of IVIP.. Reduction of SIVP to IVIP.. 18320 Circuit Privacy188 Bibliography190ixList of TablesxChapter 1 IntroductionWe propose a solution to the old open problem of constructing afully HOMOMORPHIC en-cryption SCHEME .

9 This notion, originally called aprivacy homomorphism, was introduced byRivest, Adleman and Dertouzous [120] shortly after the invention of RSA by Rivest, Shamir,and Adleman [121]. Basic RSA is a multiplicatively HOMOMORPHIC ENCRYPTION SCHEME ,given RSA public key pk = (N, e) and ciphertexts{ i eimodN}, one can efficientlycompute i i= ( i i)emodN, a ciphertext that encrypts the product of the originalplaintexts. One imagines that it was RSA s multiplicative homomorphism, an accidentalbut useful property, that led Rivest et al. [120] to ask a natural question: What can one dowith an ENCRYPTION SCHEME that isfullyhomomorphic: a schemeEwith an efficient algo-rithmEvaluateEthat, for any valid public key pk,anycircuitC(not just a circuit consistingof multiplication gates as in RSA), and any ciphertexts i EncryptE(pk, i), outputs EvaluateE(pk, C, 1, .. , t),a valid ENCRYPTION ofC( 1.)

10 , t) under pk? Their answer: one can arbitrarilycompute onencrypted data , one can process encrypted data (query it, write into it, do anythingto it that can be efficiently expressed as a circuit) without the decryption key. As anapplication, they suggested private data banks. A user can store its data on an untrustedserver in encrypted form. Later, it can send a query on the data to the server, whereupon theserver can express this query as a circuit to be applied to the data, and use theEvaluateEalgorithm to construct an encrypted response to the user s query, which the user thendecrypts. We obviously want the server s response here to be more concise than the trivial1 CHAPTER 1. INTRODUCTION2solution, in which the server just sends all of the encrypted data back to the user to processon its have accumulated a long assortment of killer applications for fullyhomomorphic ENCRYPTION since then.