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.

2 (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. 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.

3 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.

4 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.

5 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).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.

6 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!.. 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.

7 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?.. 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.

8 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.. Counterbalancing Assumptions.. 11312 Performance and Simple Optimizations.. Basic Performance.. More Optimizations.. 11713 Background on Ideal Lattices Overview of Gaussian Distributions over Lattices.

9 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.

10 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.