Kunkun

Kunkun

CS & Applied Math & MPC @ GZU | Phd

Reading Falcon Note 1

3 minute read

Published:

诚实方占多数的恶意安全模型下Secure Deep Learning框架

1. 基本思想

Falcon设计了一个三方安全计算的机器学习框架。三方主要包括数据拥有者(data holder, DH)，需要机器学习服务的查询用户(query users, Users)和提供机器学习服务的计算服务器(computing servers, Server). Falcon框架包括两个阶段：训练阶段和推导阶段。训练阶段由DH提供数据，Server计算出机器学习模型；推导阶段User向Server发出查询请求，Server提供一个训练模型。DH把数据用重秘密共享(Replicated secret sharing)方式把数据分布到不同3个服务器上。三个服务器利用这些共享数据训练出各自不同神经网络模块，用户此时可以提交查询，并得到模型的秘密分块。用户通过重构这些秘密分块重构出完整的训练模型。这种方式的优点是，因为服务器只有秘密分块，因此DH的数据对三个服务器都是完全隐私的，Users的查询请求也对服务器也是保密的。Falcon使用安全多方计算设计协议。安全性满足恶意安全，如果一方是恶意腐败的(corruption)，协议能够保证有正确的输出或者终止协议的恶意行为，不会输出错误的结果。同时文章也是开源的。同时文章也对不同的机器学习安全多方计算协议进行比较，如下图。 falcon多方计算比较图

2. 算子

ABY3依赖于高效进GC计算非线性函数，不同于简单的模数计算。

相关随机性 文章利用用\(\text{PRF}\)(伪随机函数)设计两个基本的随机数生成器。$(3,3)$随机性，即各方随机生成\(\alpha_i\)，使得\(\alpha_1 + \alpha_2 + \alpha_3 = 0\)。$(2,3)$随机性，即各方随机生成\((\alpha_i, \alpha_{i+1})\)，使得\(\alpha_1 + \alpha_2 + \alpha_3 = 0\)。给定一个$P_i$和$P_{i+1}$之间的随机密钥$k_i$，令\(\mathsf{cnt}\) 是每次调用后递增的计数器。

初始化 $P_i$选择一个随机种子$k_i$，并把它发送给$P_{i+1}$。 一般随机性：令$F$是一个PRNG(伪随机数生成器)

  • $ \alpha_i = F_{k_i}(\mathsf{cnt}) - F_{k_{i-1}}(\mathsf{cnt}),\; \mathsf{cnt}++ $
  • $ (\alpha_i, \alpha_{i-1}) = (F_{k_i}(\mathsf{cnt}), F_{k_{i-1}}(\mathsf{cnt})),\; \mathsf{cnt}++ $

截断数对：\([\![ r]\!], [\![ r^\prime]\!] = [\![ r / 2^d]\!]\)

关联隐私比较随机性：

  • 随机取样比特\([\![ b]\!]^2\)
  • 利用位插入\([\![ b]\!]^2 \rightarrow [\![ b]\!]^p\)
  • 随机取值$m_1, \cdots, m_k \in \mathbb{Z}_p$
  • 计算并公开\(m^{p-1}_1, \cdots, m^{p-1}_k\)
  • 移除为0，留下为1的值，设置一个大的$k$值，均摊开销提高效率，共计\(\lceil \log_2 p \rceil\)轮。

关联封装函数随机性：

  • 随机取样比特\([\![ r_i ]\!]^2, \; i \in [l]\)
  • 执行位分解得到\([\![ r_i ]\!]^L\)
  • 执行位插入\([\![ r_i ]\!]^2 \rightarrow [\![ r_i ]\!]^p\)
  • 利用全加器计算最终进位

关联ReLU随机性：

  • 随机取样比特\([\![ b]\!]^2\)
  • 利用位插入\([\![ b]\!]^2 \rightarrow [\![ b]\!]^L\)

线性操作 令$a,b,c$是公共参数，\([\![ x ]\!]^m\) 和 \([\![ y ]\!]^m\)是秘密共享，各方在本地计算

  • \([\![ ax + by + c ]\!]^m := (ax_1 + by_1 + c, ax_2 + by_2, ax_3 + by_3)\)。

乘法 要使两个秘密共享相乘\([\![ x ]\!]^m = (x_1, x_2, x_3)\) 和 \([\![ y ]\!]^m = (y_1, y_2, y_3)\)

  • 各方本地计算\(z_1 = x_1y_1+x_2y_1+x_1y_2, z_2 = x_2y_2+x_3y_2+x_2y_3, z_3 = x_3y_3+x_1y_3+x_3y_1\)
  • 由$z_1, z_2, z_3$形成$(3,3)$门限共享\([\![ z=x \cdot y ]\!]^m\)
  • 各方执行重共享协议，利用$(3,3)$随机性生成$(2,3)$门限共享，即第$i$方发送\(\alpha_i + z_i\) 给第$i-1$方，${\alpha_i }$形成$(3,3)$零共享。

重构\([\![ x ]\!]^m\)

  • 半诚实模型中，每方发送一个环元素给下一方，即$P_i$ 发送共享$x_i$ 给$P_{i+1}$
  • 恶意模型中，第$i$方发送共享$x_i$给$P_{i+1}$，再发送共享$x_{i+1}$给$P_{i-1}$，若两个值不同，则中止协议。此轮协议是单轮通信。

秘密共享 输入两个随机共享\([\![ x ]\!]^L\) 和 \([\![ y ]\!]^L\)，一个随机比特\([\![ b ]\!]^2\)，通过判断$ b = 0 \; \text{or} \; 1 $输出\([\![ Z ]\!]^L = [\![ x ]\!]^L \; \text{or} \; [\![ y ]\!]^L\)。

  • 获取共享随机比特\([\![ c ]\!]^2\)，预计算\([\![ c ]\!]^L\)
  • 公布比特\((b \oplus c) = e\)，若$e = 1$，设置\([\![ d ]\!]^L = [\![ 1 - c ]\!]^L\)；若$e = 0$，设置\([\![ d ]\!]^L = [\![ c ]\!]^L\)
  • 计算\([\![ z ]\!]^L = [\![ (y-x) \cdot d ]\!]^L + [\![ x ]\!]^L\)，其中用乘法协议计算\([\![ (y-x) \cdot d ]\!]^L\)

与公开位$b$异或 给定共享比特\([\![ x ]\!]^m\)和一个公开位$b$

  • 各方在本地计算共享比特\([\![ y ]\!]^m = [\![ x \oplus b ]\!]^m\)，注意到$ y = x+b-2b \cdot x $
  • b是公开的，这属于线性运算，在半诚实和恶意的对手模型中都能计算。

从\([\![ x ]\!]^m\)到\([\![ \beta ]\!]^m\)估计\([\![ (-1)^\beta \cdot x ]\!]^m\) 令\(\beta \in \{0,1 \}\)，执行乘法协议获得\([\![ (1-2\beta)\cdot x ]\!]^m = [\![ (-1)^\beta \cdot x ]\!]^m\)

3. 隐私比较

各方持有\(\mathbb{Z}_p\)中的共享比特$x$和公开值$r$，计算$ x \ge r$。协议如下图 隐私比较 在协议中需要用随机比特\(\beta\)盲化，若没有这一步，\(\beta ^ \prime\)将会泄露输出$ (x \leq r) $的信息。每一位的比特都是相对独立，单个盲化比特位\(\beta\)隐藏\((x \ge r) \; \text{or} \; (r > x)\)的计算。该协议将简单模块算法与恶意安全模型相结合。 根据协议看到：

  • 步骤2表示通过估计\(2\beta-1\)共享计算$u[i]$，再计算$ (2\beta - 1)(x[i] - r[i]) $，调用乘法协议在一轮交互通信完成
  • 步骤3、4是本地简单的计算，比如\([\![ w[i] ]\!] = (w[i]_1, w[i]_2, w[i]_3)\)能用\(w[i]_j = x[i]_j + \delta_{j1}[i] - 2r[i]x[i]_j\)计算，这里$ j \in {1, 2, 3}$, \(\delta_{ij}\) 是克罗内克函数(Kronecker delta function)，即$i=j, \; \delta_{ij}=1$，否则$\delta_{ij}=0$
  • 步骤6用连续调用较小字符串的乘法协议，在\(\log_2l+1\)计算随机盲化因子，故多出1轮通信
  • 步骤7、8在本地计算
4.Warp函数ReLU和DReLU

文章定义Warp函数来计算比较。wrap 函数定义 \(\mathsf{wrap}_2\) 和 \(\mathsf{wrap}_3\) 为各方秘密份额的函数，并在将共享看作整数并相加，有效地计算“进位比特”。

\[\mathsf{warp}_2(a_1, a_2, L)= \begin{cases} 0 & \text{if}\; a_1 + a_2 < L \\ 1 & \text{Otherwise} \end{cases}\]

\(\mathsf{warp}_{3e}(a_1, a_2, a_3, L)= \begin{cases} 0 & \text{if} \; \sum^3_{i=1}a_i < L \\ 1 & \text{if} \; L \leq \sum^3_{i=1}a_i < 2L \\ 2 & \text{if} \; 2L \leq \sum^3_{i=1}a_i < 3L \end{cases}\) \(\mathsf{warp}_{3}(a_1, a_2, a_3, L)= \mathsf{warp}_{3e}(a_1, a_2, a_3, L) \pmod 2\)

\(\mathsf{wrap}_3\)函数中共享$ a_1, a_2, a_3 $与底层秘密 $a$ 的最高有效位 (MSB) 之间关系密切。$ a=a_1+a_2+a_3 \pmod{L} $作为$a_i$在模$L$的共享，用逻辑电路(如行波进位加法器)计算此和，可以计算$ \text{MSB}(a) = \text{MSB}(a_1) + \text{MSB}(a_2) + \text{MSB}(a_3) +c \pmod{2} $，$c$是来自上一索引的进位比特。上一索引的进位比特$c$只在$a_i$的模$L/2$上计算的\(\mathsf{wrap}_{3e}\)函数。这最后一个操作和计算$2a_i$模$L$上的\(\mathsf{wrap}_{3e}\)函数意义相同。算法2给出了\(\mathsf{wrap}_3\)函数的计算。 算法2 算法中参数的计算：

\[r = a + x - \eta \cdot L\] \[r = r_1 + r_2 + r_3 - \delta_e \cdot L\] \[r_i = a_i + x_i - \beta_i \cdot L \quad \forall i \in \{1,2,3\}\] \[x = x_1 + x_2 + x_3 - \alpha_e \cdot L\]

其中\(\delta_e, \alpha_e\)是wrap函数，等式(1)中，$r, a, x \in [0, L-1] $和$ r \equiv a+x \pmod{L} $。因此，若$ a+x \ge L $，当且仅当$ r < x (\text{or} \; x \ge r+1) $，假设$ \theta_e $是$a_1, a_2, a_3$的wrap函数即： \(a = a_1 + a_2 + a_3 - \theta_e \cdot L\) 在定点算术计算中，正数是前$2^{l-1}$位，最高有效位MSB为0；负数是后$2^{l-1}$位，最高有效位MSB为1。定义ReLU的导数函数为：

\[\text{DReLU}(x)= \begin{cases} 0 & \text{if}\; x > L/2 \\ 1 & \text{Otherwise} \end{cases}\]

它与定点数表示\(\text{DReLU}(a) = 1-\text{MSB}(a)\)的最高有效位有简单的联系。通过联系\(\mathsf{wrap}_3\)函数，写成如下等式： \(\mathsf{DReLU}(a) = \mathsf{MSB}(a_1) \oplus \mathsf{MSB}(a_2) \oplus \mathsf{MSB}(a_3) \\ \oplus \mathsf{wrap}_3(2a_1, 2a_2, 2a_3, L) \oplus 1 \tag{6}\) 从DReLU函数计算ReLU函数，可以用简单的秘密共享完成，通过对$a$的共享和$\text{DReLU}(a)$的共享执行乘法协议。$P_1, P_2, P_3$持有$\mathbb{Z}_L$上的共享$a$，均得到$ \mathsf{ReLU}(a) $的共享

  • 各方利用算法2获得$\mathsf{wrap}_3(2a_1, 2a_2, 2a_3, L)$
  • 通过等式6计算共享\([\![ b]\!]^2, b=\mathsf{DReLU}(a)\)
  • 在$ {a, 0} $上，用$b$的选择执行秘密共享协议得到输出

You May Also Enjoy