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
（待更新……）
Luminol Chen
2024 Undergraduate in Cyberspace Security
My research interests include cryptography and blochchain.