简述双密钥加密算法：全同态加密的理论与构造-上篇

简述双密钥加密算法：全同态加密的理论与构造-上篇IND-CCA1是选择密文攻击下的不可区分性。相对前者，增加敌手可以在收到之前，调用一次加密或解密能力，下面是具体流程：如果可以忽略，那么可以认为和不可区分。IND-CPA是选择明文攻击下的不可区分性。敌手和挑战者商定目标密码体制，选定加密密钥pk，然后进行以下各阶段：寻找阶段：敌手选择两个等长的明文猜测阶段：敌手被挑战者告知其中一个明文和随机数r的加密结果 判断是还是 其中b是保密的。敌手的目标是以大于二分之一的概率猜对b的值。下面定义敌手的优势。

1基础知识同态加密算法的简单定义如下：

同态加密的一个经典的应用是外包计算（或者说云计算）。有一个客户端计算能力很弱，而服务器计算能力很强。客户端希望云服务器执行计算任务，但又不想泄露隐私数据。此时可以考虑使用同态加密进行加密计算。这是一个非常经典的应用场景。

1.1 安全性

为了保证更强的安全性，GoldWasser和Micali在1984年提出了概率加密，引入更强的安全目标：语义安全。理论上已证明，语义安全（Semantic Security，SS）等价于密文不可区分性。semantic security 语义安全：一个密文不会泄露除了长度之外的任何明文信息。我们很少用semantic security的形式来说明算法的安全性，因为他形式化的描述比较晦涩。IND-CPA 、IND-CCA1、IND-CCA2是常见的对于公钥加密安全性的定义。这里对三者进行简单介绍。参考了下面链接的文章。

[https://blog.csdn.net/m0_47659650/article/details/125223197]

IND-CPA

IND-CPA是选择明文攻击下的不可区分性。敌手和挑战者商定目标密码体制，选定加密密钥pk，然后进行以下各阶段：寻找阶段：敌手选择两个等长的明文

猜测阶段：敌手被挑战者告知其中一个明文和随机数r的加密结果 判断是还是 其中b是保密的。

敌手的目标是以大于二分之一的概率猜对b的值。下面定义敌手的优势。

如果可以忽略，那么可以认为和不可区分。

IND-CCA1

IND-CCA1是选择密文攻击下的不可区分性。相对前者，增加敌手可以在收到之前，调用一次加密或解密能力，下面是具体流程：

训练： 敌手向挑战者请求任意密文的解密（多项式有界次数），即选取密文C给挑战者，挑战者返回解密结果给敌手。

挑战：敌手A选择两个等长的明文 再从挑战者接受加密后的密文 b是随机的；猜测：敌手输出 若= 则敌手成功。敌手的目标是以大于二分之一的概率猜对b的值。下面定义敌手的优势：

敌手

如果敌手可以忽略，那么认为此密码体制在非适应性选择密文攻击下具有不可区分性，称为IND-CCA1安全。

IND-CCA2

IND-CCA2是自适应选择密文攻击下的不可区分性。
相对前者，不限制敌手调用解密的时间。下面是具体流程：

训练1：敌手向挑战者请求任意密文的解密（多项式有界次数），即选取密文C给挑战者，挑战者返回解密结果给敌手。挑战：敌手A选择两个等长的明文 再从挑战者接受加密后的密文 b是随机的；训练2：敌手继续向挑战者请求任意密文的解密（多项式有界次数），即选取密文C（C不能是）给挑战者，挑战者返回解密结果给敌手。猜测：敌手输出 若= 则敌手成功。

同态算法是不能做到IND-CCA2的。IND-CCA1能做到但是比较复杂。在这个课程，只专注于IND-CPA这个级别的语义安全。

1.2 从SK-HE 到 PK-HE

在同态加密暑期班郁昱老师的课程笔记中我们也提到过，可以从一个对称同态加密算法来构造一个非对称的同态加密算法。我们接下来再简单回顾一下。假设是一个对称同态加密算法。

定义：

其中B是密文的规模上限。

假设我们要加密 定义

Choose such that.

Define.

Let定义则得到的是一个公钥加密的同态加密算法。因此，在不考虑效率的情况下，对称的全同态算法和非对称的全同态算法是等价的。

2Gentry's Bootstrapping 理论

2.1 Augmented Decryption Circuit

假设是一个非对称同态加密方案。我们定义一个Decryption Circuit如下：

这个公式可以理解为用对密文进行解密。在这里是输入，是公开的。

若= 则：

Augmented Decryption Circuit：

NAND是一个通用电路，我们可以使用NAND来构造任何逻辑电路。NAND可用如下式表达，

这个定义也有一个很好的性质，

NANDNAND

2.2 Bootstrapping Theorem

对于一个同态加密算法，如果他对密文计算支持Augmented Decryption Circuit，那么它是bootstrappable。

如果存在一个bootstrappable公钥同态加密机制，那么就一定存在全同态加密机制。

remark: 这里是对定理的一个简化版本的描述，完整版还需要加上更多的限制。但是这并不影响我们对课程的理解。

2.3 Gentry's Construction

假设是一个bootstrappable的同态加密算法。我们根据以下步骤来进行构造。

1 密钥生成