物联网客户端的实用加密计算方法（二）

3.客户端优化的客户端辅助HE

CHOCO是一个客户端优化的系统模型和客户端辅助加密计算的实现。该模型假设了一个资源受限的客户端设备和一个计算能力更强但不受信任的共享卸载服务器。对典型的HE系统，我们假设卸载设备采用的是半诚实的对手模式：对手（攻击者）可能会对输入的数据感到好奇，但系统是可信的，它将忠实地执行指定的操作。与计算成本高昂的MPC协议相比，CHOCO不做任何试图向客户端隐藏卸载设备上的数据，包括预训练的ML模型数据。相反，CHOCO的首要任务是为物联网设备的敏感客户端数据提供强有力的隐私保障。

CHOCO实现了客户端辅助的HE卸载，在客户端和卸载设备之间逐层划分工作。它优化了之前工作中所开发的加密算法，并调整了加密参数，使所执行的客户端工作量变得可行。CHOCO引入了旋转冗余，这是一种新的方法，来重新排序加密在密文中的数据向量，这对卷积等矩阵操作非常有用。该技术减少了常见的旋转操作所带来的噪声增长，允许较小的参数选择和相应的较小的密文。

A.选择高效的HE参数

在加密应用程序开发中，选择合适的HE参数（如第二节A部分中介绍的那样）是至关重要而又繁琐的一步[15]。不同参数的选择会导致不同的密文大小和噪声特性，而这些特性又会影响客户端辅助模型的计算、加密、解密和通信成本。一个系统可以用不同的参数（如不同的密文大小）以达到相同的安全级别。因此，CHOCO通过量化和加密算法优化，主动把参数选择减至最少。

HE方案的明文模数t定义了在加密向量的每个元素中存储每个明文值的位数。CHOCO在加密前将数据量化为较少的比特（bits ），因为在允许的情况下，量化为较少的比特可以使用较小的明文模数。由表4中t值的变化可以看出，这在不改变密文大小的情况下，增加了密文的噪声预算，从而激励了不溢出[35]的最小可能的t。我们的CHOCO原型将符号的浮点输入值量化到4位范围。然后依次应用卷积的HE运算，将这些值扩展到（但不超过）我们的23位质数系数模值。当密文在层边界刷新时，数据也会被重新量化为4位。

B.HE算法优化

CHOCO使用SEAL加密计算库[27]中的加密基元来实现Gazelle[18]中开发的HE算法。这些HE算法对应于（例如DNN推理中使用的）加密线性代数运算。在CHOCO中，所有这些加密计算都在卸载设备上执行。

在第二节B部分中介绍过，Gazelle实现了打包同态算法，它要求在加密向量中重新排序输入元素。这样一来，元素就会被适当地对齐，以便进行如1-D、2-D和步幅卷积等矩阵操作[18]。任意排列带来的一个关键挑战是，每个排列都需要一连串的加密向量旋转和隐蔽乘法操作[36]。这种操作的深度很快就会消耗掉密文有限的噪声预算。

旋转冗余是一种对加密向量进行某些排列组合的新方法。该技术的目标是窗口化旋转排列，旋转一个矢量子区间内的元素，将元素从子区间的顶部环绕到底部，反之亦然。这与自然支持的HE旋转不同，HE旋转只能对矢量进行整体旋转。图5显示了对密文的窗口化旋转排列。图5显示了对密文的窗口化旋转排列。标准实施(A)同时使用旋转和隐蔽乘法，以迅速耗尽密文的噪声。相比之下，CHOCO中引入的实施(B)使用旋转冗余来执行这样的排列，而只需要一个相对低成本的加密旋转。旋转冗余的关键是在加密前，将要旋转的数值窗口以两边的附加冗余打包。冗余包含了执行排列时 “环绕 “的窗口内元素。经过一系列的窗口旋转和其他操作后，在解密时只需忽略感兴趣的窗口之外的值。窗口化旋转所需的冗余量与要执行的旋转量相对应，而且，对于卷积中使用的旋转，通常只占向量大小的一小部分。旋转冗余以使用更多的向量空间来换取更慢的密文噪声消耗，进而可以使用更小的参数选择。表4量化了这些好处。

在我们的神经网络图像分类实现中，密文向量是图像中每个通道的向量的级联。执行推理需要在每个通道内进行窗口化旋转。我们将图像打包，给每个通道增加旋转冗余。然后将通道打包到密文中均匀分布的二幂插槽中，整个通道的对齐也可以通过简单的加密旋转和无隐蔽乘法来实现。最终，卷积实现了最优的乘法效率–权重与输入的单乘法。

在所有算法和参数优化后，CHOCO利用了只有2个质数残差的新加密密文，比SEAL默认参数N=8192的密文大小减少了50%。其中一半的改进，整个残差的消去，都仅仅是来自于旋转冗余。正如第六节中所讨论的那样，这种密文大小的减少在计算和通信成本方面都有直接和显著的好处。

4.硬件加速

CHOCO-TACO是一个用于同态加密和解密操作的硬件加速器，专为客户端辅助HE而设计。图3显示，仅加速NTT/INTT和二元乘法[31]不足以降低这些加密基元的主要成本。相比之下，CHOCOTACO有效地加速了构成HE加密和解密的所有组件函数，我们在第四节C部分中通过一个工作示例演示了这一点，并在第五节中定量地展示了这一点。

A.BFV加密

CHOCO-TACO加速非对称BFV加密，如公式3[28]所述，其中m为待加密的信息，P0、P1为公钥，u、e1、e2为随机采样数的向量。图6完整地展示了SEAL[27]中方程3的RNS实现。该算法首先将随机采样的数字向量与公钥，通过系数乘法和加法结合，生成一个加密的 “零”，从而对信息进行加密。然后将编码后的信息添加到加密后的零点上，以生成最终的密文。

B.加密架构

CHOCO-TACO加速了构成BFV加密和解密的每个主要子操作。CHOCO-TACO是一个直接实现BFV算法的并行流水线加速器。图7展示了完整的加密和解密加速器。本设计有几个关键模块：随机数生成、多项式乘法、多项式加法和模数切换、消息编码。每个模块都包含功能块，可以复制以实现并行，以及执行每个操作所需的内存。每个功能块都包含一个处理元素数组，以便在一个功能块内实现数据并行。此外，该设计还在模块内和模块间进行流水线式操作。

1）随机数生成

CHOCO-TACO有一个专门的RNG模块，实现了Blake3[37]加密散列（hashing）算法。图7中的CHOCO-TACO配置，要求该模块在峰值时生成565 MB/s的随机值，平均为201 MB/s。RNG模块还负责将提供的随机性解释为三元分布或正态分布的整数，并将其转换为RNS形式。我们升级了我们的软件加密实现，使用Blake3而不是Blake2，使算法性能提高到CHOCO-TACO和基线。

2）多项式乘法

CHOCO-TACO包括一个模块，用于两个多项式的多项式乘法，就如之前的工作[31]-[34]一样。该模块将多项式转化为NTT形式，然后进行按元素并向量积。该模块使用INTT将结果转换回多项式。CHOCO-TACO的NTT和INTT模块在概念上与HEAX相似[31]。这些模块遵循NTT的蝶形数据流模式，执行流水线式的SIMD内存访问。

硬件计算u和每个公钥P0和P1的RNS形式的多项式乘法。SEAL以NTT形式存储公钥，所以在硬件上只支持对u进行单一NTT转换。NTT的蝶式数据流要求一次访问整个多项式，排除了激进的流水线（即转发部分结果）。一旦u完全转换，结果随P0和P1一起流至并向量积块。两个密文组件（c0和c1）都使用相同的NTT编码的u，使其在整个加密过程中保持在NTT工作缓冲区中。二元乘法的结果流至单独的INTT缓冲区。所有输出累加后，硬件执行就地INTT，生成结果。

3）多项式加法和模数转换

多项式乘法后，加速器应用多项式加法和模数切换。多项式加法是多项式的系数加法，一个输入来自INTT缓冲区，另一个来自RNG模块填充的缓冲区。输出填充一个小的中间缓冲区，该缓冲区是模数切换的输入，它将RNS编码中的主关键残差去除，导致是k – 1多项式。模数切换应用了一系列模块化的乘法和还原，模数切换是唯一需要跨RNS残差交互的操作，这就排除了直接跨残差的数据并行。

4）信息编码

加密零点后，CHOCO-TACO对输入的信息进行编码、缩放，并将其添加到加密的零点上。编码/解码模块包括一对小NTT和INTT块。编码硬件通过明文模数t计算出每个系数的模数，并将系数重新排序到明文的插槽中。硬件必须通过缩放将编码信息转换为RNS，仅用k-1个残差表示。专用的多项式加法模块将结果加到c0的k – 1个中间残差上，并将结果存储在最后的输出缓冲区中。

5）储存器

每个模块都集成并管理嵌入式SRAM暂存存储器。除NTT外，所有模块都接受流式输入，模块的存储器必须按照输入到达的速度和运行时间来容纳它的（并行）输入流。然而，NTT和INTT在算法上对整个多项式进行操作，要求其缓冲区根据HE方案的多项式大小来调整大小。当HE参数N=8192，k=3时，每个NTT/INTT缓冲区为64kB。相反，通过我们在第五节中的设计空间探索来划分大小的其他存储器，大小都在1kB以下。正如第五节所述，我们使用Destiny来对存储器进行建模，Destiny是为单一读取器，单一写入器64字节数据访问而移植的。

C.加密操作示例

BFV加密将零加密成密文，并在加密后的零密文中添加一条缩放的信息。首先，加速器根据三元分布从RNG中采样N个字节，以u的形式存储在NTT工作缓冲区中。NTT块就地生成u的NTT，该值成为并向量积模块的输入。并向量积模块的另一个输入是加速器输入缓冲区，软件用公钥P1的NTT变换残差进行初始化。二进乘法在INTT块的缓冲区中生成u和P1的元素乘积，由INTT块对其进行处理。

与u和P1的并向量积并行，RNG单元生成e2，这是一个8字节的、正态分布的样本序列，将它们存储在密码加法模块的缓冲区中。当INTT完成后，PolyAdd模块流入其结果，与e2按元素进行相加，并将结果存储在模数切换模块的缓冲区中，如c1。

c1是最终密文的一个组成部分，它被输出到CPU的主机内存中。

同时，加速器开始在Poly乘法模块中生成c0。计算c0重用了u的NTT，用公钥P0按元素相乘。加速器对一组正态分布的8字节e1值序列（如e2）进行采样，将它们与u和P0的乘积INTT的结果按元素相加。加速器对一组正态分布的8字节e1值序列（如e2）进行采样，将它们与u和P0的乘积INTT的结果按元素相加。其结果是密码文本的另一个组成部分c0的部分计算版本。

最后一步是将部分计算出的c0和编码后的输入信息进行多项式加法，生成c0，c0与c1一起构成最终的密文。

D.增加并行性

CHOCO-TACO利用BFV加密中可用的通道和数据并行性。平行性存在于独立的RNS残差、独立系数和整个加速器的流水线中。多项式乘法和加法操作了RNS编码多项式的多个残差。每个残差都是被操作的多项式的独立部分，需要对每个残差进行相同的操作。

在面积和功率的限制下，CHOCO-TACO架构可以创建这些操作模块的并行副本，包括它们的输入和输出存储器，从而实现多项式RNS残差的并行处理。RNS并行还消除了为将来的执行而缓冲大量随机数向量的需要。图7通过分层图形化地说明了RNS残差操作的并行性。

在每个RNS层中，每个多项式的数千个系数提供了数据并行性。CHOCO-TACO架构的一个关键设计参数是每个模块利用这个数据并行源的程度。在面积和功率的限制下，CHOCO-TACO架构可以在一个模块中创建模块的并行副本，确定存储器的大小以匹配，从而实现更高的系数吞吐量处理。第五节系统地探讨了并行加速器的设计空间。

E.解密支持

BFV解密在操作上与加密非常相似。公式4从数学上展示了解密。

图7用黑线表示了解密的控制和数据流。解密需要一些额外的硬件组件，但需要重复用现有的多项式乘法和加法模块来处理c1、s和c0。此外，这些中间结果经过快速的基数变换和纠错，之后只需对信息进行解码。解码使用信息编码模块，执行NTT，然后通过明文模数t进行模变（调制）。其结果是解密后的信息，由硬件传达给CPU的储存器。

参考文献（二）

[1]H.-J. Chae, D. Yeager, J. Smith, and K. Fu, “Wirelessly powered sensor networks and computational rfifid,” 01 2013.

下略