Some Basic Protocol on BLAZE

关于安全三方计算中的一些基本协议

共享密钥设置

令$F: 0,1^\kappa \times 0,1^\kappa \rightarrow X$是一个安全伪随机函数PRF，其值域$X \in \mathbb{Z}_{2^l}$

• 每个配对之间有一共享密钥，$k_{01}, k_{02}, k_{12}$相对应于$(P_0,P_1),(P_0,P_2),(P_1,P_2)$
• 三方之间共享一个密钥$k_{\mathcal{P}}$

若服务器$P_0,P_1$非交互的采样随机值$r \in \mathbb{Z}_{2^l}$，他们则调用函数 $ F_{k_{01}}(id_{01}) $，$id_{01}$是服务器每次调用PRF函数后在本地更新的计数器。这里省略选取随机数的密钥。

抗碰撞哈希函数

一个哈希函数簇$\mathsf{H} = \mathcal{K} \times \mathcal{L} \rightarrow \mathcal{Y}$，若对于所有概率多项式时间敌手$\mathcal{A}$，给定$\mathsf{H}_k$，其中$k \in_R \mathcal{K}$，都存在一个可忽略的函数$\mathsf{negl}()$使得$\text{Pr}[(x_1, x_2) \leftarrow \mathcal{A}(k): (x_1 \neq x_2) \wedge \mathsf{H}_k(x_1) = \mathsf{H}_k(x_2) ] \le \mathsf{negl}(\kappa)$，这里$x_1, x_2 \in_R \{0,1\}^m, \; m=\mathsf{poly}(\kappa)$。

承若方案

令$\mathsf{Com}(x)$是$x$的一个承诺方案，它包括两部分：隐藏和盲化。隐藏的功能让承若保证$x$值的隐私性，盲化则让敌手打开承若时不能区分$x^\prime \neq x$。一般可以通哈希函数$\mathcal{H}()$构造承若，其安全性依赖于随机语言机(ROM)的证明，比如$(c, o) = (\mathcal(h \Vert r), x \Vert r) = \mathsf{Com}(x;r)$。

乘法协议

$\langle \cdot \rangle$共享的乘法协议，对于$\mathsf{v}$的$\langle \cdot \rangle$定义如下：$\langle \mathsf{v} \rangle_0 = ([\lambda_{\mathsf{v}}]_1, [\lambda_{\mathsf{v}}]_2), \langle \mathsf{v} \rangle_1 = ([\lambda_{\mathsf{v}}]_1, \mathsf{v} + \lambda_{\mathsf{v}}), \langle \mathsf{v} \rangle_2 = ([\lambda_{\mathsf{v}}]_2, \mathsf{v} + \lambda_{\mathsf{v}})$。同时给定$\mathsf{d}$和$\mathsf{e}$的$\langle \cdot \rangle$共享计算$\mathsf{f} = \mathsf{de}$的$\langle \cdot \rangle$共享。

要验证这种方法，要使证明者P在零知识的情况下$\text{V}_1, \text{V}_2$证明他知道$w$，并且$(x, w) \in \mathcal{R}$。令$\mathsf{ckt}$是被验证者的电路，使得$\mathsf{ckt}(x, w) = 0$ 当且仅当$(x, w) \in \mathcal{R}$。两个验证者共享语句$x$，$x_1,x_2$分别对应$\text{V}_1, \text{V}_2$，显然有$x = x_1 \Vert x_2$。另外若$\lvert x_1 \rvert=n_1, \lvert x_2 \rvert=n_2$，则$n = n_1 + n_2$，$\mathsf{ckt}$上的乘法门数有$M$。

证明者$P_0$选择三个多项式$f(), g(), h()$，分别是乘法门的左、右和输出电路。$f(), g()$的常数项分别为环$\mathbb{Z}_{2^l}$上的随机元素$z_1, z_2$，$h()$的常数项则为$z_1z_2$，更详细的如下。$P_0$对多项式$f(), g(), h()$进行插值计算，$f(), g()$最多$M$次多项式，$h()$多项式最多是$2M$次。令$\pi$是一个证明$(w, z_1, z_2, c_h) \in \mathbb{Z}_{2^\ell}$，其中$c_h$是多项式$h()$的系数。证明的大小是$\sigma = s + d + 3$，$s$是目击者的大小。$P_0$向$\pi$提供加法共享$\pi_i$给验证者，$\pi_i$是$P_i, i \in \{1,2\}$。若$P_0$是诚实方，则$\forall r \in \mathbb{Z}_{2^\ell}, \; h(r)=f(r)g(r)$和$h(M) = 0$。

验证者$P_1,P_2$一起随机生成$r \in \mathbb{Z}_{2^\ell} \backslash \{z_1, z_2\}$并生成相对应的查询向量$q_f, q_g, g_f \in \mathbb{Z}^{n+\sigma}_{2^\ell}$。验证者$P_1,P_2$从$q_f,q_g,q_h$中构造三个查询向量。更进一步，相对应于多项式$f()$，验证者$P_1,P_2$从$q_f$中构建向量$Q^i_f \in \mathbb{F}^{n_i + \sigma}, i \in \{1,2\}$，这样，前$n_i$个位置被保留给对应于后面是$q_f$的$x_i$项。 然后，验证者$P_1,P_2$本地计算向量$(x_i \Vert \pi_i)$和$Q^i_f$点积$f_i(r) = (x_i \Vert \pi_i) \odot Q^i_f$并发送给$P_1$。一旦$P_1$接收到$f_i(r)$的共享就计算$f(r) = f_1(r) + f_2(r)$。这是由于每个查询向量定义了输入$x$和证明$\pi$的线形组合。因此，验证者用输入$x_i$和加法共享$\pi_i$的部分，形成查询答案的加法共享，这个答案在随机数$r$处评估的多项式。 相似的步骤，可以让$P_1$获得多项式$g(r),h(r)$，若$h(r) \neq f(r) g(r)$，则$P_1$中止协议。若一个想作弊的验证者要通过验证的概率最大为$\frac{2M-1}{2^\ell - 2}$，$\ell$足够大的话，概率可以忽略不计。 对于第二个验证，即$h(M) = 0$，验证者用相同的方式生成查询向量$q$。对于$i \in \{1,2\},P_i$的查询$Q^i$计算$h_i(M)$并发送$h(M)$的共享给$P_1$。若$h(M) \neq h_1(M) + h_2(M) = 0$，则$P_1$​中止协议。这种查询采用了2轮的完全显性交互喻示器证明，查询复杂度为$\text{O}(\sqrt n)$，其中$n$是输入的大小。

安全性

文章用标准现实/理想模型证明协议构造的安全性。令$\mathcal{A}$是现实世界的敌手，表示各方服务器中$\mathcal{P}$中的腐败方。用$\mathcal{S}$表示$\mathcal{A}$的理想世界的敌手(也就是模拟器)，它是一个诚实方的服务器，模拟敌手$\mathcal{A}$在执行协议中收到的信息。仿真器初始化布尔变量$\mathsf{flag} = 0$，它表示诚实方服务器在协议执行期间是否出现中止操作。若协议中止，则$\mathsf{flag} = 1$。对于电路$\mathsf{ckt}$，仿真器从共享输入阶段开始，$\mathcal{S}$将诚实方输入设置为$0$。从共享协议$\Pi_{\mathsf{sh}}$，$\mathcal{S}$提取$\mathcal{A}$的输入，这使得$\mathcal{S}$或得电路$\mathsf{ckt}$的全部输入，这反过来有能让$\mathcal{S}$​知道所有中间值和电路的输出。通过分别模拟参与方$P_0, P_1$的攻击行为，证明协议的安全性。

共享协议$\Pi_{\mathsf{sh}}$的理想功能实现 $P_0$为腐败方时仿真器执行协议 $P_1$为腐败方时仿真器执行协议