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 NameDescription
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 learningpair-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}$,如图:

image-20220728081126187

此时,$\boldsymbol{y_1}+\boldsymbol{y_2}$恰为$\boldsymbol{x_1}+\boldsymbol{x_2}$,且服务器从$\boldsymbol{y_1},\boldsymbol{y_2}$不能获得与$\boldsymbol{x_1},\boldsymbol{x_2}$相关的任何信息。

需注意的是,此处要求$len(\boldsymbol{r_i})\geq len(\boldsymbol{x_i})$,即满足One-time Pad,具有完美安全性。

但随之而来,会发现有一个问题,由于$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$,要求一方的公钥和另一方的私钥,不会把信息泄露给第三方。

image-20220728082043225

这就得到了一个基于DH的安全聚合方法(作者称该过程为 pair-wise DH)。

由于显然存在可逆映射$F:\mathbb{Z}_p^k\rightarrow \mathbb{Z}_p$将参数向量降维,此处将$\boldsymbol{r_i}$ 规约到 $\mathbb{Z}_p$上,下同理。

Further Example, More Users

我们进一步扩展用户集的数量至3人,该方法是否还可行呢?

image-20220728082623247

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

image-20220728082755491

用户$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$同理,如图所示。

image-20220728083114276

不难归纳出该方法的计算公式: $$ 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
Luminol Chen
2024 Undergraduate in Cyberspace Security

My research interests include cryptography and blochchain.