前几日业内报道“阿里安全最新研发的Cheetah（猎豹）安全两方计算框架让两方计算的整体性能取得了大幅提升，最快可比目前世界最好的计算方案——微软CryptFlow2快5倍以上”，这个消息得到了业界广泛关注。

链接：阿里安全开源顶尖两方计算技术研究被安全顶会收录

今天特意给大家分享上面报道里提到的这篇由阿里安全双子座实验室的洪澄博士团队发表在USENIX Security'22的论文《Cheetah: Lean and Fast Secure Two-Party Deep Neural Network Inference》。

文章链接如下:

https://eprint.iacr.org/2022/207。

今天这个中文版是在昨天那版基础上的进一步理解更新。感谢洪澄老师对本译文的更正和补充，本次更新修正了部分错误，并扩展了SIMD技术中的Packing操作，希望对大家有帮助。

Cheetah: Lean and Fast Secure Two-Party Deep Neural Network Inference

• 摘要

• 技术概览

• 预备知识

• 威胁模型

• 符号约定

• 基于格的同态加密

• 扩展: SIMD的Packing操作

• 不经意传输

• 线性层的2PC协议

• 全联接层(FC层)

• 卷积层(CONV层)

• 批标准化层(BN层)

• 非线性函数的2PC优化协议

• 百万富翁协议

• 近似截断

• 优化

• 计算优化

• 通信优化

• 实验

• 总结

• 参考文献

摘要

2PC-NN安全推理与实际应用之间仍存在较大性能差距, 因此只适用于小数据集或简单模型. 本文通过仔细设计DNN, 基于格的同态加密、VOLE类型的不经意传输和秘密共享, 提出了一个2PC-NN推理系统Cheetah, 比CCS'20的CrypTFlow2技术开销小的多, 计算效率更快, 通信效率更高. 主要贡献有两点:

• 基于格的同态加密的协议可在不进行任何昂贵同态rotation操作的情况下评估线性层;
• 提出了非线性函数的几个精简且通信高效的原语.

本文的方案在ResNet50神经网络下在WAN进行端到端安全推理需要不到2.5分钟和2.3G通信量, 分别优于CrypTFlow2约5.6倍和12.9倍.

具体代码已在Github开源: 

技术概览

现有的大多基于HE的方案构造2PC-NN协议存在两大痛点: 一是为使用同态SIMD均摊同态运算操作, 只能在上工作, 需要额外借助CRT才能支持, 造成额外的同态计算开销, 降低了效率; 二是NN推理的计算中的卷积和矩阵计算涉及大量的同态rotation操作, 是主要的性能瓶颈. Cheetah提出的方案不需要使用SIMD和rotation, 从而避免了这两个问题.

2PC-NN的非线性计算, 如比较、截断等一直是影响安全推理速度的一大原因. 例如CrypTFlow2中的截断协议通信开销超过50%. VOLE类型OT协议的出现可以更新现有OT扩展, 用于非线性函数的两方安全评估, 但直接应用VOLE类型OT协议并不能达到最佳性能. 本文中优化了以下两点:

• CrypTFlow2中的截断协议被设计为消除两个概率误差: 溢出误差和尾部误差, 其中. 前者对安全推理的结果影响极大, 但后者1bit误差造成的影响几乎可以忽略. 基于此, 可以不考虑, 设计更加高效的截断协议来消除.
• 通过使用VOLE类型OT协议, 在已知最高有效位的前提下, Cheetah实现了更高效的截断协议.

Cheetah与最先进的2PC协议复杂度比较如表1.

预备知识

威胁模型

Cheetah是半诚实两方计算设定下构造的. 两方分别为Alice(作为Server)和Bob(作为Client). 在安全推理中, Alice持有DNN, Bob持有神经网络的输入, 如图像. 协议允许Bob获得神经网络架构信息和推理输出, 而Alice根据应用场景的不同要么没有输出, 要么得到安全推理结果.

符号约定

表示集合. 多项式表示为, 其第个系数表示为. 多维张量表示为.

多项式算术(Polynomial Arithmetic): 设是二次幂数, , 给定整系数多项式, 在上的乘积定义如下:

这是基于事实  

基于格的同态加密

Cheetah使用了两种基于格的方案, 即基于LWE和基于RLWE的同态加密方案. 两种方案共享参数: : , 明文模数可不为素数. 以往的方案中通常设定为满足的素数以使用SIMD技术均摊同态乘法的开销, 但是Cheetah不需要使用SIMD，因而不需要是素数.

RLWE同态加密方案的私钥为, 与之关联的公钥为, 其中是均匀随机的, 的系数采样自服从标准差为的离散高斯分布. 设明文为多项式, 则

• 加密:
     
  
  其中的系数采样自, 的系数均匀随机选取自;
• 解密:
    
  

LWE同态加密方案的密钥为向量, 设明文为, 则

• 加密:
    ;
• 解密:
    .

为统一记号, 对所有, 令LWE的密钥为以统一LWE和RLWE密文. 下文中记LWE的加密为.

RLWE方案支持同态加减法、常量积运算以及抽取(extract). 抽取是指, 给定RLWE密文, 可以抽取的第个系数为LWE密钥下的合法密文.

扩展: SIMD的Packing操作

SIMD指的是把一系列数通过中国剩余定理(CRT)打包(pack)到多项式中, 使一次多项式乘法计算可以完成多次明文乘法. 它的计算域必须为素数域. 下面举例说明SIMD中的Packing操作.

• 如何将需要计算的数据编码为多项式?

• 可以表示为个多项式的积:

  

• 例: 设, 多项式阶数, 则
    .

可以表示为个整数: , 即“pack”了.

• 例： 可以表示为和, 即“pack”了和.
• 给定个整数, 可以通过CRT找到对应的来编码它们
• 例: “pack”了和, 因为
    .
• Packing在模上依然保持同态性:
• 加法: “pack”了和, 因为, .
• 乘法: “pack”了和, 因为, , .
• SIMD: 一次多项式运算完成了次整数运算.

Cheetah中没有使用SIMD, 因此不需要为素数. (感谢洪澄老师对SIMD扩展部分的补充)

不经意传输

Cheetah的协议非线性计算依赖于Boyle等人于CCS'19提出的VOLE类型OT协议——Silent OT extension[2], 它通过低通信量、与输入无关的设定以及纯本地计算两个阶段生成大量Random OT correlation, 而Ferret[3]和Silver[4]是Silent OT extension的两个更高效的变种.

线性层的2PC协议

全联接层(FC)、卷积层(CONV)、批标准化层(BN)都可以写成一系列内积的形式. Cheetah的线性协议不需要使用SIMD和同态rotation, 其关键在于观察到对多项式乘法公式(1), 若适当地排列多项式系数, 则可以将其视为一系列内积运算. 为此, Cheetah中针对不同层的功能, 通过构造一对自然映射分别用于排列的输入和权重的多项式系数, 对于任意, 这两个映射是良定义的(well-defined), 这使协议直接接受来自二次幂环的秘密份额输入. 相比之下, 以往的工作仅支持接受来自有限域的秘密份额输入, 为支持接受来自二次幂环的秘密份额输入, 需要借助中国剩余定理将明文模数扩展到大约比特来实现40比特的统计安全性, 导致计算量和通信量增加的倍数.

全联接层(FC层)

FC层输入为向量, 参数为权重矩阵和偏置向量, 输出为向量, 这里的. 因此, FC的核心在于计算矩阵向量乘积, 这可以分解为向量内积运算, 从而可以使用多项式算术来计算. 直观上看, 两个阶为的多项式相乘, 所得结果多项式的阶的系数是两系数向量反序作内积.

设, 定义两个映射: 和:

  

  

其中, , 且的所有其他系数均设为0. 则多项式的乘积的某些系数直接给出了.

性质1: 给定两个多项式, 通过环上的乘积可以对进行求解, 即对于所有, .

证明: 对于每个, 记. 根据公式(1)的定义以及当时, , 我们有

根据性质1，  的系数除了  外，会泄露  的额外信息，为此，Alice还是用抽取函数  从  中抽取所需的系数.

SIMD中把一系列数通过CRT打包(pack)到多项式中, 使一次多项式乘法计算可以完成多次明文乘法, 而Cheetah中则直接把这些数写在多项式系数上, 虽然这样做会导致不能通过一次多项式乘法完成多次明文乘法(多项式相乘后系数会变乱), 但刚好能做卷积, 如图3. (感谢洪澄老师的说明)

若  , 则将权重矩阵切分为子矩阵, 使得, 这里和是只要满足约束, 可自由选取的公开参数. 若或, 则通过Zero padding用0补足, 从而将矩阵乘法转化为更小的矩阵乘法. 具体协议如图2.

复杂度分析: Bob加密并发送了个RLWE密文给Alice. Alice计算了个同态乘法和加法. Alice发送个LWE密文给Bob解密. 可通过优化压缩通信量为比特.

卷积层(CONV层)

上的二维步幅卷积作用在一个步幅为、核为四维张量的三维张量上, 生成三维张量, 其中, 表示卷积中使用的核数, 表示核的尺寸. 从数学的观点来看, 二维步幅卷积可以看作对输出张量的每个位置计算权重和:

首先考虑最简单的情况, 此时输入张量的形状与卷积核相同, 则公式(2)的计算变为逐行逐通道连接和的两个向量的内积. 通常情况下, 可以将二维卷积计算看作一系列个值的内积运算.

设, 定义映射  和  :

  

  

其中, 且和的所有其他系数设为0. 则多项式的乘积的某些系数直接给出了二维卷积的结果. 类似于FC, Alice需要使用抽取函数保护可能的泄漏. 具体协议见图4.

性质2: 给定两个多项式, 卷积公式(2)可以通过环上的多项式乘积来求解, 即对的所有位置, , 其中.

现在考虑大张量情况下的一般情形, 主要做法与FC类似, 仍是需要将大的输入张量和核切分为更小的子块使之适合上的多项式运算, 并对边缘块不足的部分通过Zero padding用零补足.

首先将切分窗口轴坐标分别定义为可自由选择的, 但需满足约束条件: 

  ,

本文中为了最小化Bob发送的密文数量, 选取  使得乘积  最小化, 此时  . 

由于沿  轴上的卷积独立于每个子核, 因而可以将  轴切分为  个组, 每个组包含  个子核. 类似地, 沿  轴上的卷积需要额外的加法, 而同态运算支持加法, 因此我们也可以安全无重叠地沿着  轴进行切分.

当  时, 需要额外关注轴和轴的切分, 以确保步幅窗口不会切分到两个邻近的分区中. 本文中分别将轴切分为块, 将轴切分为块. 对于子块, 包含了从第行开始的的连续行, 从第列开始的的连续列. 举例如图5所示, 当时, 相邻块存在重叠, 虚线部分是Zero padding.

整个卷积层的安全协议完整版如下图11.

复杂度分析: Bob发送了个RLWE密文给Alice, 大约比特. Alice计算了个同态加法和乘法, 并发送个LWE密文给Bob解密. 整个协议的计算复杂度与核大小无关.

批标准化层(BN层)

在DNN中, BN层取三维张量为输入, 参数是缩放向量, 是移位向量, 输出相同形状的三维张量. 对于所有的, 

若将看作大小为的向量, 可以将公式(3)看成标量-向量乘法和向量加法的形式.

于是我们可以通过映射张量的每个通道到多项式以使用标量多项式乘法计算BN, 这会使安全BN协议通信个密文. 为此, 可以通过“堆砌”多通道为单个多项式来降低通信成本.

设, 定义映射: 和:

  

其中, , , 和的所有其他系数均设为0. 如此, 多项式乘积的某些系数给出了公式(3)的乘法部分结果, 即对所有位置, 有

当, 类似于上面的方法, 将切分成形状为的子块, 使得. 由于每个通道在BN计算中都是独立进行的, 因此可以将两个映射直接应用于的子块. 整个协议如下图6:

复杂度分析: Bob加密并发送个RLWE密文给Alice. Alice进行次同态运算. 最后, Alice发送个LWE密文给Bob解密.

非线性函数的2PC优化协议

CrypTFlow2中对非线性计算协议大量应用了IKNP类型OT扩展协议, Cheetah中则使用VOLE类型OT扩展协议来简化和优化CrypTFlow2的非线性计算协议.

本文主要使用, 和. 由于使用的是VOLE类型OT扩展协议, 因此其调用的均摊通信开销几乎为零. 它与CryptTFlow2的对比如下表2, 当和消息长度很小时, 本文的方案有明显优势, 对所有神经网络安全推理中的协议均如此(通常).

百万富翁协议

百万富翁协议即比较协议, 几乎是所有非线性层的核心组件, 如ReLU、截断和池化. Cheetah中的比较协议与CrypTFlow2的主要不同之处在于底层的使用VOLE类型OT扩展协议实现而不是IKNP类型OT扩展协议.

设, 是取和的布尔份额为输入并输出的布尔份额的功能函数, 协议如图12.

首先回顾CrypTFlow2中的比较协议,

1. 每方将各自的比特输入分解为比特小块. 设和分别代表和的第小块. 两方调用两次分别计算  和  ;
2. 两方使用  组合前面的输出, 根据  对深度为  的二叉树进行求值, 其中  .

关于CrypTFlow2中的比较协议更详细的解读可以参考之前文章：

CryptFlow2：实用两方安全推理

CrypTFlow2中对步骤2提出了多种优化方案以分析在IKNP类型OT扩展协议的效率, 例如使用生成两个Beaver三元组和生成关联元组. 然而在Cheetah中, 则使用更高效的生成Beaver三元组. 尽管如此, CrypTFlow2在步骤1中分成比特块求值的方案极大地减少了直接对逐比特生成的深度为的二叉树进行求值的原始方案所使用AND门数量, 表3对三种方案的通信复杂度进行了比较.

下文中, 设代表百万富翁协议, 其中Alice输入为, Bob输入为, 得到的布尔分享份额.

近似截断

在定点数计算中, 截断是乘法计算后的必要步骤.

一比特近似截断

DELPHI[4]、ABY3、SecureML中使用的本地截断的误差来源有两个: 一是当秘密份额之和溢出时造成极大的误差; 二是以1/2的概率造成最后一比特误差. CrypTFlow2中以繁重、faithful截断协议来约束这两种情况. 但本文通过实验发现, 在实际应用中, 当时, 前者造成极大误差这个概率是不可忽略的, 而最后一比特造成的误差实际上不会影响机器学习预测模型的质量[6]. 由于这个原因, 可以移除最后一比特误差的约束来构造更简洁轻量的截断协议, 从而显著降低通信和计算开销.

性质3: 给定无符号比特整数和它的算术分享份额和, 定义. 设是一比特整数0或1, 有.

性质3中的取值实际上与直接相关, 这是导致本地截断大误差的原因. 设表示将的布尔共享份额转化为在上的的算术共享份额, 可通过VOLE类型OT协议实例化的来构造具体协议(与CrypTFlow2的B2A协议相同, 只是OT类型不同, 如下图13). 如此可构造一比特近似截断协议如下图8.

已知符号位的近似截断

当输入的符号位/最高位(MSB)已知时, 可以构造更高效的2PC截断协议. 设已知输入为正, 即其最高位为0, 则的计算可以只调用一次完成, 而不需要借助百万富翁协议, 此时, 如此可构造图9的协议. 类似地, 当最高位为1时, .

通信复杂度分析: 比起CrypTFlow2, Cheetah通信开销更小, 如下表所示.

优化

计算优化

通常BN层放在CONV层或FC层后面. BN融合技术可以将BN操作并入CONV层中, 成为新CONV层, 相比先CONV后BN, 可大大减少计算量. 由于Alice已知BN层和CONV层的权重, 因此可以通过BN融合(fusion)技术来减少的计算. 此外, 通过使用BN融合技术, 还可以节省一个深度的定点数乘法从而减少截断的计算.

通信优化

文章还给出了减少Alice通信开销的两个优化方法, 主要是减少Alice发送的HE密文数量.

1. 若某些LWE密文抽取自相同的RLWE密文, 则这些LWE密文具有相同的向量, 因而Alice可以只发送一次该向量.
2. 来自于对LWE解密算法的观察. 假设Alice需要发送LWE密文给Bob解密, 则Alice只需发送和中元素的某些高位比特给Bob, 并忽略剩下低位到最后的部分, 因为这部分对解密来说是无用的. 具体来说, Alice可以忽略的后比特和中元素的后比特. 可以证明Bob对这样的密文解密失败的几率可忽略不计. 如此Alice可以节省16%~25%的通信开销.

实验

本文的协议可以使用任意VOLE类型的OT扩展协议实现, 本文代码使用的是Ferret的方案[3]. 涉及的开源库有: SEAL, HEXL acceleration, EMP-toolkit. 具体代码已在Github开源: https://github.com/Alibaba-Gemini-Lab/OpenCheetah.

实验环境: 阿里云ecs.c7.2xlarge, 2.70GHz处理器, 16GB RAM.

实验部分主要与CrypTFlow2的开源库进行对比. 实验数据中的通信量是指Alice和Bob的所有信息发送量, 时间是指不同网络设置(LAN/WAN)下的端到端时间, 但两者都不包括一次性设定(如密钥生成和Base-OT)的通信量和时间.

线性协议对比: 计算快约1.3~20倍, 通信开销低1.5~2倍.

非线性函数对比: 单线程下, 本文的所有非线性协议通信开销低10倍以上.

与DELPHI[^5]对比: Cheetah计算快1个量级, 通信低2个量级.

与CrypTFlow2对比: 即使在WAN环境下, Cheetah求解SqueezeNet, ResNet50, DenseNet121耗时不到3分钟. 端到端时间方面, Cheetah比快2~5倍.

与SecureQ8[6]对比: 文章还引入了3PC推理框架SecureQ8进行了对比, LAN下SecureQ8比Cheetah快3~4倍, 但WAN下由于通信较少, Cheetah比SecureQ8快2~3倍.

文章还对近似截断协议的有效性进行了实验, 结果发现对于所有实验图片, Cheetah输出标签向量几乎与相同, 定点数计算的预测准确度也与相应的浮点数计算的预测准确度相匹配, 因此对2PC-NN来说, Cheetah是有效的.

总结

Cheetah提供了一个高度优化的2PC-NN推理架构, WAN设定下, 在不到2.5分钟的时间内对ResNet50模型进行安全推理, 消耗2.3GB的通信量, 非常高效, 适合大规模神经网络训练推理, 是目前最好的2PC-NN工作之一.

总体而言, 本文的亮点有以下几点:

• 卷积和矩阵向量乘法中涉及的同态rotation操作是基于格的HE方案的性能瓶颈之一, 本文通过构造映射巧妙地消除了同态rotation运算, 加快了同态运算的效率;
• 基于HE的协议可以直接接受的秘密份额, 而不局限于, 避免了额外的计算和通信开销;
• 本文使用了基于VOLE类型的OT扩展协议来构造高效、精简的非线性计算协议, 如截断、比较协议等, 极大降低了安全推理的计算和通信开销.

参考文献

[1]Deevashwer Rathee, Mayank Rathee, Nishant Kumar, Nishanth Chandran, Divya Gupta, Aseem Rastogi, and Rahul Sharma. CrypTFlow2: Practical 2-party secure inference. In CCS, pages 325–342. ACM, 2020. 

[2]Elette Boyle,Geoffroy Couteau,Niv Gilboa,Yuval Ishai, Lisa Kohl, Peter Rindal, and Peter Scholl. Efficient two-round OT extension and silent non-interactive secure computation. In CCS, pages 291–308, 2019. 

[3]Kang Yang, Chenkai Weng, Xiao Lan, Jiang Zhang, and Xiao Wang. Ferret: Fast extension for correlated OT with small communication. In CCS, pages 1607–1626, 2020. 

[4]Geoffroy Couteau, Peter Rindal, and Srinivasan Raghuraman. Silver: Silent VOLE and oblivious transfer from hardness of decoding structured LDPC codes. In CRYPTO, pages 502–534, 2021. 

[5]Pratyush Mishra, Ryan Lehmkuhl, Akshayaram Srini- vasan, Wenting Zheng, and Raluca Ada Popa. DELPHI: A cryptographic inference service for neural networks. In USENIX, pages 2505–2522, 2020. 

[6]Anders P. K. Dalskov, Daniel Escudero, and Marcel Keller. Secure evaluation of quantized neural networks. Proc. Priv. Enhancing Technol., 2020(4):355–375, 2020.

译者简介：

往期内容：