2.2 电路加密

密码学领域涉及的电路一般有两种： 布尔电路 和 算术电路 。两者都用于表示计算过程（或者说通常意义上的算法），它们的区别仅在于输入的类型和门电路类型。布尔电路的输入及输出是比特，门电路是布尔操作，如与、或、非等；算术电路的输入是某个域上的元素，其门电路通常是域上的算术运算，即加法和乘法。

2.2.1 为什么用电路来表示

在计算复杂性理论中，计算多项式最自然的计算模型就是算术电路。简单地说，算术电路以变量或数字作为输入，并且允许使用加法、乘法两种运算来操作表达式。使用算术电路可以很好地理解计算多项式所需的复杂性。对于一个给定的域 F ，一个算术电路计算一个在 F ［ x ₁ ，…， x _n ］中的多项式。顺便提一句，证明某些多项式在算术电路下需要操作步骤的下界问题是计算复杂性理论中重要的难题。

同态加密算法定义在域上，所以使用算术电路来表示计算是很方便的。如图2-5所示为（ x ₁ +2）（ x ₂ +3）（ x ₃ +6）的算术电路。

不管是布尔电路还是算术电路，都有一个在应用于同态加密时很优良的特性，即 电路包含的操作非常简单，仅仅是电路门所对应的逻辑操作或算术操作，没有选择、判断、循环等复杂操作， 这对于密文处理来说太便利了，用户仅需要对每一个电路门实现同态密文运算即可。在密码学的研究应用以及计算复杂性的研究中，使用电路来表示运算或者算法屡见不鲜，比如在安全多方计算中往往也是采用电路来表示计算的。

对于密码学研究人员来说，使用电路确实省事，但是 对于程序设计开发人员来说，将已有的程序或者算法翻译成电路是一件难度很大的事情。

2.2.2 布尔电路：数理逻辑的玩具

数理逻辑是研究推理逻辑规律的数学分支，它采用数学符号化的方法，给出推理规则来建立推理体系，进而讨论推理体系的一致性、可靠性、完备性。在计算机科学中，数理逻辑是一门基础课，也是数字电路发展的理论基础。数理逻辑中最基础的概念是命题真伪的推导和计算，其中命题真值的演算过程需要使用“与”“或”“非”等逻辑连接词。

布尔电路是组合数字逻辑电路的数学模型，布尔电路也被用作数字电子学中组合逻辑的形式化模型。布尔电路由输入、输出、逻辑门和有向连接线组成。输入、输出和逻辑门通过连接线连接。如果把输入、输出和逻辑门看作节点，把线看作边，一个布尔电路就可以用一个有向图来表示。一个布尔电路由电路中所包含的逻辑门来定义，如与门、或门、非门等，每一个逻辑门对应一个输出为单比特的布尔函数，如图2-6所示。

上述逻辑门也可以用文本符号表示，与门符号为“∧”，或门符号为“∨”，非门符号为“¬”，异或门符号为“⊕”，同或门符号为“☉”。布尔函数可以用逻辑门在硬件上实现。布尔电路或布尔网络由电路门组成，用于实现一些布尔函数。当上下文中的含义明确时，可以使用术语“电路”或“网络”来表示布尔电路。图2-7给出了布尔电路的示意图。

为展示布尔电路的能力，这里给出一个 使用布尔电路实现加法运算 的例子。假设给定两个 n 比特的整数 a 和 b ，用二进制表示为 a = a _{n -1} a _{n -2} … a ₀ ， b = b _{n -1} b _{n -2} … b ₀ ，下面使用布尔电路实现 a + b 的计算，令 s = a + b 。显然其是 n +1比特的整数，用二进制表示为 s = s _n s _{n -1} … s ₀ ，为了进一步表示二进制加法过程，定义 c _i 为第 i 位的进位， i =0，1，…， n 。

回顾一下二进制加法过程，显然符合如下规则：

s ₀ = a ₀ ⊕ b ₀

c ₀ =0

c _i =（ a _{i -1} ∧ b _{i -1} ）∨（ a _{i -1} ∧ c _{i -1} ）∨（ b _{i -1} ∧ c _{i -1} ）

s _i = a _i ⊕ b _i ⊕ c _i

s _n = c _n

通常，加法是从低位到高位顺序执行的，因为高位的计算结果受到低位进位的影响。但是在加法电路的设计中希望通过电路能够提升并发性，观察到以下情况：第 i 位存在进位，意味着在第 i 位之前，有某个位置生成进位，并且该进位一直传递到第 i 位。

为标记进位信息，对于0≤ i ≤ n ，有如下两个变量定义：

g _i = a _i ∧ b _i

p _i = a _i ∨ b _i

这两个变量的含义是： g _i =1时说明第 i 位产生一个进位； p _i =1时说明第 i 位能够传递一个进位。也就是说，如果第 i -1位有进位传递给第 i 位，那么第 i 位会将该进位传递给第 i +1位。

因此，“第 i 位存在进位”这一事件成立的条件用形式化的文本符号表示为：

一旦可以计算进位，则可以计算每一位的求和结果为： s ₀ = a ₀ ⊕ b ₀ 、 s _i = a _i ⊕ b _i ⊕ c _i 、 s _n = c _n 。这三个公式结合前面进位计算的公式，可以看出 C _i 可以并行计算。于是，整个加法过程也可以并行计算， n =3时的布尔电路如图2-8所示。

2.2.3 用电路表示算法

对于程序员朋友来说，平时开发程序参考的算法都是用伪代码或者流程图表示的。一般情况下，算法中有三种结构：顺序、选择、循环。

使用类C语言伪代码表示，典型的选择结构如下。

if（条件）

语句块1；

else

语句块2；

使用流程图表示为图2-9所示。使用流程图实现时，可以 使用组合逻辑，通过下述布尔代数式来表达：

（条件∧语句块1）∨（¬ 条件∧语句块2）

或者使用电路图表示，如图2-10所示。该电路执行的流程是，从“开始”信号启动电路后，首先组合条件逻辑模块输出条件为“真”或“假”的信号，如果条件为“真”，执行信号就激活语句块1的执行逻辑；反之，如果条件为“假”，执行信号就激活语句块2的执行逻辑。总而言之，根据条件信号，响应开始启动语句块1或语句块2。一旦语句块1和语句块2中的任意一个输出“已完成”信号，或门将“已完成”信号作为整个逻辑块的输出完成。

循环结构一般有三种模式：while循环、for循环、do-while循环。以while循环为例，典型的while循环结构如下：

while（条件）

循环体；

使用流程图表示为图2-11所示。

while循环执行的原理是，每次循环开始前先判断条件是否成立，如果成立则进入循环体并执行一次，如果不成立则结束。使用电路图的表示为图2-12所示。

上述电路执行的流程是，判断条件组合逻辑输出一个条件为“真”或者为“假”的信号，当开始执行信号到来时，如果条件为“真”，则进入循环体执行，如果条件为“假”，则进入一个翻转信号后，输出“已完成”信号。

2.2.4 同态加密中的电路

在各类具体应用中，需要对算法电路进行精心设计，以免在应用同态方案时由于电路规模过于庞大导致效率太低。以检索为例来分析电路的构成，在数据库中进行一次检索由两个步骤组成：首先要把检索内容与数据库中的数据进行比较（对比步骤）；其次要根据上一步对比的结果进行输出（决定步骤）。如果 使用同态加密实现密文检索， 必须借用特定的密文同态操作， 具体说来，实现如下三个同态电路模块就可以构建同态密文检索方案了。

●同态减法模块FHE_Sub。

●同态比特逆模块FHE_Inv。

●同态相等判断模块FHE_Equal。

1.FHE_Sub的实现

FHE_Sub实现密文减法，以 a 和 b 的减法为例，令 a' 和 b' 是 a 和 b 加密以后所得的密文， a 和 b 之间的减法可以使用下述公式实现：

a-b = a + b 的补码

即密文减法 a'-b' 可以通过 a' 加上 b 补码的密文来实现。而 b 补码的密文可以通过下述公式来实现：

Enc（ b 的补码， pk ）= b' ⊕Enc（11…1， pk ）⊕Enc（1， pk ）

因此，整个FHE_Sub可以通过图2-13所示电路模块图实现。

2.FHE_Inv的实现

FHE_Inv模块执行加密的 比特翻转： 将0的密文变成1的密文，将1的密文变成0的密文。当输入记为“输入”时，该模块可以通过如下简单公式实现：

输出=输入 ⊕Enc（1， pk ）

3.FHE_Equal的实现

本模块如图2-14所示，用于检查两块密文数据是否同态相等（即对应明文是否相等）， 如果二者相等，则二者之差为0， 因此只需用FHE_Sub模块进行密文减法，然后执行以下步骤。

1）使用FHE_Inv模块对减法结果的每一个比特都同态地进行翻转。

2）将上一步的结果进行逐比特同态相乘。

3）如果相减的结果非0（意味着两个输入数据对应明文不相等），则相减结果至少有一个比特非0，于是翻转后逐比特同态相乘的结果为0的密文。

4）检查逐比特同态相乘的结果，如果是Enc（1）则代表“相等”；如果是Enc（0）则代表“不等”。

4.密文数据的同态搜索

有了上述几个模块作为工具，可以很容易地构建密文同态搜索算法。令检索关键词密文为 s ，加密数据库为DB，其中包含 n 个加密数据项，检索流程如图2-15所示。

如果要检查同态减法的每一项，需要解密 n 次，为了简单起见，采取如下流程。

1）使用FHE_Sub对 s 和DB中的每个数据项执行同态减法运算，记结果为sub ₁ ，sub ₂ ，…，sub _n 。

2）使用FHE_Equal检查sub ₁ ，sub ₂ ，…，sub _n 是否等于0。

3）为避免解密FHE_Equal的每个结果，将上一步中FHE_Equal执行的 n 个结果均执行同态翻转FHE_Inv，并将 n 个翻转后结果同态相乘，得到一个输出结果。

4）若输出结果为0的密文，则搜索成功；若输出结果为1的密文，则说明DB中不包含 s 所表示的检索项。

5.同态密文交换

排序是一种常用的算法，在数据的排序过程中经常使用交换功能，例如，多次使用冒泡排序算法直接交换两个数据。同态密文交换是有效实效同态密文排序算法的关键模块。

使用FHE_Mux、同态加法FHE_Sub可以很容易组装出同态密文交换电路， 如图2-16所示。

FHE_Swap模块对两个输入数据（记为 A ［ i ］和 A ［ i +1］）进行操作，通过FHE_Sub进行同态减法以判断 A ［ i ］和 A ［ i +1］的大小，并使用FHE_Mux模块来实现交换，如下：

A ［ i ］=FHE_Mux（ A ［ i ］， A ［ i +1］， bt ）

A ［ i +1］=FHE_Mux（ A ［ i ］， A ［ i +1］，（1 -bt ））

其中，FHE_Mux电路模块的功能是根据最后一个输入比特决定从前两个输入中选择一个作为输出。如果 bt =1，则输出第一个输入参数；如果 bt =0，则输出第二个输入参数。 l8IE9dkJms5oP8MyCuAyR3RZltViG5NTbIMZidvZDIIBfZq1X7ZQ7Y5EzjSVNQyV