Note - HE-Based PPML
Efficient Dropout-resilient Aggregation for Privacy-preserving Machine Learning

本文为基于同态性质的PPML方案的综述,以下为主要参考文献的信息:
Article: Efficient Dropout-resilient Aggregation for Privacy-preserving Machine Learning
Journal: TIFS (IEEE Transactions on Information Forensics and Security)
Author: Ziyao Liu, Jiale Guo, Kwok-Yan Lam, Jun Zhao
Date: AUGUST 2021
1. Background
机器学习是目前信息技术的一个主要方向,其要求数据量巨大的特性造成了对于用户共享数据集的需求。而为了保护用户的数据隐私,隐私保护机器学习(Privacy-preserving Machine Learning, PPML)近年来受到关注。
在大规模机器学习中,用户或设备随时会退出(dropout),本文对此提出了一种可扩展的隐私聚合方案,通过同态伪随机数生成器(Homomorphic Pseudorandom Generator, HPRG)、Shamir秘密共享和数字签名方案,构建了一种PPML方案。该方案的特点包括:
- 动态性:用户或设备可以随时退出;
- 安全性:可抵抗半诚实用户和恶意敌手的攻击;
- 高效性:相较于传统方案(SecAgg)更快。
Compare
以下为以往工作的一些特点:
Article Name | Description |
---|---|
Privacy-preserving stream aggregation with fault tolerance | 阈值HE,高开销的building block,对大规模PPML不现实 |
Privacy-preserving deep learning via additively homomorphic encryption | 比上述高效,但存在梯度泄露 |
Mpc-enabled privacypreserving neural network training against malicious attack | 依靠MPC,DNN的通信开销很大 |
Aby3: A mixed protocol framework for machine learning | 服务器辅助MPC,但对于单个服务器不能保证非共谋性 |
Falcon: Honest-majority maliciously secure framework for private deep learning | 同上 |
Practical secure aggregation for privacy-preserving machine learning | pair-wise DH,抗退出(弹性) |
名词缩写
HE:同态加密;MPC:多方安全计算;DNN:深度神经网络;DH:Diffie-Hellman
2. Protocol
此处会提及两篇文章的内容,为方便下做简称:
- EDRAgg:即本文的主要参考文献,Efficient Dropout-resilient Aggregation for Privacy-preserving Machine Learning
- SecAgg:来自Google的最早的方案,Practical secure aggregation for privacy-preserving machine learning
2.1 Masking Model
首先需要明确我们的目标。在目前的研究中,PPML的底层是由安全聚合协议支持的。在该环境下,我们进行如下的定义:
设存在用户集 $\mathcal{U}$ 和服务器集 $\mathcal{S}$,用户$u_i\in \mathcal{U}$拥有的ML模型参数记作$\boldsymbol{x_i}$,则安全聚合的目标是在不泄露 $\boldsymbol{x_i}$ 的任何信息的情况下,使得服务器获得聚合参数 $\boldsymbol{y} = \sum_{u_i \in \mathcal{U}} \boldsymbol{x_i}$ 。
🤔此处“不泄露”针对的是 $o_j \in \mathcal{U} \cup \mathcal{S} \backslash \{u_i\}$
类似完美安全性,$o_j$在协议前后的视角不变(同分布)
An Example
此处我们考虑两个用户,一个服务器的情况,即 $\mathcal{U} = \{u_1,u_2\}$,$\mathcal{S} = \{s\}$。
此时,想要不泄露任何信息,可让用户对自己的模型参数加上遮罩(mask),再使服务器能够消除遮罩即可。我们将遮罩记作$\boldsymbol{r_i}$,则有:
$$ \boldsymbol{y_i} = \boldsymbol{x_i} + \boldsymbol{r_i} $$
于是对于两个用户的情况如下图所示,此处$r_i$为随机选取的随机数:

此时,只需要服务器能过获得$\sum \boldsymbol{r} =\boldsymbol{r_1} + \boldsymbol{r_2}$,就可以消除遮罩,但显然这又变成了一个安全聚合问题。此时一个巧妙的方法是让$\sum \boldsymbol{r} =0$,即$\boldsymbol{r_1} =- \boldsymbol{r_2}$,对于该情况,可以让$u_1$向$u_2$发送$\boldsymbol{r_1}$,如图:

此时,$\boldsymbol{y_1}+\boldsymbol{y_2}$恰为$\boldsymbol{x_1}+\boldsymbol{x_2}$,且服务器从$\boldsymbol{y_1},\boldsymbol{y_2}$不能获得与$\boldsymbol{x_1},\boldsymbol{x_2}$相关的任何信息。
但随之而来,会发现有一个问题,由于$u_2$从$u_1$处获得了$\boldsymbol{r_1}$,如果$u_2$和服务器$s$共谋,则可以还原$\boldsymbol{x_1}=\boldsymbol{y_1}-\boldsymbol{r_1}$,从而导致$u_1$的ML模型参数泄露。有什么方法可以让$u_1,u_2$双方共享一个数,并且不能被别人获取呢?此处就需要引入SecAgg的工作,巧妙利用Diffie-Hellman密钥交换算法来完成目标。
此处我们省去关于DH密码学原语的详细说明,观察下图不难发现DH天然的给出了一个双方共享的数$g^{ab}$,且由于计算该数$g^{ab}=(g^a)^b=(g^b)^a$,要求一方的公钥和另一方的私钥,不会把信息泄露给第三方。

这就得到了一个基于DH的安全聚合方法(作者称该过程为 pair-wise DH)。
Further Example, More Users
我们进一步扩展用户集的数量至3人,该方法是否还可行呢?

我们可以从$u_1$的视角考虑:

用户$u_1$除了自己的私钥$a$外,还可以得知$u_1,u_2,u_3$的公钥$g^a,g^b,g^c$,于是相关可计算$g^{ab},g^{ac}$。我们不妨使$u_1$的mask恰为$r_1=g^{ab}+g^{ac}$,那么与之对应在计算$u_2$的mask时,由于需要和$g^{ab}$配对相消,使之为$r_2=-g^{ab}+g^{bc}$,$u_3$同理,如图所示。

不难归纳出该方法的计算公式: $$ y_i=x_i+\sum_{i<j}g^{sk_isk_j}-\sum_{i>j}g^{sk_isk_j} $$ 则显然: $$ y=\sum_{u_i\in\mathcal{U}}{y_i}=\sum_{u_i\in\mathcal{U}}{\left(x_i+\sum_{i<j}g^{sk_isk_j}-\sum_{i>j}g^{sk_isk_j}\right)}=\sum_{u_i\in\mathcal{U}}{x} $$
Another Method
(待更新……)
2.2 Security Analysis
(待更新……)
3. Summary
(待更新……)