实例介绍
【实例简介】
同态加密是最近比较流行的加密算法，本文为完全同态加密算法，英文版，经典，
I certify that I have read this dissertation and that, in my opinion, it is fully adequate in scope anld qualily 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 Plotki Approved for the University Committee on Graduate Studies abstract We propose the first fully homomorphic encryption scheme, solving a central open problem in cryptography. Such a schcmc allows onc to compute arbitrary functions ovcr 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(mI,., 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 coinpules 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 filc server and can latcr have the server rctricve 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-ernbedding, bootstrappable encry pion gives fully horno- morphic encryption. The construction makes use of hard problems on ideal lattices Acknowledgments This thesis would have been impossible without the support and mentoring of my advisor Dan Bonch. Even after sevcral ycars of working with him, I am constantly surprised by his amazing intelligence, infinite energy, boundless optimism, and genuine friendliness. I wisk 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. Bul i have lever gone wrong following his advice I have also received a lot of input and support from my friends in the IBM Crypto Group, wherc Ivc interned for the past couple of summers, and wherc 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 Iron any 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 WS 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 10 1.5 Squashing the Decryption Circuit: The Encrypter Starts Decryption! 5 1.6 Security 18 1.7 Performance 20 8 Applications 21 2 Definitions related to Homomorp hic Encryptic 27 2.1 Basic definitions 27 2.2 Computational Security Definitions 3 Previous Homomorphic Encryption Schemes 34 4 Bootstrappable Encryption 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 5 An abstract scheme based on the ideal coset problem 57 5.1 The Ideal Coset Problem 5.2 Al Abstract Scheme 59 5.3 Security of the abstract Scheme 62 6 Background on Ideal Lattices I: The Basics 63 6.1 Basic Background on Lattices 63 6.2 Basic Background on Ideal Lattices 65 6.3 Probability Background 7 A Somewhat Homomorphic Encryption Scheme 69 7.1 Why Lattices? 69 7.2 Why Ideal lattices? 70 7.3 A Geometric Approach to Maximizing the Circuit Depth that Can Be Evaluated 70 7.4 Instantiating the Ring: The Geometry of Polynoimial Rings 7.5 Instantiating Encrypt and Minimizing rEnc 7.6 Instantiating Decrypt and maximizing rdec 75 7.7 Security of the Concrete Scheme 77 7.8 How Useful is the Somewhat Homomorphic Scheme By Itself? 79 8 Tweaks to the Somewhat Homomorphic scheme 81 8.1 On the Relationship between the Dual and the Inverse of an Ideal Lattice. 82 8.2 Transference Lemmas for Ideal lattices 85 8.3 Tweaking the Decryption equation 86 8.1 A Tweak to Reduce the Circuit Complexity of the Rounding Step in Decryption 9 Decryption Complexity of the T weaked Scheme 90 10 Squashing the Decryption Circuit 98 10.1 A Generic Description of the Transformation Q 10.2 How to Squash, Concretely 100 10.3 Bootstrapping Achieved: The Decryption Circuit for the Transformed System 102 11 Security 104 11.1 Regarding the Hint Given in Our "Squashing?" Transformation .104 11.2 Counterbalancing Assumptions 12 Performance and optimizations 115 12. 1 Simple optimizations 116 12.2 Basic Performance 117 12.3 More Optimizations 117 13 Background on Ideal Lattices II 125 13.1 Ovcrvicw of Gaussian Distributions ovcr Lattices 125 13.2 The Smoothing Parameter 126 13.3 Sampling a Lattice According to a gaussian Distribution ..,.128 13.4 Ideal Factorization in Polynomial rings 129 14 The Somewhat Homomorphic Scheme Revisited 132 14.1 Using Gaussian Sampling in Encrypt 132 14.2 Generating an Ideal with Very Small norm 133 14.3 Proof of Security Based on the Inner Ideal Membership Problem(IIMP).. 135 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 Lifting 138 14.6 Toward Reducing the SIVP to the BDDP: Regev's Quantum Reduction 141 14.7 Sunnary of Security Results for this Construction So far ,,143 14.8 Looking Forward 143 15 Background on Ideal Lattices III 145 15.1 Lemmata Regarding Vectors Nearly Parallel to e1 145 15.2 Distribution of prime ideals 148 16 Random self-Reduction of ideal lattice Problems 151 16.1 A New Type of Worst-Case/ Average-Case Connection for Lattices 151 16.2 Our Average-Case Distribution 153 16.3 How to“ Randomize” a worst- Case ideal 154 16. 4 Why Does the Reduction Require a Factoring Ora acle 157 16.5 Applicalion lo our Fully Homomorphic Encryption Scheine 159 1 7 How to randomize a worst-Case ideal 161 17.1 The Randomizeldeal algorithm 161 17.2 Is the ideal randon? The Proof of Theorem 16.3.4 17.3 Reduction of WBddp to HBdDp and worst-case ivip to Average-Case IVIP164 17.4 An Alternative Way to Randomize an Ideal 166 18 Key Gen per the Average Case Distribution 175 18.1 The Secret Key 175 18.2 Adapling Kalais Algorithm to Generate a Randoin Factored Idea. .177 19 Basing Security on Worst-case SIVP in Ideal Lattices 181 19.1 Relationship Among Instances of IVIP 182 19.2 Reduction of sivp to IVip .183 20 Circuit Privacy 188 Bibliography 190 List of tables 【实例截图】
【核心代码】
同态加密是最近比较流行的加密算法，本文为完全同态加密算法，英文版，经典，
I certify that I have read this dissertation and that, in my opinion, it is fully adequate in scope anld qualily 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 Plotki Approved for the University Committee on Graduate Studies abstract We propose the first fully homomorphic encryption scheme, solving a central open problem in cryptography. Such a schcmc allows onc to compute arbitrary functions ovcr 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(mI,., 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 coinpules 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 filc server and can latcr have the server rctricve 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-ernbedding, bootstrappable encry pion gives fully horno- morphic encryption. The construction makes use of hard problems on ideal lattices Acknowledgments This thesis would have been impossible without the support and mentoring of my advisor Dan Bonch. Even after sevcral ycars of working with him, I am constantly surprised by his amazing intelligence, infinite energy, boundless optimism, and genuine friendliness. I wisk 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. Bul i have lever gone wrong following his advice I have also received a lot of input and support from my friends in the IBM Crypto Group, wherc Ivc interned for the past couple of summers, and wherc 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 Iron any 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 WS 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 10 1.5 Squashing the Decryption Circuit: The Encrypter Starts Decryption! 5 1.6 Security 18 1.7 Performance 20 8 Applications 21 2 Definitions related to Homomorp hic Encryptic 27 2.1 Basic definitions 27 2.2 Computational Security Definitions 3 Previous Homomorphic Encryption Schemes 34 4 Bootstrappable Encryption 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 5 An abstract scheme based on the ideal coset problem 57 5.1 The Ideal Coset Problem 5.2 Al Abstract Scheme 59 5.3 Security of the abstract Scheme 62 6 Background on Ideal Lattices I: The Basics 63 6.1 Basic Background on Lattices 63 6.2 Basic Background on Ideal Lattices 65 6.3 Probability Background 7 A Somewhat Homomorphic Encryption Scheme 69 7.1 Why Lattices? 69 7.2 Why Ideal lattices? 70 7.3 A Geometric Approach to Maximizing the Circuit Depth that Can Be Evaluated 70 7.4 Instantiating the Ring: The Geometry of Polynoimial Rings 7.5 Instantiating Encrypt and Minimizing rEnc 7.6 Instantiating Decrypt and maximizing rdec 75 7.7 Security of the Concrete Scheme 77 7.8 How Useful is the Somewhat Homomorphic Scheme By Itself? 79 8 Tweaks to the Somewhat Homomorphic scheme 81 8.1 On the Relationship between the Dual and the Inverse of an Ideal Lattice. 82 8.2 Transference Lemmas for Ideal lattices 85 8.3 Tweaking the Decryption equation 86 8.1 A Tweak to Reduce the Circuit Complexity of the Rounding Step in Decryption 9 Decryption Complexity of the T weaked Scheme 90 10 Squashing the Decryption Circuit 98 10.1 A Generic Description of the Transformation Q 10.2 How to Squash, Concretely 100 10.3 Bootstrapping Achieved: The Decryption Circuit for the Transformed System 102 11 Security 104 11.1 Regarding the Hint Given in Our "Squashing?" Transformation .104 11.2 Counterbalancing Assumptions 12 Performance and optimizations 115 12. 1 Simple optimizations 116 12.2 Basic Performance 117 12.3 More Optimizations 117 13 Background on Ideal Lattices II 125 13.1 Ovcrvicw of Gaussian Distributions ovcr Lattices 125 13.2 The Smoothing Parameter 126 13.3 Sampling a Lattice According to a gaussian Distribution ..,.128 13.4 Ideal Factorization in Polynomial rings 129 14 The Somewhat Homomorphic Scheme Revisited 132 14.1 Using Gaussian Sampling in Encrypt 132 14.2 Generating an Ideal with Very Small norm 133 14.3 Proof of Security Based on the Inner Ideal Membership Problem(IIMP).. 135 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 Lifting 138 14.6 Toward Reducing the SIVP to the BDDP: Regev's Quantum Reduction 141 14.7 Sunnary of Security Results for this Construction So far ,,143 14.8 Looking Forward 143 15 Background on Ideal Lattices III 145 15.1 Lemmata Regarding Vectors Nearly Parallel to e1 145 15.2 Distribution of prime ideals 148 16 Random self-Reduction of ideal lattice Problems 151 16.1 A New Type of Worst-Case/ Average-Case Connection for Lattices 151 16.2 Our Average-Case Distribution 153 16.3 How to“ Randomize” a worst- Case ideal 154 16. 4 Why Does the Reduction Require a Factoring Ora acle 157 16.5 Applicalion lo our Fully Homomorphic Encryption Scheine 159 1 7 How to randomize a worst-Case ideal 161 17.1 The Randomizeldeal algorithm 161 17.2 Is the ideal randon? The Proof of Theorem 16.3.4 17.3 Reduction of WBddp to HBdDp and worst-case ivip to Average-Case IVIP164 17.4 An Alternative Way to Randomize an Ideal 166 18 Key Gen per the Average Case Distribution 175 18.1 The Secret Key 175 18.2 Adapling Kalais Algorithm to Generate a Randoin Factored Idea. .177 19 Basing Security on Worst-case SIVP in Ideal Lattices 181 19.1 Relationship Among Instances of IVIP 182 19.2 Reduction of sivp to IVip .183 20 Circuit Privacy 188 Bibliography 190 List of tables 【实例截图】
【核心代码】
标签：
好例子网口号：伸出你的我的手 — 分享！
小贴士
感谢您为本站写下的评论，您的评论对其它用户来说具有重要的参考价值，所以请认真填写。
- 类似“顶”、“沙发”之类没有营养的文字，对勤劳贡献的楼主来说是令人沮丧的反馈信息。
- 相信您也不想看到一排文字/表情墙，所以请不要反馈意义不大的重复字符，也请尽量不要纯表情的回复。
- 提问之前请再仔细看一遍楼主的说明，或许是您遗漏了。
- 请勿到处挖坑绊人、招贴广告。既占空间让人厌烦，又没人会搭理，于人于己都无利。
关于好例子网
本站旨在为广大IT学习爱好者提供一个非营利性互相学习交流分享平台。本站所有资源都可以被免费获取学习研究。本站资源来自网友分享，对搜索内容的合法性不具有预见性、识别性、控制性，仅供学习研究，请务必在下载后24小时内给予删除，不得用于其他任何用途，否则后果自负。基于互联网的特殊性，平台无法对用户传输的作品、信息、内容的权属或合法性、安全性、合规性、真实性、科学性、完整权、有效性等进行实质审查；无论平台是否已进行审查，用户均应自行承担因其传输的作品、信息、内容而可能或已经产生的侵权或权属纠纷等法律责任。本站所有资源不代表本站的观点或立场，基于网友分享，根据中国法律《信息网络传播权保护条例》第二十二与二十三条之规定，若资源存在侵权或相关问题请联系本站客服人员，点此联系我们。关于更多版权及免责申明参见 版权及免责申明
网友评论
我要评论