SWIFT 超快速鲁棒隐私保护机器学习

SWIFT: Super-fast and Robust Privacy-Preserving Machine Learning

今天给大家带来的是发表于USENIX Security'21的文章SWIFT: Super-fast and Robust Privacy-Preserving Machine Learning, 原文链接如下: https://arxiv.org/abs/2005.10296.

Abstract

SWIFT是一个环上基于秘密共享的高效、恶意安全的3PC/4PC隐私保护机器学习框架, 在诚实大多数设定中(至多只有一个恶意服务器)实现了输出可达性(GOD), 非常适用于安全外包计算(SOC)范式, 能让用户积极参与计算而不需担心拒绝服务. SWIFT与BLAZE一样快, 但后者只实现了公平性. 当SWIFT从三方扩展到四方时, 与4PC具备公平性的Trident一样快, 且比4PC具备鲁棒的FLASH框架快2倍. 在WAN环境中计算域为的情况下, 文章对流行的ML算法和DNN进行了基准测试, 证明了SWIFT的实用性. 对于DNN, 实验结果证明本文的方案提升了安全性保障, 不会为3PC带来额外开销, 同时还为4PC提升了2倍性能.

Introduction

只实现中止安全性的MPC协议不能满足安全外包计算的要求, 因为用户可能无法获得输出, 导致用户的参与度降低, 因此实现输出可达性/鲁棒性的MPC协议对安全外包计算来说是至关重要的. 为了提高效率, 许多PPML方案采用了offline-online范式来设计MPC协议. 此外, 为了进一步提升效率, 充分利用CPU架构的特性, 多数MPC方案的计算域都建立在二次幂环上, 如等.

总的来说, 本文的主要贡献如下:

1. 鲁棒的3PC/4PC框架: SWIFT的3PC框架的亮点之一是鲁棒的点积协议的(均摊)通信成本与向量大小无关. 对于不同的组件, SWIFT与只实现公平性(Fairness)的BLAZE在通信量、通信轮次等方面的比较见表1.
2. SWIFT的PPML模块可用于LR, SVM, BNN的训练和推理.
3. SWIFT实现GOD的关键在于本文引入的联合消息传递(Joint Message Passing, JMP)原语, 它允许两个服务器将其共有的消息中继(relay)给第三个服务器验证消息的一致性, 要么中继成功, 要么识别出诚实计算的服务器, 然后诚实服务器作为可信第三方(TTP)来完成明文计算.
   为重构协议引入了一个超快的在线阶段, 通信轮次比BLAZE提升了4倍.

Preliminaries

服务器代理模式, 静态恶意敌手至多腐化一个计算服务器, 仅在3PC的情况下存在一个广播信道. 服务器之间通过一次性密钥设定生成用于PRF的预分享随机密钥, 用于生成相关随机性.

计算域: 布尔域, 算术环为, 数据长度为bits, 精度bits, 整数部分长度为bits.

符号说明: 为向量的第个元素. 对于长为的数, 表示第个位置的比特. 对于比特, 记为它在二次幂环上的等价取值, 即, 其余比特位置为0. 参与方集合记为.

Robust 3PC and PPML

Secret Sharing Semantics

文章中使用了如下三种分享语义:

• -sharing: 两方下的加法秘密共享, 秘密, 持有, .
• -sharing: 三方下的复制秘密共享, 秘密, 拥有.
• -sharing: 三方下的复制秘密共享, 设秘密为, 分别持有的份额, 存在, , 持有, 持有, 其中. 在这个分享语义中, 任意一方无法重构, 但任意两方可以.

以上三种秘密共享方案都满足线性性, 因此, 它们的加法和常量积的计算是非交互的.

Joint Message Passing primitive

引入的联合消息传递(Joint Message Passing, JMP)原语允许两个服务器将其共有的消息中继(relay)给第三个服务器验证消息的一致性, 要么中继验证成功, 要么识别出诚实计算的服务器, 然后, 将诚实服务器作为可信第三方(TTP)来完成相关计算(明文计算). 在均摊意义下, JMP对于一个个元素的消息, 只产生个元素的通信.

对于, 将, 作为不一致标志比特. 当收到不一致的消息对时, 设定, 并将发送给, 由这两方通过交换不一致标志比特相互进行交叉检验, 若从收到的或者从其他发送方接收到的比特为1, 则这两方将自己的不一致标志比特设定为1. 当服务器的不一致标志比特为1时, 服务器会广播值的Hash结果. 的值来自它从接收到的值. 接下来按照具体协议来选出合适的服务器当做TTP, 三方下JMP的理想功能如图1, 协议如图2. 容易验证协议是正确的. 下文中为简便起见, 称 jmp-send  给, 是指调用.

为均摊通信开销, 实际应用协议时, JMP的发送阶段随协议调用而执行, 而验证阶段在协议的所有结束后进行, 通过组合验证的方式可让验证只需执行一次. 当验证不通过时则通过TTP的帮助来完成相关计算. JMP的通信1轮, 均摊通信量为比特.

3PC Protocols

Sharing Protocol

Sharing Protocol : 允许生成秘密的份额. 该协议预处理阶段不需交互, 在线阶段需要2轮通信, 均摊通信量为比特.

Joint Sharing Protocol

Joint Sharing Protocol : 允许联合生成它们的共同秘密的份额. 该协议预处理阶段不许交互, 在线阶段需要1轮通信, 均摊通信量为比特.

特别地, 当知道预处理阶段的时, 可以不需要交互: 随机采样, 然后本地按照表2约定他们各自的份额.

Multiplication Protocol

Multiplication Protocol : 给定, 允许计算得到的份额.

首先给出半诚实安全下的乘法协议(与BLAZE相同): 在预处理阶段, 随机选取, 随机选取, 随机选取. 本地计算, 并为生成相同的份额. 对于, 在线阶段本地计算  , 并互相交换重构. 然后发送给, 完成半诚实安全的协议. 协议的正确性在于如下等式

与BLAZE类似, 在恶意安全下, 需要考虑如下几个问题:

问题1. 当被腐化时, 所计算的;

问题2. 当或被腐化时, 可能发送错误的份额给另一方, 导致重构的是错误的;

问题3. 当被腐化时, 在线阶段发送给的可能是不正确的.

BLAZE中的恶意安全的乘法方案仅是中止安全的(Security with abort), 在SWIFT中处理方式与BLAZE不同.

对于问题3, SWIFT框架在计算后, 通过 jmp-send 给来解决.

对于问题2, 我们首先介绍BLAZE中的处理方式. 在BLAZE中, 让基于计算进行验证. 令, 通过可以计算如下等式:

若可以得到, 则它可以发给和, 由和通过计算来验证的正确性. 但当是腐化方时, 让得到是不安全的. 为此, 通过关联随机性共同选取随机数作为茫化因子, 然后令. 此时让得到的是, 然后计算验证的正确性. 接下来, 如何确保在诚实时计算了正确的? BLAZE将该问题规约到一个Beaver triple. 注意到对于, 可以本地计算, 其中由两方通过关联随机性生成. 为了验证正确计算了正确的, 我们可以利用如下关系: 若满足, 当且仅当正确计算了. 这是因为

于是, 的正确性规约到是否为Beaver triple.

对于问题1, 仍可通过规约到判断Beaver triple的方案来解决, 这是因为若的份额为, 则.

现在回到SWIFT的解决方案中. 首先, SWIFT不依赖于验证信息, 如此当被腐化时协议不会中止. 与直接让得到不同,  在SWIFT中让得到, 得到, 然后通过jmp-send发送给第三方服务器计算.  由于每个参与方集合中至少存在一个诚实参与方, 因此可确保是正确的, 直接用它来计算.  SWIFT中定义

显然, 给定, 和可以计算  . 但还需要解决如下两个问题:

(1) 如何让得到?

(2) 如何从Beaver triple中提取?

类似于BLAZE的方法, 若  ,  是Beaver triple当且仅当和是正确的. 这是因为

在预处理阶段中通过使用乘法协议计算上述triple并从的份额中提取的必然是正确的. 具体而言, (a) 服务器本地得到的-份额, 如表3; (b) 服务器计算的-份额, 表示为, 通过使用高效鲁棒的三方乘法协议(图6); (c) 服务器本地提取所需的预处理数据:

将这部分转换为份额的鲁棒乘法协议不需要任何通信, 因为(a)和(c)都是本地计算, 通信开销规约到单次执行乘法协议的开销. 

根据-sharing, 得到, 进而得到. 类似地, 得到, 进而得到. 最后, 得到, 进而可以计算.  这样两个问题都解决了. 完整的乘法协议见图5. 预处理阶段的均摊通信开销为1轮, 比特, 在线阶段的均摊开销为比特. 

Reconstruction Protocol

Reconstruction Protocol : 允许服务器鲁棒地从份额  重构秘密 . 重构协议主要使用了承诺. 通信轮次为1, 通信量为  比特.

The Complete 3PC Protocol

使用以上子协议实现GOD的3PC协议如下. 总的来说, 如果某个参与方存在任何恶意行为, 协议都能通过jmp选出一个TTP, 所有参与方将输入发给TTP进行明文计算. SWIFT证明的是标准的real-ideal world-based Security, 因为FaF安全的鲁棒3PC协议已经被证明是不可能实现的.

Building Blocks for PPML using 3PC

Input Sharing and Output Reconstruction in SOC Setting

Input Sharing Protocol : 在SOC场景下允许用户三个服务器之间生成秘密输入  的 -sharing的份额.

Output Reconstruction Protocol : 在SOC场景下允许服务器向用户重构秘密 .

在以上协议中, 若某处确定了TTP, 则服务器将通知用户TTP身份, 用户将明文形式的输入发送给TTP进行计算函数输出, 然后将结果返回给用户.

MSB Extraction

MSB Extraction Protocol : 给定  的算术分享 , 协议允许服务器计算  的最高有效位的布尔分享. SWIFT使用了ABY3的优化的2-输入并行前缀加法器布尔电路[optimized 2-input Parallel Prefix Adder (PPA) boolean circuit]. PPA电路由  个AND门和  的乘法深度.

令 , 则 . 服务器首先根据表4本地计算  的每个比特相应的布尔分享. ABY3中将  表示为 , 其中  , 这里的  代表一个全加电路,  代表比特的和,  代表进位比特.  总之, 服务器并行运行  次  来计算 .  是独立运行的, 需要1轮通信, 使用优化后的FFA电路计算最终结果为 .

 在预处理阶段需要的通信量为  比特, 通信轮次为  轮, 在线阶段均摊通信量为  比特.

Bit to Arithmetic Conversion

Bit to Arithmetic Conversion Protocol : 给定比特  的布尔分享 , 该协议允许服务器计算算术分享 . 和BLAZE一样, 原理是先在预处理阶段生成  , 然后在线阶段计算  . 具体协议如下图. 该协议预处理阶段的均摊通信量为  比特, 在线阶段需要1轮,  比特通信量.

Bit Injection

Bit Injection Protocol : 给定比特  的二进制分享  和  的算术分享 , 该协议计算 . 原理是先通过  将  转换为 , 然后再通过  计算 . 预处理阶段均摊通信量为  比特, 在线阶段需要2轮, 均摊通信量为  比特.

Dot Product

Dot Product Protocol : 给定长度为  的向量  和 , 协议允许服务器鲁棒地生成  的 -sharing份额 .  SWIFT中借鉴了BLAZE的方法, 使得协议在线阶段的通信量与向量长度  无关.

 是形式为  的  个并行乘法, 再将结果累加在一起. 令 , 则

其中  .

点积协议的在线阶段处理方式与乘法协议类似.  本地计算  并通过jmp-send发送给 . 类似地,  本地计算  并通过jmp-send发送给 . 然后  和  重构  并计算  . 最后,  通过jmp-send发送  给 .

下面介绍如何通过黑盒(black-box)方式在预处理阶段让服务器获得点积协议所需的 .

令 , 其中   , 如此

其中  .

使用以上关系, 预处理阶段的处理方式如下:  随机选取 ,  随机选取 ,  随机选取 . 服务器类似于乘法协议一样准备 , 并将其作为图12的鲁棒3PC点积协议  的输入, 计算 , 这里的 . 给定 ,  和  的提取方式如下:

如此根据 -sharing语义,  可以得到 , 进而得到 , 同时  均可得到  进而得到 ,  均可得到  进而得到 .

完整的点积计算协议如下图11. 预处理阶段的均摊通信量为  比特, 在线阶段需要1轮, 均摊通信量为  比特.

对于图12的具体协议, SWIFT中通过半诚实点积协议进行实例化, 并在验证阶段验证正确性, 通过适当地设定验证阶段参数可以给出一个均摊通信成本与向量长度几乎无关的 . 见文章的附录B.

Truncation

在定点数表示形式下进行乘法运算需要考虑截断问题, 设定点精度为 . 与ABY3的截断方案类似, 服务器运行  协议生成截断对 , 其中  是随机环元素,  是  的截断结果, 即 . 给定 , 要截断的值 , 截断结果表示为 . 为了从  的布尔分享中获得算术分享, 与ABY3需要多轮通信的方法不同, SWIFT中使用的是Trident中的方案,  实现布尔分享到算术分享的隐式转换只需2个点积运算的开销.

下面介绍如何生成所需的截断对 .  随机采样 ,  随机采样 . 设  的第  比特表示为 , 定义 , 则  . 更进一步地, 有

类似地, 对于 , 有

服务器通过表2的形式非交互生成  的每个比特的算术  份额. 然后执行两次  计算  的份额  和  的份额 . 然后服务器各自根据以上两条等式本地计算  的  份额.

然而服务器需要的并非  份额而是  份额. 将  份额本地转换为  份额的方式如下: 设  是  份额的相应参数. 因为  知道明文的  和 , 因此可以本地计算 . 然后  令 ,  令 .

整个  协议如下, 均摊通信量为  比特.

Dot Product with Truncation

Dot Product with Truncation Protocol : 允许服务器对点积计算结果  进行截断得到 .  SWIFT中使用了BLAZE中相应的优化方案. 预处理阶段的均摊通信量为  比特, 在线阶段需要1轮,  比特的均摊通信量.

Secure Comparison

在FPA表示法下两数比较大小只需通过  协议提取两数差值的最高有效位.

Activation Functions

• ReLU函数: , 其中 , 反之 . 因此关键在于抽取  的符号位, 在  形式下可以通过  协议生成 . 而  可以令  本地计算求得. 最后将  作为输入执行一次  协议即得. 预处理阶段均摊通信量为  比特, 在线阶段需要  轮, 均摊通信量为  比特.
• Sigmoid函数: 与SecureML相同, SWIFT通过分段函数来替代Sigmoid函数, 此时 , 其中 , . 通过ReLU函数的方法来求解. 预处理阶段均摊通信量为  比特, 在线阶段需要  轮, 均摊通信量为  比特.

Maxpool, Matrix Operations and Convolutions

• Maxpool: 计算长度为  的向量  中的最大值. 两两成对进行比较, 并使用  协议更新最大值.
• 矩阵乘法: 转化为点积计算.
• 卷积计算: 与SecureNN相同, 可以转化为矩阵乘法的计算.

Robust 4PC and PPML

SWIFT将3PC扩展到4PC, 不再需要调用广播, 点积计算与向量长度无关, 高效的主要原因是4PC的鲁棒JMP4原语 . 由于4PC的实现原理多数与3PC类似, 因此下面除不同之处外, 不再展开.

4PC Secret Sharing Semantics

扩展到4PC的 -sharing: 对于秘密 ,  的份额为 ,  的份额为 ,  的份额为 ,  的份额为 . 易见,  的份额与3PC下的份额相同.

4PC Joint Message Passing Primitive

 原语允许  发送消息对  给 , 当  收到的信息不一致时, 设定不一致标志比特为1, 将服务器  作为TTP再进行相关明文计算. 称  通过jmp4-send发送  给  是指调用 . 该原语比FLASH提出的双向传输(bi-convery)方案快2倍. 具体协议见图16, 在线阶段需要1轮, 均摊通信量为  比特.

4PC Protocols

Sharing Protocol

Sharing Protocol : 在线阶段需要2轮, 当  分享秘密时, 均摊通信量为  比特; 当  需要分享秘密时, 均摊通信量为  比特.

Joint Sharing Protocol

Joint Sharing Protocol : 允许服务器  联合生成 , 其中  是  的共同秘密. 当发现信息存在不一致时, 将没有进行计算的那个服务器选为TTP. 在线阶段, 需要1轮, 当  分享时, 均摊通信量为  比特. 其他情况的均摊通信量为  比特.

特别地, 若  是  的共同秘密, 那么不需交互即可生成  份额: 令 .

若  是  的共同秘密, 那么可以只通信1个元素:  选取随机数 , 令 ;  约定 , 然后jmp4-send发送  给 .

-sharing Protocol

某些情况下,  需要在预处理阶段生成  的 -sharing, 其中 ,  持有 ,  持有 ,  持有 , 而  则有 . 具体协议  如下图19, 需要2轮, 均摊通信量为  比特.

此外, 服务器可以本地将  转换为 , 只需按照下表5的方式约定他们的份额即可. 此时,   .

Multiplication Protocol

4PC下 -sharing的乘法协议 . 预处理阶段需要  比特的均摊通信量, 在线阶段需要1轮,  比特的均摊通信量.

4PC下给定 , 鲁棒地重构  的协议 . 因为每个服务器都只缺少一个份额即可重构, 而该缺失份额其他三个服务器都有, 因此这三个服务器中的其中两个发送该缺失份额, 第三个发送该份额的Hash值以进行一致性检查. 与3PC下的乘法协议相比, 4PC下的乘法协议不需要使用承诺方案. 在线阶段需要1轮, 均摊通信量为  比特.

Building Blocks for PPML using 4PC

Input Sharing and Output Reconstruction in SOC Setting

下面将SOC场景中的3PC的输入分享和输出重构协议扩展到4PC. 其核心在于使用了拜占庭协定(Byzantine agreement, BA).

为了生成用户的输入  的 -sharing份额 , 用户从四个服务器中的三个中接收 , 以及  共同选取的随机数 , 接受其中大多数的那个 . 用户本地计算 , 并发送  给所有服务器. 服务器执行两轮拜占庭协定接受  或者 .

拜占庭协定过程如下: 设  接收到的来自用户的值为 , 为达成协定, 服务器首先就  收到  达成一致, 为此,  首先发送  给所有服务器, 而这只需  互相交换 , 然后每个  从接收到的  的三个版本中选择最多的那个版本的  即可, 这由诚实大多数假设保证. 一旦协定完成, 每个服务器都将  中的占大多数的那个选为它们从用户接收到的值; 若没有任何一个出现占大多数, 那么就选择一个默认值.

BA完成后,  从  中本地计算 , 同时  从  中本地计算 . 对于  的重构, 服务器发送它们的  份额给用户, 用户选取每个份额中的占大多数的值重构输出. 在任何情况下, 如果协议识别出了TTP, 则所有服务器发送它们的份额给TTP, 由TTP选取每个份额中的占大多数的值计算功能函数的输出, 并把输出发给用户.  用户也从所有服务器中接收TTP的身份, 并接受来自占大多数的TTP的输出.

Bit Extraction Protocol

4PC下的比特抽取协议 : 为计算4PC下  的最高有效位的布尔分享 , SWIFT仍使用了ABY3中优化的并行前缀加法器电路[Optimized Parallel Prefix Adder (PPA) circuit]方案. 因为  表示为 , 因此该电路的两个输入分别为  的布尔分享 .  拥有 , 可以通过  协议生成 . 同理,  生成 . 于是通过优化的电路, 可计算出 . 该协议预处理阶段的均摊通信量为  比特, 在线阶段需要1轮, 均摊通信量为  比特.

Bit2A Protocol

4PC下的布尔分享与算术分享转换协议 , 与3PC下的相比, 4PC下的原理在于:

设 , 则

 的预处理阶段均摊通信量为  比特, 在线阶段需要1轮, 均摊通信量为  比特.

Bit Injection Protocol

比特映射协议 : 给定比特  的布尔分享  和  的算术分享 , 计算 .

简单的方法是先把  通过  转化为 , 然后通过乘法协议  计算 . 下面介绍一种减少预处理阶段和在线阶段通信量的方法.

记 , 注意到

其中,   .

具体协议如下图, 预处理阶段均摊通信量为  比特, 在线阶段需要1轮, 均摊通信量为  比特.

Dot Product

4PC下的点积协议 . 预处理阶段需要  比特的均摊通信量, 在线阶段需要1轮,  比特的均摊通信量.

Truncation

4PC下的截断对生成协议 . 在线阶段需要1轮,  比特的均摊通信量.

Dot Product with Truncation

4PC下的点积截断协议 . 预处理阶段需要  比特的均摊通信量, 在线阶段需要1轮,  比特的均摊通信量.

Activation Functions

• ReLU函数计算: 预处理阶段均摊通信量为  比特, 在线阶段需要  轮, 均摊通信量为  比特.
• Sigmoid函数: 预处理阶段均摊通信量为  比特, 在线阶段需要  轮, 均摊通信量为  比特.

Experiment

Logistic Regression

NN Inference

Conclusion

本文提出了一个高效PPML框架SWIFT, 实现了输出可达性(GOD)的最强安全属性，其中3PC协议基于BLAZE且实现GOD而无额外开销. 4PC协议基于实现GOD的FLASH和实现Fairness的Trident. SWIFT框架能实现GOD的关键在于文章所引入的Joint message passing原语，若发现信息不一致，则会选出一个必为诚实参与方的TTP进行明文计算. 本文中所构造协议的预处理和在线阶段的通信量都是常数. 此外, SWIFT中认为Fantastic Four中提出的Privacy Robustness概念(对诚实方仍保持输入隐私性)和本文中的Robustness概念并无差别, 因为SWIFT中认为隐私性仅对恶意敌手, 而没有必要对诚实方保持隐私性.

References

[1] A. Patra and A. Suresh. BLAZE: Blazing Fast Privacy-Preserving Machine Learning. NDSS, 2020.

[2] A. Dalskov, D. Escudero, and M. Keller. Fantastic Four: Honest-Majority Four-Party Secure Computation With Malicious Security. USENIX, 2021.

[3] H. Chaudhari, R. Rachuri, and A. Suresh. Trident: Efficient 4PC Framework for Privacy Preserving Machine Learning. NDSS, 2020.

[4] M. Byali, H. Chaudhari, A. Patra, and A. Suresh. FLASH: fast and robust framework for privacy-preserving machine learning. PETS, 2020.

[5] B. Alon, E. Omri, and A. Paskin-Cherniavsky. MPC with Friends and Foes. CRYPTO, 2020.

译者简介：

魏伟明, 应用数学硕士, 目前在广州大学数学与信息科学学院攻读博士学位, 主要研究方向为: 安全多方计算在隐私保护机器学习领域中的应用. 知乎: @云中雨雾.

往期内容：

欢迎投稿

邮箱：[e-mail]

参与更多讨论，请添加小编微信加入交流群