本文为美国斯坦福大学（作者：CraigGentry）的博士论文，共209页。

我们提出了第一个完全同态加密方案，解决了密码学中的中心开放问题。这种方案允许在没有解密密钥的情况下，对加密数据计算任意函数，即给定m₁、…、m_t的加密分别为E(m₁)、…、E(m_t)，对于任何有效的可计算函数f，可以有效地计算加密f(m₁、…、m_t)的压缩密文。这个问题由Rivest等人在1978年提出。

完全同态加密有许多应用。例如，它允许搜索引擎上的私人查询——用户提交一个加密查询请求，搜索引擎计算出一个简洁的加密答案，而不必查看清晰的查询。它还支持对加密数据进行搜索——用户将加密文件存储在远程文件服务器上，以后可以让服务器仅检索（解密时）满足某些布尔约束的文件，即使服务器无法自行解密文件也是可行的。更广泛地说，完全同态加密提高了多方安全计算的效率。

我们的构造从一个类同态的“可增强”加密方案开始，该方案在函数f是当前自己的解密函数时适用。然后我们展示了如何通过递归的自嵌入，引导该方案提供完全同态加密。这种构造利用了理想框架上的难题。

We propose the first fully homomorphicencryption scheme, solving a central open problem in cryptography. Such ascheme allows one to compute arbitrary functions over encrypted data withoutthe 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 efficiently computable function f. This problem was posed byRivest et al. in 1978. Fully homomorphic encryption has numerous applications.For example, it enables private queries to a search engine – the user submitsan encrypted query and the search engine computes a succinct encrypted answerwithout ever looking at the query in the clear. It also enables searching onencrypted data – a user stores encrypted files on a remote file server and canlater have the server retrieve only files that (when decrypted) satisfy someboolean constraint, even though the server cannot decrypt the files on its own.More broadly, fully homomorphic encryption improves the efficiency of secure multipartycomputation. Our construction begins with a somewhat homomorphic“boostrappable” encryption scheme that works when the function f is thescheme’s own decryption function. We then show how, through recursiveself-embedding, bootstrappable encryption gives fully homomorphic encryption.The construction makes use of hard problems on ideal lattices.

1 引言

2 与同态加密相关的定义

3 现有的同态加密方案

4 可引导加密

5 基于理想陪集问题的抽象方案

6 理想Lattices I型背景知识：基础

7 类同态加密方案

8 类同态加密方案的改进

9 改进方案的解密复杂性

10 解密电路

11 安全性

12 性能与优化

13 理想Lattices II型背景知识

14 重温类同态方案

15 理想Lattices III型背景知识

16 理想Lattice问题的随机自约简

17 如何随机化最坏情况的理想条件

18 每个平均案例分布的KeyGen

19 基于理想Lattices中最坏情况SIVP的安全性

20 电路私密性问题

下载英文原文地址：

http://page2.dfpan.com/fs/al5c8j42c241f249166/ 

更多精彩文章请关注微信号：