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$为腐败方时仿真器执行协议