logo资料库

完全同态加密.pdf

发布时间：2022-06-26 发布人：admin 分类：说明书 资料大小：0.91M 资料格式：pdf 举报 版权申诉
第1页 / 共209页
第2页 / 共209页
第3页 / 共209页
第4页 / 共209页
第5页 / 共209页
第6页 / 共209页
第7页 / 共209页
第8页 / 共209页
资料共209页，剩余部分请下载后查看
    A FULLY HOMOMORPHIC ENCRYPTION SCHEME A DISSERTATION SUBMITTED TO THE DEPARTMENT OF COMPUTER SCIENCE AND THE COMMITTEE ON GRADUATE STUDIES OF STANFORD UNIVERSITY IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF DOCTOR OF PHILOSOPHY Craig Gentry September 2009
    c Copyright by Craig Gentry 2009 All Rights Reserved ii
    I certify that I have read this dissertation and that, in my opinion, it is fully adequate in scope and quality as a dissertation for the degree of Doctor of Philosophy. (Dan Boneh) Principal Adviser I certify that I have read this dissertation and that, in my opinion, it is fully adequate in scope and quality as a dissertation for the degree of Doctor of Philosophy. (John Mitchell) I certify that I have read this dissertation and that, in my opinion, it is fully adequate in scope and quality as a dissertation for the degree of Doctor of Philosophy. (Serge Plotkin) Approved for the University Committee on Graduate Studies. iii
    Abstract We propose the first fully homomorphic encryption scheme, solving a central open problem in cryptography. Such a scheme allows one to compute arbitrary functions over encrypted data without the decryption key – i.e., given encryptions E(m1), . . . , E(mt) of m1, . . . , mt, one can efficiently compute a compact ciphertext that encrypts f(m1, . . . , mt) for any effi- ciently computable function f. This problem was posed by Rivest et al. in 1978. Fully homomorphic encryption has numerous applications. For example, it enables private queries to a search engine – the user submits an encrypted query and the search engine computes a succinct encrypted answer without ever looking at the query in the clear. It also enables searching on encrypted data – a user stores encrypted files on a remote 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 own. More broadly, fully homomorphic encryption improves the efficiency of secure multiparty computation. Our construction begins with a somewhat homomorphic “boostrappable” encryption scheme that works when the function f is the scheme’s own decryption function. We then show how, through recursive self-embedding, bootstrappable encryption gives fully homo- morphic encryption. The construction makes use of hard problems on ideal lattices. iv
    Acknowledgments This 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 his amazing intelligence, infinite energy, boundless optimism, and genuine friendliness. I wish I could incorporate more of his qualities. I have limited optimism about my chances. In a presentation to my fellow Ph.D. admits four years ago, Dan highlighted fully homo- morphic encryption as an interesting open problem and guaranteed an immediate diploma to anyone who solved it. Perhaps I took him too literally. He certainly neglected to mention how much writing would be involved. But I have never gone wrong following his advice. I have also received a lot of input and support from my friends in the IBM Crypto Group, where I’ve interned for the past couple of summers, and where I will be working permanently – namely, Ran Canetti (now at Tel Aviv University), Rosario Gennaro, Shai Halevi, Charanjit Jutla, Hugo Krawczyk, Tal Rabin, and Vinod Vaikuntanathan (postdoc). These discussions have led to significant performance optimizations. Also, Tal Rabin has been particularly helpful in terms of optimizing my own performance, so that I could finally finish the thesis. I have had helpful discussions and received comments and suggestions from many other people, 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, Amit Sahai, Adam Smith, Salil Vadhan, and Brent Waters. This work was supported by the NSF, a Stanford Graduate Fellowship and an IBM PhD fellowship. v
    Contents Abstract Acknowledgments 1 Introduction 1.1 A Very Brief and Informal Overview of Our Construction . . . . . . . . . . 1.2 What is Fully Homomorphic Encryption? . . . . . . . . . . . . . . . . . . . 1.3 Bootstrapping a Scheme that Can Evaluate its Own Decryption Circuit . . 1.4 Ideal Lattices: Ideally Suited to Construct Bootstrappable Encryption . . . 1.5 Squashing the Decryption Circuit: The Encrypter Starts Decryption! . . . . 1.6 Security . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.7 Performance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.8 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 Definitions related to Homomorphic Encryption 2.1 Basic Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Computational Security Definitions . . . . . . . . . . . . . . . . . . . . . . . 3 Previous Homomorphic Encryption Schemes 4 Bootstrappable Encryption iv v 1 2 5 7 10 15 18 20 21 27 27 31 34 43 4.1 Leveled Fully Homomorphic Encryption from Bootstrappable Encryption, Generically 43 4.2 Correctness, Computational Complexity and Security of the Generic Construction 48 4.3 Fully Homomorphic Encryption from KDM-Secure Bootstrappable Encryption 51 4.4 Fully Homomorphic Encryption from Bootstrappable Encryption in the Random Oracle Model 53 vi
    5 An Abstract Scheme Based on the Ideal Coset Problem 5.1 The Ideal Coset Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 An Abstract Scheme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.3 Security of the Abstract Scheme . . . . . . . . . . . . . . . . . . . . . . . . 6 Background on Ideal Lattices I: The Basics 6.1 Basic Background on Lattices . . . . . . . . . . . . . . . . . . . . . . . . . . 6.2 Basic Background on Ideal Lattices . . . . . . . . . . . . . . . . . . . . . . . 6.3 Probability Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 58 59 62 63 63 65 68 7 A Somewhat Homomorphic Encryption Scheme 7.1 Why Lattices? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.2 Why Ideal Lattices? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.3 A Geometric Approach to Maximizing the Circuit Depth that Can Be Evaluated 70 Instantiating the Ring: The Geometry of Polynomial Rings . . . . . . . . . 7.4 Instantiating Encrypt and Minimizing rEnc . . . . . . . . . . . . . . . . . . . 7.5 7.6 Instantiating Decrypt and Maximizing rDec . . . . . . . . . . . . . . . . . . . 7.7 Security of the Concrete Scheme . . . . . . . . . . . . . . . . . . . . . . . . 7.8 How Useful is the Somewhat Homomorphic Scheme By Itself? . . . . . . . . 72 75 75 77 79 69 69 70 81 82 85 86 8 Tweaks to the Somewhat Homomorphic Scheme 8.1 On the Relationship between the Dual and the Inverse of an Ideal Lattice . 8.2 Transference Lemmas for Ideal Lattices . . . . . . . . . . . . . . . . . . . . 8.3 Tweaking the Decryption Equation . . . . . . . . . . . . . . . . . . . . . . . 8.4 A Tweak to Reduce the Circuit Complexity of the Rounding Step in Decryption 88 9 Decryption Complexity of the Tweaked Scheme 90 10 Squashing the Decryption Circuit 98 98 10.1 A Generic Description of the Transformation . . . . . . . . . . . . . . . . . 100 10.2 How to Squash, Concretely . . . . . . . . . . . . . . . . . . . . . . . . . . . 10.3 Bootstrapping Achieved: The Decryption Circuit for the Transformed System 102 11 Security 11.1 Regarding the Hint Given in Our “Squashing” Transformation . . . . . . . 104 104 vii
    11.2 Counterbalancing Assumptions . . . . . . . . . . . . . . . . . . . . . . . . . 113 12 Performance and Optimizations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12.1 Simple Optimizations 12.2 Basic Performance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12.3 More Optimizations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 Background on Ideal Lattices II 13.1 Overview of Gaussian Distributions over Lattices . . . . . . . . . . . . . . . 13.2 The Smoothing Parameter . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13.3 Sampling a Lattice According to a Gaussian Distribution . . . . . . . . . . 13.4 Ideal Factorization in Polynomial Rings . . . . . . . . . . . . . . . . . . . . 115 116 117 117 125 125 126 128 129 14 The Somewhat Homomorphic Scheme Revisited 14.1 Using Gaussian Sampling in Encrypt . . . . . . . . . . . . . . . . . . . . . . 14.2 Generating an Ideal with Very Small Norm . . . . . . . . . . . . . . . . . . 14.3 Proof of Security Based on the Inner Ideal Membership Problem (IIMP) . . 14.4 Success Amplification: Proof of Security Based on the Modified IIMP (MIIMP)136 14.5 Basing Security on a Search Problem: Bounded Distance Decoding Via Hensel Lifting138 14.6 Toward Reducing the SIVP to the BDDP: Regev’s Quantum Reduction . . 14.7 Summary of Security Results for this Construction So Far . . . . . . . . . . 14.8 Looking Forward . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141 143 143 132 132 133 135 15 Background on Ideal Lattices III . . . . . . . . . . . . . . 15.1 Lemmata Regarding Vectors Nearly Parallel to e1 15.2 Distribution of Prime Ideals . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 Random Self-Reduction of Ideal Lattice Problems 16.1 A New Type of Worst-Case / Average-Case Connection for Lattices . . . . 16.2 Our Average-Case Distribution . . . . . . . . . . . . . . . . . . . . . . . . . 16.3 How to “Randomize” a Worst-Case Ideal . . . . . . . . . . . . . . . . . . . 16.4 Why Does the Reduction Require a Factoring Oracle? . . . . . . . . . . . . 16.5 Application to our Fully Homomorphic Encryption Scheme . . . . . . . . . 145 145 148 151 151 153 154 157 159 viii
    分享到：
    赞 收藏

    相关推荐

    资料库

    安全技术

    共收录1285份资料，累计4个分类，关注成员有19位，主要包括：网络攻防,系统安全,其它,网络安全

    热门标签

    网络攻防 系统安全 其它 网络安全

    最新资料