百科问答小站 logo   百科问答小站
问题

同态加密的实现原理是什么？在实际中有何应用？

回答
同态加密的实现原理与实际应用

同态加密（Homomorphic Encryption，HE）是一种革命性的加密技术，它允许对密文进行计算，并将计算结果解密回明文，而无需先解密数据。这意味着我们可以在加密状态下对敏感数据进行处理，例如存储在云端的数据，而无需担心数据泄露。这在数据隐私和安全领域具有巨大的潜力。

一、 同态加密的实现原理

同态加密的实现原理并非单一技术，而是多种数学构造和算法的集合。其核心在于设计一种加密方案，使得对密文上的特定操作（例如加法或乘法）在解密后对应于对明文上的相同操作。根据支持的运算种类，同态加密可以分为以下几种类型：

1. 部分同态加密（Partially Homomorphic Encryption, PHE）:
只支持一种特定运算（加法或乘法）的同态性。
示例：
RSA 加密（乘法同态）:
加密： $c = m^e pmod{n}$ (其中 $m$ 是明文，$e$ 是公钥，$n$ 是模数)
乘法同态： $c_1 imes c_2 = (m_1^e pmod{n}) imes (m_2^e pmod{n}) = (m_1 m_2)^e pmod{n}$。对密文进行乘法运算，解密后得到的是明文的乘积。
缺点： 无法进行加法运算。
Paillier 加密（加法同态）:
加密： $c = g^m r^n pmod{n^2}$ (其中 $m$ 是明文，$g$ 是生成元，$r$ 是随机数，$n$ 是模数)
加法同态： $c_1 imes c_2 = (g^{m_1} r_1^n) imes (g^{m_2} r_2^n) pmod{n^2} = g^{m_1+m_2} (r_1 r_2)^n pmod{n^2}$。对密文进行乘法运算（在模 $n^2$ 下），解密后得到的是明文的和。
缺点： 无法进行乘法运算。

2. 近似同态加密（Somewhat Homomorphic Encryption, SHE）:
支持有限次数的加法和乘法运算。
当对密文进行运算时，会引入“噪声”项。噪声会随着运算次数的增加而累积。当噪声过大时，将无法正确解密。
为了克服噪声问题，SHE 方案允许用户在计算过程中定期执行“重线性化”或“引导”操作来减少噪声，但这会增加计算复杂度。

3. 完全同态加密（Fully Homomorphic Encryption, FHE）:
支持任意次数的加法和乘法运算，即能够执行任何可计算函数。
FHE 是同态加密的终极目标，因为它能够实现对任意加密数据的通用计算。
实现的关键突破： 2009年，Craig Gentry 首次提出了实现 FHE 的理论框架，基于格（Lattice）上的困难问题。Gentry 的方案通过一个称为“引导”（Bootstrapping）的技术来解决噪声累积问题。

FHE 的核心思想与关键技术

要理解 FHE，需要深入了解其背后的数学原理。目前主流的 FHE 方案主要基于以下几种格上的困难问题：

最近向量问题 (Closest Vector Problem, CVP)
最短向量问题 (Shortest Vector Problem, SVP)
学习误差问题 (Learning With Errors, LWE) / 学习带噪声的乘法（Learning With Rounding, LWR）

以基于 LWE 的 FHE 方案（如 TFHE, CKKS 等）为例，其基本原理可以概括为：

1. 密钥生成 (Key Generation):
生成一个秘密密钥 $s$（通常是一个小的向量或整数）。
基于秘密密钥 $s$，生成公开的公钥。公钥通常包含一系列具有特定结构的矩阵或多项式，例如 $A$ 和 $b = As + e pmod{q}$，其中 $e$ 是一个小的随机噪声向量，$q$ 是一个大的模数。

2. 加密 (Encryption):
将明文消息 $m$（通常编码为一个小整数或向量）与公钥结合进行加密。
一个典型的 LWE 加密过程可能如下：
选择随机的向量 $u$ 和小的噪声向量 $e_1, e_2$。
密文 $c = (c_1, c_2)$ 被计算为：
$c_1 = u^T A + e_1 pmod{q}$
$c_2 = u^T b + m + e_2 pmod{q}$
其中 $b = As + e$。
仔细观察 $c_2$，可以发现它大致为 $u^T(As+e) + m + e_2 = u^T A s + u^T e + m + e_2 pmod{q}$。如果我们将 $c_1$ 视为对 $u^T A$ 的一个近似（加上噪声 $e_1$），那么 $c_2$ 中就包含了 $c_1 cdot s + m + ext{噪声}$ 的形式。

3. 同态运算（例如加法）:
假设我们有两个加密消息 $c = (c_1, c_2)$ 和 $c' = (c'_1, c'_2)$。
对密文进行加法运算，结果是：
$c_{sum} = (c_1 + c'_1, c_2 + c'_2) pmod{q}$
解密 $c_{sum}$ 将得到 $(m + m') + ext{累积噪声}$。

4. 同态运算（例如乘法）:
对密文进行乘法运算更为复杂，会产生一个“二次项”和更多的噪声。一个简单的乘法可能产生一个三元组 $(c_1 c'_1, c_1 c'_2 + c_2 c'_1, c_2 c'_2)$。
为了在密文上进行多项运算，需要一种机制来“摊平”这些二次项和更高阶的项，并减少噪声。

5. 引导（Bootstrapping）:
当密文上的噪声累积到一定程度，无法正确解密时，就可以使用引导技术。
引导本质上是一个“解密操作”，但它在密文域上进行。我们使用一个特殊的多项式函数（通常被称为“自举函数”）来对加密的密文进行“解密”，但输出仍然是密文形式，只是噪声被重置到较低的水平。
例如，可以将一个加密的明文 $m$ 的密文 $c$ “解密”为一个新的密文 $c'$，使得 $c'$ 加密的是 $m$，但 $c'$ 的噪声比 $c$ 小得多。
引导是 FHE 实现的关键，但它也是计算量最大的操作之一，是当前 FHE 效率低下的主要原因。

不同的 FHE 方案在具体实现细节和性能上有所差异：

BGV (BrakerskiGentryVaikuntanathan) / BFV (BrakerskiFanVercauteren): 主要基于 LWE 问题，支持加法和乘法同态，通常在密文更新时进行重线性化。
CKKS (CheonKimKimSong): 主要基于 LWE 问题，但其设计目标是支持实数或复数的近似计算，通过“重缩放”操作来控制噪声，对机器学习等应用非常有用。它不是严格意义上的精确同态加密，但对于很多实际应用已经足够。
TFHE (Fully Homomorphic Encryption over the Torus): 基于带符号的 LWE 问题，利用“引导”技术进行高效的比特级别的操作（如比较、逻辑门），可以直接在加密数据上执行布尔电路，灵活性非常高。

二、 同态加密的实际应用

尽管同态加密在计算效率上仍有待提升，但其独特的隐私保护能力使其在众多领域展现出巨大的应用潜力：

1. 隐私保护的云服务:
场景： 用户可以将敏感数据（如医疗记录、财务信息、搜索历史）加密后上传到云服务器。云服务提供商可以在加密数据上进行计算（如数据分析、机器学习模型训练、搜索查询），而无需访问用户的原始数据。计算结果仍然是加密的，只有用户拥有私钥才能解密。
优势： 极大地增强了云服务的隐私性，解决了用户对数据泄露的担忧。

2. 安全的机器学习:
场景：
联邦学习中的模型训练: 在联邦学习中，数据分布在多个设备上，模型训练需要在不共享原始数据的情况下进行。同态加密可以加密模型参数或梯度，使得模型可以在加密状态下进行聚合和更新，进一步保护了用户数据的隐私。
隐私保留的预测服务: 用户可以将输入数据加密后发送给一个机器学习模型服务商，服务商在加密数据上进行预测，并将加密的预测结果返回给用户。
敏感数据集上的模型训练: 研究人员可以在不暴露数据集内容的情况下，在包含敏感信息的医疗、金融等数据集上训练模型。
优势： 能够在不牺牲数据隐私的前提下，实现分布式或本地化的机器学习。

3. 安全多方计算 (Secure MultiParty Computation, SMPC) 的补充:
场景： 安全多方计算允许多个参与方联合计算一个函数，而无需透露各自的输入。同态加密可以作为 SMPC 的一种实现技术，或与 SMPC 结合使用，例如，通过同态加密来保护中间计算结果。
优势： 增强了 SMPC 协议的安全性和隐私性。

4. 私有信息检索 (Private Information Retrieval, PIR):
场景： 用户可以加密一个搜索查询，然后发送给一个数据库服务器。服务器在加密的查询上执行搜索，并将加密的结果返回给用户。用户可以解密结果以获取所需信息，而服务器无法知道用户的具体查询内容。
优势： 保护用户搜索隐私，防止服务器记录用户的搜索行为。

5. 安全的金融服务:
场景：
加密投票: 用户可以加密自己的投票，然后将加密的选票提交给一个计票系统。计票系统可以在加密的选票上进行统计，而无需知道每个人的投票内容，从而确保计票过程的透明性和匿名性。
加密支付: 在进行支付时，可以将交易金额加密后传输，商家在加密金额上进行处理，而无需看到明文金额。
隐私计算在金融风控: 金融机构可以在不暴露客户个人信息和交易细节的情况下，对加密的客户数据进行风险评估。
优势： 提高金融交易的隐私性和安全性。

6. 医疗健康领域:
场景： 医疗机构可以将患者的病历、基因数据等敏感信息加密后存储或进行分析。研究人员可以在不直接接触患者隐私数据的情况下，对大量匿名化的加密数据进行流行病学研究或药物研发。
优势： 遵守严格的医疗数据隐私法规，同时促进医疗研究。

三、 同态加密的挑战与未来发展

尽管同态加密潜力巨大，但其大规模应用仍面临一些挑战：

计算效率: 目前的同态加密方案在计算速度上远不如明文计算，尤其是在执行复杂函数和 FHE 的引导操作时。
密文膨胀: 同态加密后的密文通常比明文大很多，这会增加存储和传输的成本。
技术复杂性: 同态加密的实现和使用需要专业的密码学知识，对开发者而言门槛较高。
标准化和生态系统: 缺乏统一的标准和成熟的开发工具链，限制了其在产业界的推广。

未来的发展方向包括：

更高效的同态加密算法: 不断研究和优化现有算法，或探索新的数学难题，以提高计算速度和降低密文膨胀。
硬件加速: 开发专门的硬件加速器来提升同态加密的性能。
更易用的开发工具和库: 提供更友好、更抽象的 API 和开发框架，降低开发者的使用难度。
实际场景的优化: 针对特定应用场景（如机器学习、数据库查询）进行算法和协议的定制化优化。

总而言之，同态加密是一项前沿的隐私保护技术，其核心原理是设计在密文上进行运算，解密后结果与明文运算一致的数学方案。虽然目前仍存在效率和易用性等方面的挑战，但随着技术的不断发展和成熟，同态加密必将在保护数据隐私和安全方面发挥越来越重要的作用。

网友意见

user avatar

谢邀。

在Asiancrypt 2015投稿日期之前，想最后回答一个知乎问题，后面要专心学术了哈。既然是半年来的最后一个问题，肯定要选一个合适的。知乎上面被邀请回答了这个问题，正好和我后面要做的研究相关，而且这个问题我自己也已经挖坑很久了。因此，这次算是来填坑了~在回答问题之前，给出一些温馨提示：

首先，同态加密特别适合在云计算（Cloud Computing）中得以应用。而知乎er们应该有好多Computer Science专业的同学，而这其中又有很多将致力于云计算的研究。因此，我的回答会尽量通俗易懂。大家各取所需，其乐融融嘛。当然了，比我水平再高的知乎er们我就没法呈现更棒的答案了，欢迎帮我补充，同时欢迎一起讨论一起研究。我分3个层次进行回答：

  1. 概览和基本概念。这一部分争取做到大家都能看的很明白，从而多多支持我们的研究，给funding啊！
  2. 定义、安全性和简单实例。这一部分呈现给有一点密码学基础，同时对代数学有一定基础的知乎er们。
  3. 安全假设和构造概览。这一部分呈现给致力于同态加密及其相关研究的知乎er们，做到抛砖引玉的作用。

其次，同态加密的安全模型、构造以及安全性证明，乃至安全性假设，都是密码学近10年提出的知识。因此现在市面上还没有相关的教材和比较权威的介绍。所以我的介绍主要来源于：（1）论文；（2）公开课，特别是Bar-Ilan University在2012年组织的Winter School；（3）我自己和导师的交流。我会给出全部资料的链接，有兴趣的知乎er们可以进行查阅，并进一步进行学习。

最后，一些感谢的话。

  • 感谢帮我画答案中插图的杨柳飔同学。她是我的小学同学，好朋友，也是邻居啦，现在在清华美院读研究生。考虑到我自己画图学术气息太浓，这次特意请她帮我画了插图，水平很高哦！
  • 感谢“知乎密码学交流群”的全体成员们。自群成立以来，大家一直在群里讨论各种密码学的问题。这个题我说想答，也得到了他们的大力支持。包括 @玄星， @钱宸， @秦飞， @Laughing man， @刘健， @edwardz 等。特别是 @edwardz 同学，现在正在研究Lattice-Based Cryptography，很厉害的！

==============================

一、 概览：同态加密的概念

同态加密（Homomorphic Encryption）是很久以前密码学界就提出来的一个Open Problem。早在1978年，Ron Rivest, Leonard Adleman, 以及Michael L. Dertouzos就以银行为应用背景提出了这个概念[RAD78]。对，你没有看错，Ron Rivest和Leonard Adleman分别就是著名的RSA算法中的R和A。至于中间的S，Adi Shamir，现在仍然在为密码学贡献新的工作。

什么是同态加密？

提出第一个构造出全同态加密（Fully Homomorphic Encryption）[Gen09]的Craig Gentry给出的直观定义最好：

A way to delegate processing of your data, without giving away access to it.

这是什么意思呢？一般的加密方案关注的都是数据存储安全。即，我要给其他人发个加密的东西，或者要在计算机或者其他服务器上存一个东西，我要对数据进行加密后在发送或者存储。没有密钥的用户，不可能从加密结果中得到有关原始数据的任何信息。只有拥有密钥的用户才能够正确解密，得到原始的内容。我们注意到，这个过程中用户是不能对加密结果做任何操作的，只能进行存储、传输。对加密结果做任何操作，都将会导致错误的解密，甚至解密失败。

同态加密方案最有趣的地方在于，其关注的是数据处理安全。同态加密提供了一种对加密数据进行处理的功能。也就是说，其他人可以对加密数据进行处理，但是处理过程不会泄露任何原始内容。同时，拥有密钥的用户对处理过的数据进行解密后，得到的正好是处理后的结果。

有点抽象？我们举个实际生活中的例子。有个叫Alice的用户买到了一大块金子，她想让工人把这块金子打造成一个项链。但是工人在打造的过程中有可能会偷金子啊，毕竟就是一克金子也值很多钱的说… 因此能不能有一种方法，让工人可以对金块进行加工（delegate processing of your data），但是不能得到任何金子（without giving away access to it）？当然有办法啦，Alice可以这么做：

  • Alice将金子锁在一个密闭的盒子里面，这个盒子安装了一个手套。
  • 工人可以带着这个手套，对盒子内部的金子进行处理。但是盒子是锁着的，所以工人不仅拿不到金块，连处理过程中掉下的任何金子都拿不到。
  • 加工完成后。Alice拿回这个盒子，把锁打开，就得到了金子。

这个盒子的样子大概是这样的：

这里面的对应关系是：

  • 盒子：加密算法
  • 盒子上的锁：用户密钥
  • 将金块放在盒子里面并且用锁锁上：将数据用同态加密方案进行加密
  • 加工：应用同态特性，在无法取得数据的条件下直接对加密结果进行处理
  • 开锁：对结果进行解密，直接得到处理后的结果

同态加密哪里能用？

这几年不是提了个云计算的概念嘛。同态加密几乎就是为云计算而量身打造的！我们考虑下面的情景：一个用户想要处理一个数据，但是他的计算机计算能力较弱。这个用户可以使用云计算的概念，让云来帮助他进行处理而得到结果。但是如果直接将数据交给云，无法保证安全性啊！于是，他可以使用同态加密，然后让云来对加密数据进行直接处理，并将处理结果返回给他。这样一来：

  • 用户向云服务商付款，得到了处理的结果；
  • 云服务商挣到了费用，并在不知道用户数据的前提下正确处理了数据；

这方法简直完美啊有没有？！但是，这么好的特性肯定会带来一些缺点。同态加密现在最需要解决的问题在于：效率。效率一词包含两个方面，一个是加密数据的处理速度，一个是这个加密方案的数据存储量。我们可以直观地想一想这个问题：

  • 工人戴着手套加工金子，肯定没有直接加工来得快嘛~ 也就是说，隔着手套处理，精准度会变差（现有构造会有误差传递问题），加工的时间也会变得更长（密文的操作花费更长的时间），工人需要隔着操作，因此也需要更专业（会正确调用算法）。
  • 金子放在盒子里面，为了操作，总得做一个稍微大一点的盒子吧，要不然手操作不开啊（存储空间问题）。里面也要放各种工具吧，什么电钻啦，锉刀啦，也需要空间吧？

这种加密方案真的有在研究？

我举3个简单的例子：

  1. 第一个构造出全同态加密方案的人是Gentry，这是他在Stanford攻读博士学位的研究成果。Gentry毕业后去哪里了呢？IBM。大家知道IBM可是一个云服务提供商啊！在IBM，Gentry和另一个密码学大牛Halevi继续进行同态加密及其相关的研究，并实现了一些同态加密方案。如果IBM真的做出了可以在实际使用的同态加密方案，那么其他云服务提供商就可以拜拜了啊！这游戏不用玩了啊，人家能在不知道数据内容得前提下处理数据啊，毕竟谁都不想把数据泄露给其他公司啊！
  2. 国内的某个大公司（具体是哪个我就不透露了…）对这方面的研究非常感兴趣，我也和他们做了一次交流，并且初步达成了一定的研究大方向。要不怎么我现在也去弄这个头大的东西呢。要知道，国内的公司也没闲着，这是制高点，拿到了就是一家独大，而且是超级技术垄断，不公开源代码或者不了解内部构造的话想仿造都仿造不了啊…不过，这方面的研究说实话Gap确实大，入门起码要3个月的时间，还不一定做的出来…
  3. 即使没有实现全同态加密，也可以得到其他一些很有趣的结论。而每一个结论都可能引发技术垄断。这些结论由于涉及到了一定的基础知识，我在后面中会进行介绍。

业界如何评价全同态加密的构造？

在此引用一个前辈的话：

如果未来真的做出了Practical Fully Homomorphic Encryption，那么Gentry一定可以得到图灵奖。

剩下的，我也就不用多说了吧…

==============================

二、 同态加密的定义、安全性和简单实例

下面的内容，如果可以接受符号表述，具有一点密码学的知识，对抽象代数有一定的了解的话，可能体会的更深刻哦。

同态加密具体如何定义？

我们在云计算应用场景下面进行介绍：

Alice通过Cloud，以Homomorphic Encryption（以下简称HE）处理数据的整个处理过程大致是这样的：

  1. Alice对数据进行加密。并把加密后的数据发送给Cloud；
  2. Alice向Cloud提交数据的处理方法，这里用函数f来表示；
  3. Cloud在函数f下对数据进行处理，并且将处理后的结果发送给Alice；
  4. Alice对数据进行解密，得到结果。

据此，我们可以很直观的得到一个HE方案应该拥有的函数：

  1. KeyGen函数：密钥生成函数。这个函数应该由Alice运行，用于产生加密数据Data所用的密钥Key。当然了，应该还有一些公开常数PP（Public Parameter）；
  2. Encrypt函数：加密函数。这个函数也应该由Alice运行，用Key对用户数据Data进行加密，得到密文CT（Ciphertext）；
  3. Evaluate函数：评估函数。这个函数由Cloud运行，在用户给定的数据处理方法f下，对密文进行操作，使得结果相当于用户用密钥Key对f(Data)进行加密。
  4. Decrypt函数：解密函数。这个函数由Alice运行，用于得到Cloud处理的结果f(Data)。

那么，f应该是什么样子的呢？HE方案是支持任意的数据处理方法f？还是说只支持满足一定条件的f呢？根据f的限制条件不同，HE方案实际上分为了两类：

  • Fully Homomorphic Encryption (FHE)：这意味着HE方案支持任意给定的f函数，只要这个f函数可以通过算法描述，用计算机实现。显然，FHE方案是一个非常棒的方案，但是计算开销极大，暂时还无法在实际中使用。
  • Somewhat Homomorphic Encryption (SWHE)：这意味着HE方案只支持一些特定的f函数。SWHE方案稍弱，但也意味着开销会变得较小，容易实现，现在已经可以在实际中使用。

什么叫做安全的HE？

HE方案的最基本安全性是语义安全性（Semantic Security）。直观地说，就是密文（Ciphertext）不泄露明文（Plaintext）中的任意信息。这里密文的意思就是加密后的结果；明文的意思就是原始的数据。如果用公式表述的话，为：

这里PK代表公钥（Public Key），是非对称加密体制中可以公开的一个量。公式中的"约等于"符号，意味着多项式不可区分性，即不存在高效的算法，可以区分两个结果，即使已知m0, m1和PK。有人说了，这怎么可能？我已经知道m0, m1了，我看到加密结果后，对m0或者m1在执行一次加密算法，然后看哪个结果和给定结果相同不就完了？注意了，加密算法中还用到一个很重要的量：随机数。也就是说，对于同样的明文m进行加密，得到的结果都不一样，即一个明文可以对应多个密文（many ciphertexts per plaintext）。

在密码学中，还有更强的安全性定义，叫做选择密文安全性（Chosen Ciphertext Security）。选择密文安全性分为非适应性（None-Adaptively）和适应性（Adaptively），也就是CCA1和CCA2。

@一大坨

的答案中已经间接提到了，HE方案是不可能做到CCA2安全的。那么，HE方案能不能做到CCA1安全呢？至今还没有CCA1安全的FHE方案，但是在2010年，密码学家们就已经构造出了CCA1的SWHE方案了[LMSV10]。

HE方案还有一方面的安全性，就是函数f是不是也可以保密呢？这样的话HE就更厉害了！Cloud不仅不能够得到数据本身的内容，现在连数据怎么处理的都不知道，只能按照给定的算法执行，然后返回的结果就是用户想要的结果。如果HE方案满足这样的条件，我们称这个HE方案具有Function-Privacy特性。不过，仅我个人所了解到的，现在还没有Function-privacy FHE，甚至Function-privacy SWHE也没有。

不过，Function-privacy引入了另一个很有趣的概念，那就是我们能不能反过来，就做到Function-privacy，但是不用做到数据隐私呢？这其实也有很好的应用场景：比如一个天才设计了一个算法（想象Jeffrey Dean设计了历史上第一个O(1/n)复杂度算法，或者设计了一个O(n^2)算法，但是是用来解决旅行商问题的），但是他不想把这个算法公开。他只提供一个程序，这个程序不泄露任何算法本身的内容，人们只能调用这个算法，然后得到输出的结果。这个特别像什么？对啦，就是程序的编译与反编译嘛。如果Function-privacy的加密设计出来了，那么计算机科学家们就可以一劳永逸地阻止程序反编译，甚至连破解都杜绝了。满足这样条件的加密方案，即，给算法加密的方案，叫做Obfuscation。很遗憾，2001年，密码学家们已经证明，不可能实现严格意义上的Obfuscation [BGIRSVY01]。但是，可以做到一个称为Indistinguishability Obfuscation的东西。这个东西是密码学家们研究同态加密过程中的一个产物，现在已经有了一些候选方案了[GGHRSB13]。这个就不展开说了，是另一个领域的内容。

举个SWHE的例子？

在2009年Graig Gentry给出FHE的构造前，很多加密方案都具有Somewhat Homomorphism的性质。实际上，最最经典的RSA加密，其本身对于乘法运算就具有同态性。Elgamal加密方案同样对乘法具有同态性。Paillier在1999年提出的加密方案也具有同态性，而且是可证明安全的加密方案哦！后面还有很多啦，比如Boneh-Goh-Nissim方案[BGN05], Ishai-Paskin方案等等。不过呢，2009年前的HE方案要不只具有加同态性，要不只具有乘同态性，但是不能同时具有加同态和乘同态。这种同态性用处就不大了，只能作为一个性质，这类方案的同态性一般也不会在实际中使用的。

在此我们看一下Elgamal加密方案，看看怎么个具有乘同态特性。Elgamal加密方案的密文形式为：

其中r是加密过程中选的一个随机数，g是一个生成元，h是公钥。如果我们有两个密文：

我们把这两个密文的第一部分相乘，第二部分相乘，会得到：

也就是说，相乘以后的密文正好是m1m2所对应的密文。这样，用户解密后得到的就是m1m2的结果了。而且注意，整个运算过程只涉及到密文和公钥，运算过程不需要知道m1m2的确切值。所以我们说Elgamal具有乘同态性质。但是很遗憾，其没有加同态性质。

HE的效率如何？

2011年，Gentry和Halevi在IBM尝试实现了两个HE方案：Smart-Vercauteren的SWHE方案[SV10]以及Gentry的FHE方案[Gen09]，并公布了效率。结果如何呢？我们给出Gentry公布的数据（原始数据可以在

2nd Bar-Ilan Winter School on Cryptography

找到）Smart-Vercauteren的SWHE方案效率如下：

看着好像还行，不过这Dimension有点夸张啊…也就是说公钥很长…那么，Gentry的FHE方案如何呢？效率如下：

公钥2.3GB，KeyGen需要2个小时，也是醉了…

==============================

三、 现有HE方案的安全假设和构造概览

如果你致力于HE的研究，我们给出一些可用的资料。

如何证明HE方案的安全性？

对于现在的密码学方案，安全性证明要把它规约到解决一个公开的困难问题上。简单地说，就是如果方案被破解了，那么攻击者可以用破解算法解决一个困难问题。然而，由于这个困难问题还没有找到高效的（多项式复杂度的）算法，因此方案是安全的。

那么，2009年以后的HE方案是建立在哪个困难问题上呢？是一个被称作Learning With Errors（LWE）的困难问题[Reg05]。后来，随着另一个新的工具出现，密码学家们又致力于基于Ring Learning With Errors（Ring-LWE）问题的HE构造[LPR10]。

Ring-LWE涉及到抽象代数中Ring以及Ideal的概念，稍显复杂。我们这里简单介绍一下LWE问题，Ring-LWE问题和它有点像。LWE问题分为两类，一个叫做Search-LWE，一个叫做Decision-LWE。Search-LWE可以简单地用下图来表示，其中A是一个m*n的矩阵，由Zp中的元素组成；s是一个n维向量；e是一个m维向量；b是一个m维向量：

这个问题大致为：选择一个秘密（secret）值s，并选择一个范数很小的扰乱（error）向量e，计算b = As + e mod q。这个问题是：只给定矩阵A和计算的结果b（图中红色部分），不给定s和e（途中蓝色部分），反过来求秘密值s的大小。Decision-LWE问题有点类似：给定A和b，算法需要判断，b是由某个s通过As + e计算得来的呢，还是就是一个随机量呢？这里有几个小问题：

  1. m和n有多大？这取决于我们要求安全度有多高了。实际上这还取决于一些其他因素。
  2. e的范数要多么小？LWE要求e的取值要满足离散高斯分布（Discrete Gaussian Distribution）。
  3. 怎么想到的这么个问题？实际上，LWE问题是Lattice中的一个问题。Lattice是什么呢？这个展开说就有点累了…

如果知乎er们想了解更多有关Abstract Algebra，Lattice，以及LWE的内容，下面的三个材料是可以阅读的：

  • Harvard Extension School的Abstract Algebra课程。这门课可以帮助快速入门Abstract Algebra。当然了，这可是Harvard学生的本科课程哦。Abstract Algebra
  • 2nd Bar-Ilan Winter School on Cryptography。Bar-llan大学自2011年开始每年都组织一次密码学的Winter School，请的都是大牛啊！2012年的主题是Lattice-Based Cryptography，2013年的主题是Pairing-Based Cryptography。2015年2月，新的一轮Winter School就开始了，知乎上 @刘健 同学要去听的哦，羡慕嫉妒恨呢！2nd Bar-Ilan Winter School on Cryptography
  • Oded Regev的Lecture Notes on Lattice。Regev是谁？是他提出的LWE和Ring-LWE，所以他课程的材料当然有价值一听。Lattices in Computer Science (Fall 2009)

介绍一下构造FHE的思路？

FHE最重要的一点是Fully，就是说要支持任意的函数f。因此我们也可以很明显看出，想要构造FHE，就需要了解计算机是如何计算的。一般来说，我们有两种思路：

  • 从计算机原理考虑。计算机无论做何种运算，归根到底都是位运算。那么，计算机至少要支持哪些位运算，才能够支持所有的运算呢？实际上，一个计算机只要支持逻辑与运算（AND），以及异或运算（XOR），那么这个计算机理论上就可以实现计算机的其他运算了（我们称之为图灵完备性，Turing Completeness）
  • 从抽象代数考虑。我们只需要加法和乘法就可以完成全部运算了。但其实更严格的说，只要我们在一个域（Field）上构造HE，理论上我们就可以支持所有的f。

基于LWE问题的FHE只能针对1 bit进行加密，因此现在的构造都是从计算机原理考虑。也就是在bit的层面上实现FHE方案，或者更严谨地说，从电路层（Circuit）实现FHE方案。具体构造呢，大家刻意参考下面给出的参考文献了。实话实说，我自己也没有都消化，或者更严格地说，Regev的LWE构造论文我还没有完全看明白。因此，我在此也号召密码学爱好者一起研究啦~

==============================

以上。

==============================

参考文献

[RAD78] Ron Rivest, Leonard Adleman, and Michael L. Dertouzos. On data banks and privacy homomorphisms. Foundations of Secure Computation, 1978.

[Gen09] Craig Gentry. Fully homomorphic encryption using ideal lattices. STOC 2009. Also, see “A fully homomorphic encryption scheme”, PhD thesis, Stanford University, 2009.

[LMSV10] Jake Loftus, Alexander May, Nigel P. Smart, and Frederik Vercauteren. On CCA-Secure Fully Homomorphic Encryption. Cryptology ePrint Archive 2010/560.

[BGIRSVY01] Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil Vadhan, and Key Yang. On the (Im)possibility of Obfuscating Programs. Crypto 2001.

[GGHRSB13] Sanjam Garg, CraigGentry, Shai Halevi, MarianaRaykova, Amit Sahai, and Brent Waters. Candidate indistinguishability obfuscation and functional encryption for all circuits. Foundations of Computer Science, 2013.

[Paillier99] Pascal Paillier. Public-Key Cryptosystems Based on Composite Degree Residuosity Classes. Eurocrypt 1999.

[BGN05] Dan Boneh, Eu-Jin Goh, and Kobbi Nissim. Evaluating 2-DNF formulas on ciphertexts. TCC 2005.

[GH11a] Craig Gentry and Shai Halevi. Implementing gentry’s fully-homomorphic encryption scheme. Eurocrypt 2011.

[SV10] Nigel P. Smart and Frederik Vercauteren. Fully homomorphic encryption with relatively small key and ciphertext sizes. PKC 2010.

[Reg05] Oded Regev. On lattices, learning with errors, random linear codes, and cryptography. STOC 2005.

[LPR10] Vadim Lyubashevsky, Chris Peikert, and Oded Regev. On ideal lattices and learning with errors over rings. Eurocrypt 2010.

类似的话题

本站所有内容均为互联网搜索引擎提供的公开搜索信息，本站不存储任何数据与内容，任何内容与数据均与本站无关，如有需要请联系相关搜索引擎包括但不限于百度，google,bing,sogou 等

© 2025 tinynews.org All Rights Reserved. 百科问答小站 版权所有

服务条款
联系我们
关于我们
隐私政策
友情链接
知乎
百度问答
搜狐
新浪