The 1st BIU Winter School--SECURE COMPUTATION AND EFFICIENCY 笔记

https://cyber.biu.ac.il/event/the-1st-biu-winter-school/

背景和定义

真实案例

  • 一个非盈利组织收到美国政府的联系,正在做一份刑事司法的研究。
  • 该组织向美国移民当局索要在纽约市被捕的外国人的 “外国人登记号码 “清单。
    • 来看哪些人在名单上
  • 考虑到隐私问题,双方都不能交出名单

这就是安全的交集操作。

安全多方计算

  • 拥有隐私输入的多方
  • 各方希望根据他们的输入计算出一个函数,来保留某些安全性
  • 即使有部分参与方恶意攻击协议,也必须保证这个性质
  • 可以对任何加密任务进行建模

安全要求

考虑一次(有秘密出价的)安全的拍卖过程:

  • 敌手可能想要知道所有各方的出价——为了防止这种情况发生,要求保密性;
  • 敌手可能想要用低价而不是高价赢得拍卖——要求正确性;
  • 敌手还可能想要保证它总是出价最高——要求输入的独立性;
  • 敌手可能想要在它出价不是最高时终止执行拍卖——要求公平性。

一般安全性

  • 保密性:只有输出被揭露
  • 正确性:该函数的计算是正确的
  • 输入独立性:各方不能根据其它方的输入来选择它们自己的输入
  • 公平性:如果一方收到输出,那么其它所有方也会收到输出
  • 保证输出送达

定义安全

选择1:对每个特定的问题进行安全考虑的分析

  • 拍卖:上面有提到
  • 选举:只需要保密性、正确性和公平性

  • 问题

    • 我们如何知道覆盖了所有的考虑?
    • 定义取决于应用,需要为每个任务重新定义

选择2:涵盖所有安全计算任务的通用定义

  • 这种定义的性质
    • 定义了良好的敌手模型
    • 定义了良好的执行设定
    • 安全保证明确、简单易懂
敌手建模

敌手行为:

  • 半诚实:遵循协议规范
    • 尝试通过检查中间结果获得更多信息
  • 恶意:遵循任意策略
  • 隐秘:遵循任意策略,但不愿被抓(?)

敌手力量:

  • 多项式时间
  • 计算无界:信息论安全

腐败策略:

  • 静态的:腐败方的集合在执行开始之前就已修复
  • 适应的:敌手可以在执行过程中根据发生的事情破坏各方
    • 为现代”黑客行为“建模
    • 无法使用选择一小部分代表进行全部计算的策略
    • 总的来说,更加困难
执行设定

单机:

  • 只考虑一个单独的协议被执行(或者只有一个执行过程被攻击)

并发一般组合:

  • 任意的协议是并发执行的
  • 现实的环境,非常重要的模型

单机对比组合:

  • 单机:研究MPC的好的开始
  • 组合:构造的真正目的

安全计算的可行性

  • 假设占多数的诚实方可以安全地计算任何函数
    • 甚至是具有自适应的信息论安全性
  • 一般来说,没有占多数的诚实方就不可能实现公平
  • 没有占多数的诚实方,可以计算出函数,但没有实现公平

前置知识

记号法

  • 安全参数 $n$
  • 我们希望只要 $n$ 足够大,对于任意输入都具有安全性
可忽略函数 $\mu$ :

如果对于任意多项式 $p(\cdot)$ 存在一个 $N$ 使得 $n > N$,有 $\mu(n) < 1 / p(n)$。

概率集合 $X=\{X(a,n)\}$
  • 无限集,由字符串 $a$ 和自然数 $n$ 索引
  • 每个 $X(a,n)$ 都是一个随机变量
    • 在我们的上下文中:使用输入 $a$ 和安全参数 $n$ 进行协议执行的输出
    • 概率空间:各方的随机性
计算的不可区分性 $X \approx Y$

对于每个(非均匀)多项式时间区分器 $D$ 存在一个可忽略函数 $\mu$ 使得对于每个 $a$ 和足够大的 $n$ 有:

统计接近度

相同,但 $D$ 在运行时间上不受限制。

函数
  • $f=(f_1,…,f_m)$:对于输入向量 $x$,每个 $f_i(x)$ 都是一个随机变量(对于概率函数)
  • $P_i$ 方收到 $f_i$
  • 记为 $(x,y) \rightarrow (f_1(x,y), f_2(x,y))$

半诚实敌手

模拟:

  • 给定输入和输出,就可以生成敌手执行协议的视图
  • 重要:由于各方遵循协议,因此输入定义明确

对于每个半诚实的 $A$,存在一个模拟器 $S$ 使得对于每组腐败方 $I$ 和输入 $x$ 的每个向量,以下内容都很接近

  • $A$ 的输出,以及协议执行后各方的输出
  • 对所有 $i \in I$ 给定 $x_i$ 和 $f_i(x)$ 的输出 $S$,以及所有的 $f_1(x),…,f_m(x)$ 的值

安全级别

定义“接近”

  • 计算安全性=计算不可区分性
  • 统计安全性=统计接近度
  • 完美安全性=相同的发行

如图所示,这里参与的两方都是半诚实的,执行安全多方计算协议后,各方能获得最终的输出以及中间的一些结果,而这个中间结果不能透露更多的信息。

敌手的视图

性质

在半诚实的模型中,正确性,输入的独立性,公平性都不是问题。

为什么这个定义保证了隐私?

  • 一次执行中,敌手的视图只能通过输入和输出来生成
  • 如果对手可以在实际协议执行后计算出某些内容,则仅能从输入/输出中进行计算
  • 与零知识证明非常类似

联合分布

关键点:需要考虑对手的输出和诚实方的输出的联合分配

在定义中:

  • 我们将所有输入和输出的分布与对手的输出进行比较

例子:

  • 函数:A 输出一个随机比特,B 不输出任何东西
    • B 显然不应该学习 A 的输出比特
  • 协议:A 选择一个随机比特并输出,然后发送给 B(后者直接忽略)

当分别查看 B 的视图和实际输出的分布时,这是可模拟的。

在确定性功能的情况下,输出完全由输入确定。

足够单独进行证明:

  • 正确性
  • 模拟:仅提供输入和输出,即可生成半诚实的对手的视图(腐败方的视图)

恶意敌手

敌手使用的输入不一定是写在输入磁带上的那些,并且不是明确的:敌手不执行协议而是执行任意代码。

理想以及现实范例

理想状态
  • 一个不能被腐败的可信第三方
  • 所有的输入都被发送到可信第三方(使用绝对安全的信道)
  • 可信第三方计算输出
  • 可信第三方将输出发送给各方(使用绝对安全的信道)
  • 敌手只能选择输入
现实情况
  • 对于攻击真实协议的每个对手 A,理想模型中都存在一个对手 S,以使(所有)输出分布都接近
    • 计算不可区分,统计接近度或相同分布…
  • S 在理想世界中交互时模拟真实协议执行
  • 这里总是看输出的联合分布

“正式”的安全定义

在以下情况下,协议 $\pi$ 安全地计算函数 $f$:

  • 对于每个非均匀多项式时间理想模型对手 A,都有一个非均匀多项式时间理想模型对手 S,这样对于所有输入向量和辅助输入:
  • $\pi$ 的实际执行中 A 和诚实方的联合输出,与在理想执行中可信第三方计算 $f$ 下的理想执行中 S 和诚实方的联合输出无法区分

性质

  • 保密性:来自敌手的输出
  • 正确性:来自诚实方的输出
  • 输入独立性:来自理想执行
  • 公平性以及输出正确传递:来自理想执行

放宽理想模型

  • 在一些情况下,理想模型很难实现。

  • 一般情况下,如果没有诚实方占多数,公平性很难实现。

  • 更改可信第三方的说明
    • 可信第三方从所有方中接收输入
    • 可信第三方发送腐败方的输出给敌手
    • 敌手说“继续”或“停止”
    • 如果“继续”,可信第三方发送输出给诚实方;反之发送“终止”
反应函数

分阶段获取输入并提供输出的功能。

例子:承诺方案

这对于放松理想功能也很有用(将辅助信息提供给S)

总结

  • 半诚实:给定输入/输出的模拟器生成对手的视图
    • 概率功能–必须考虑视图和输出的联合分布
    • 确定性功能:更容易,足以单独考虑正确性和视图仿真
  • 恶意:理想-现实模拟
  • 顺序组成

Yao的构造及其安全性证明

Yao的协议

  • 通用安全两方计算协议
    • 固定轮数
    • 对于半诚实敌手是安全的
    • 安全计算外还有许多应用
  • 通用安全计算
    • 可用于安全地计算任何功能
    • 基于布尔电路的函数计算

概览

乱码电路

  • 一个加密电路,其中每条线都有一对密钥指定一个输入
    • 可以计算输出(基于每条线上提供的键确定的输入)
    • 无法学到其他东西

不经意传输

  • 发送者有 $x_0, x_1$;接收者有 $b$
  • 接收者只获得 $x_b$
  • 发送者不能学习到任何东西

Yao的协议

  1. $P_1$ 构造一个乱码电路
  2. $P_1$ 发送在自己的输入线上与其输入相关联的密钥给 $P_2$
    • $P_1$ 仅仅发送密钥,因此 $P_2$ 不知道具体的输入是什么
  3. $P_1$ 和 $P_2$ 使用不经意传输使得对于每条 $P_2$ 的输入线:
    • $P_2$ 获得对应于其输入的正确密钥
    • $P_1$ 不能学习到关于 $P_2$ 输入的任何信息
  4. $P_2$ 计算电路获得输出,然后将其发送给 $P_1$

不经意传输

不经意传输协议

  • 发送者的输入:$(z_0, z_1)$;接收者的输入 $b$
  • 发送者的第一条信息:
    • 发送者使用算法1选择 $(f, t)$(这里 $f$ 是一个单向陷门函数,$t$ 是陷门)
    • 发送者发送 $f$ 给接收者
  • 接收者的第一条信息:
    • 接收者选择 $x_b$ 然后计算 $y_b = f(x_b)$
    • 接收者随机选取 $y_{1-b}$
    • 接收者发送 $(y_0, y_1)$ 给发送者
  • 发送者的第二条信息:
    • 发送者使用陷门计算 $(x_0, x_1)$
    • 发送者计算 $a_i = z_i \oplus B(x_i)$
    • 发送者发送 $(a_0, a_1)$ 给接收者
  • 接收者输出 $z_b = a_b \oplus x_b$

乱码电路

  • 对于整个电路,为每条导线分配随机值/键(键 $k_0$ 表示0,键 $k_1$ 表示1)

  • 加密每个门,以便为每个输入线指定一个密钥,就可以计算输出线上的适当密钥

与门

带乱码值的与门

乱码与门

  • 实际乱码门:

  • 给定 $k^0_u$ 和 $k^1_v$ 只能获得 $k^0_w$

  • 此外,由于该表是排列的,因此该方不知道它是获得了0还是1的键

输出翻译

  • 如果门是输出门,则需要提供输出线的“解密”

  • 输出翻译表:

构造一个乱码电路

  • 给定一个布尔电路
    • 为所有导线分配乱码值
    • 使用乱码值构造乱码门
  • 核心性质:
    • 给定一组乱码,每条输入线一个,可以计算整个电路,并获得输出线的乱码
    • 给定输出线的转换表,可以获得输出
    • 除了输出外没有任何信息泄露
例子

多方设置下的安全计算

如前所述,加密下的计算自然可以看作是对秘密共享数据的操作。在乱码电路中,通过让一方(生成者)持有两个可能的有线标签 $w^0_i, w^1_i$,而另一方(评估者)持有活动标签 $w^i_b$ 来实现有效线值的秘密共享。在GMW协议(Goldreich等人,1987;Goldreich,2004)中,线值的秘密共享更直接:玩家持有有效线值的加法份额。

GMW协议(或者简称为“GMW”)自然适用于两方以上的计算,而不像乱码电路,后者需要新的技术才能适用于两方以上的计算。

GMW协议

GMW协议既可以在布尔电路上工作,也可以在算术电路上工作。首先给出两方的布尔版本,然后简要解释如何将该协议推广到算术设置,以及如何推广到多于两方。与Yao的协议一样,假设输入为 $x$ 的参与方 $P_1$ 和输入为 $y$ 的参与方 $P_2$ 已经同意了表示计算函数 $\mathcal{F}(x, y)$ 的布尔电路 $\mathcal{C}$。

假设 $P_1$ 和 $P_2$ 的输入均为长为 $n$ 的比特串,其中 $P_1$ 输入为比特串 $a$,$P_2$ 输入为比特串 $b$。

对于比特串 $a$ 中的每个比特 $a_i$,$P_1$ 都生成一个随机的比特 $r_{1i}, \ i \in \{0,1\}, 1 \leq i \leq n$,并将这 $n$ 个随机产生的比特 $r_{1i}, 1 \leq i \leq n$ 发送给 $P_2$。

对于 $b$ 中的每个比特 $b_i$,$P_2$ 也都生成一个随机比特 $r_{2i}$ 并发送给 $P_1$。$P_1$ 和 $P_2$ 分别将 $a_i \oplus r_{1i}$ 和 $b_i \oplus r_{2i}$、$r_{1i}$、$r_{2i}$ 作为协议输入 $a$ 和 $b$ 的子秘密。

现在 $a$ 和 $b$ 都在 $P_1$ 和 $P_2$ 之间形成了秘密共享:

$a$ $b$
$P_1$ $a \oplus r_{1i}$ $r_{1i}$
$P_2$ $r_{2i}$ $b \oplus r_{2i}$

然后 $P_1$ 和 $P_2$ 对布尔电路中的每个门求值,直到完成整个电路的计算。

非门

由于非门是单输入的,$P_1$ 和 $P_2$ 间无须交互,直接对输入求反即可。

异或门

对于异或门有

因此双方可以在本地对其所掌握的子秘密进行计算,

与门

对于与门有

根据 $P_1$ 和 $P_2$ 的份额,$P_1$ 可以本地计算 $a_{P_1} \and b_{P_1}$ 而 $P_2$ 可以本地计算 $a_{P_2} \and b_{P_2}$。剩下的 $a_{P_1} \and b_{P_2}$ 和 $a_{P_2} \and b_{P_1}$ 双方必须协同完成。

$(a_{P_1} \and b_{P_2}) \oplus (a_{P_2} \and b_{P_1})$ 的计算可以通过四选一不经意传输协议完成。对于 $P_1$ 来说,$P_2$ 掌握的 $a_{P_2}$ 和 $b_{P_2}$ 都是单比特值,只有四种情况:

$a_{P_2}$ $b_{P_2}$
0 0
0 1
1 0
1 1

而 $P_1$ 手中又有 $a_{P_1}$ 和 $b_{P_1}$,因此 $P_1$ 可以直接计算出四种情况下 $a \and b$ 的值:

$a_{P_2}$ $b_{P_2}$ $a \and b$
0 0 $c_{00}$
0 1 $c_{01}$
1 0 $c_{10}$
1 1 $c_{11}$

$P_1$ 再生成一个随机比特 $r$,将计算出的 $c$ 的四个可能取值异或上 $r$,将 $c_{00} \oplus r$、$c_{01} \oplus r$、$c_{10} \oplus r$、$c_{11} \oplus r$ 作为四选一不经意传输协议的输入,$P_2$ 将其所掌握的 $a_{P_2}$ 和 $b_{P_2}$ 作为四选一不经意传输的输入,双方执行该OT协议,$P_2$ 得到对应的 $c_{a_{P_2} b_{P_2}} \oplus r$。

$P_1$ 将 $r$ 作为该与门的输出的子秘密,$P_2$ 将 $c_{a_{P_2} b_{P_2}} \oplus r$ 作为该与门的输出子秘密。

由于双方执行的是不经意传输协议,因此 $P_1$ 不知道 $P_2$ 在四个可能的值中选择了哪个,而 $P_2$ 也不知道随机比特 $r$ 的值,只有在最后双方都公布自己手中的计算结果才能正确地计算该门。

扩展到多方的情况

参与者为 $P_1, P_2, … , P_n$,假设输入为 $m$ 个比特,那么每个参与者 $P_i$ 产生 $m$ 组,每组 $n-1$ 个随机比特,分别将每组的 $n-1$ 个随机比特发送给除了自己之外的 $n-1$ 个参与者。

假设输入数据为 $1$ 个比特,那么每个参与者 $P_i$ 向参与者 $P_j$ 发送 $r_{ij}$,$1 \leq j \leq n$ 且 $j \neq i$。在所有参与者发送完成后,参与者 $P_i$ 掌握了 $r_{1i}, r_{2i}, … , r_{ni}$。假设 $P_i$ 的输入为 $a$,那么 $P_i$ 将 $a \oplus r_{1i} \oplus r_{2i} \oplus … \oplus r_{ni}$ 作为 $a$ 的子秘密 $a_i$。

对应的收到 $P_i$ 发送的随机比特 $r_{ij}$ 的参与者 $P_j$,将 $r_{ij}$ 当做秘密 $a$ 的子秘密 $a_j$。因此 $a = a_1 \oplus a_2 \oplus … \oplus a_n$。

对于异或门以及非门,和双方情况下相同,每个参与者直接在本地进行计算即可。对于与门,与门的输入为 $a$ 和 $b$,参与者 $P_i$ 手中掌握了 $a$ 和 $b$ 的子秘密 $a_i$ 和 $b_i$,因为 $a = a_1 \oplus a_2 \oplus … \oplus a_n$,可得:

这其中对于 $P_i$ 来说,每个 $a_i \and b_i$ 都可由参与者 $P_i$ 在本地进行计算。而对于 $a_i \and b_j, i \neq j$,可由参与者 $P_i$ 和 $P_j$ 通过上述的两方 GMW 协议共同计算出 $a_i \and b_j$ 的两个子秘密。当电路计算完成,每个参与者公布自己所掌握的子秘密,再将所有的子秘密进行异或,即可得到最后的计算结果。

BMR协议

之前介绍的姚氏混淆电路只支持双方计算,BMR(Beaver-Micali-Rogaway)协议将姚氏混淆电路扩充到了多方情景。

混淆电路的加密由一方对每条导线的真实输入值生成一个随机加密值,并根据每个门的真值表生成对应的加密表来实现。

因此如果直接把混淆电路协议扩展到多方,由一方对整个电路进行加密,或者对电路的一部分门进行加密,那么当加密方与参与者中的某个求值方进行串通或者这两者的信息都被收买时,就会破坏协议的安全性。

为了安全性,需要让所有参与者共同生成所有导线的加密值和门的加密真值表

具体而言,需要每个参加者随机生成每条导线的加密值,之后将自己生成的加密值进行掩盖后提交到多方计算协议,协议将每个参与者提交的关于同一条导线加密值进行异或,得到多方协同生成的布尔电路中该条导线的加密值。

具体过程

首先协议根据需要实现的目标函数生成布尔电路 $\mathcal{C}$,并向所有参与者公开。将 $\mathcal{C}$ 中的各条导线分别标记为 $w_1, w_2, …, w_t$。协议参与者为 $P_1, P_2,…,P_n$,其输入分别为 $x_1, x_2, …,x_n \in \{0,1\}$。

对于 $\mathcal{C}$ 中的每一条导线 $w_i$,参与者 $P_j$ 随机生成 $w_i$ 的真值 $0,1$ 对应的随机值,分别记为 $w^0_{i,j},w^1_{i,j}$。其中 $w^b_{i, j} = (k^b_{i, j},p^b_{i,j}) \in \{0,1\}^{l+1}, b \in \{0,1\}$,$p^b_{i,j}$ 满足 $p^b_{i,j} = 1 - p^{1-b}_{i,j}$,即 $k^b_{i,j}$ 为 $l$ 比特的随机比特串,$p^b_{i,j}$ 为 $1$ 比特的随机比特。再生成一个随机翻转比特 $f_{i,j} \in \{0,1\}$。对于每一条导线,参与者 $P_i$ 计算

因为 $p^b_{i,j} = 1 - p^{1-b}_{i,j}$,因此只需要发送 $p^0_{i,j}$ 或者 $p^1_{i,j}$ 即可。函数 $F$ 可以看做是哈希函数,其将 $l$ 位的输入扩展为 $n \cdot (l + 1)$ 位,$n$ 是参与者数量。

对于 $\mathcal{C}$ 中的每一个门 $G_i$,所有参与者共同参与一个计算乱码表的多方安全计算协议。该协议的输入是每个参与者之前计算的 $S_{i,j}$ 和参与者的输入 $x_1, x_2,…,x_n$。该协议的目标为:

假设 $\mathcal{C}$ 中门 $G_i$ 的输入线为 $w_a, w_b$,输出线为 $w_c$。$G_i$ 实现的函数为 $w_c = g(w_a, w_b)$。

计算指针比特:

并设置:

同理,对所有参加者提交的翻转比特求异或,

得到翻转比特 $f_a, f_b, f_c$,翻转比特用于掩盖参与者 $P_i$ 的输入,使得 $P_i$ 无法得知其对每条导线加密值的具体贡献。

接着创建门 $G_i$ 的乱码表,让 $v_a, v_b$ 分别是导线 $w_a, w_b$ 的输入,对于 $G_i$ 的输入 $v_a, v_b \in \{0,1\}$,一共只有四种可能的组合。

让 $v_c$ 表示导线 $w_c$ 的真实输出值,$e_{v_a, v_b}$ 是导线 $w_c$ 的加密值。设定

即 $e_{v_a, v_b}$ 共有四个可能的值,如下表所示:

$v_a$ $v_b$ $e_{v_a, v_b}$
$0$ $0$ $e_{0,1} = w^{v_c \oplus f_c}_c \oplus_{j=1,…,n} \left( F(i, w^{0\oplus f_a}_{a,j}) \oplus F(i, w^{0\oplus f_b}_{b,j}) \right)$
$0$ $1$ $e_{0,1} = w^{v_c \oplus f_c}_c \oplus_{j=1,…,n} \left( F(i, w^{0\oplus f_a}_{a,j}) \oplus F(i, w^{1\oplus f_b}_{b,j}) \right)$
$1$ $0$ $e_{0,1} = w^{v_c \oplus f_c}_c \oplus_{j=1,…,n} \left( F(i, w^{1\oplus f_a}_{a,j}) \oplus F(i, w^{0\oplus f_b}_{b,j}) \right)$
$1$ $1$ $e_{0,1} = w^{v_c \oplus f_c}_c \oplus_{j=1,…,n} \left( F(i, w^{1\oplus f_a}_{a,j}) \oplus F(i, w^{1\oplus f_b}_{b,j}) \right)$

其中 $w^b_c = w^b_{c,1} | \cdots | w^b_{c,n} | p^b_{c}, \ b\in \{0,1\}$,即将各个 $w^b_{c,i}$ 和 $p^b_c$ 进行级联。之后对乱码表中 $e_{v_a, v_b}$ 的条目进行重新排序,并将条目 $e_{v_a, v_b}$ 放在 $(p^{v_a}_a, p^{v_b}_b)$ 的位置上。

向参与者 $P_1$ 输出计算得到的乱码表,向 $P_1$ 发送各个参与方的输入 $x_1, x_2,…,x_n$ 所对应的电路 $\mathcal{C}$ 的加密导线值。

信息理论环境下的BGW构建

BGW 协议也是支持多方的安全计算协议,BGW 协议基于 Shamir(t, n) 门限秘密共享机制,利用了 Shamir 秘密共享机制的加法同态和乘法同态的性质。

  • 该构造提供了无条件的安全性
    • 可以抵抗半诚实敌手控制 $t < n / 2$ 方
    • 可以抵抗恶意敌手控制 $t < n / 3$ 方
  • 与基于加密假设的GMW结构不同

Shamir门限秘密共享方案

用途

假设我们存在一个秘密 $s$,把秘密 $s$ 进行特定运算,得到 $n$ 个秘密碎片 $s_i(0 < i \leq n)$,交给 $n$ 个人保存,当至少 $t$ 个人同时拿出自己所拥有的秘密碎片 $s_i$ 时,即可还原出最初的秘密 $s$。

秘密碎片生成

构造一个多项式

其中 $p$ 为素数且 $s < p$。

取 $n$ 个不相等的 $x$ 代入到 $F(x)$ 中,得到 $n$ 组 $(x_i, y_i)$,分配给 $n$ 个人;公开 $p$,销毁多项式,每个人负责保密自己的 $(x_i, y_i)$。

秘密恢复

当 $x=0$ 时,$F(0)=s$ 即可恢复出 $s$。

利用拉格朗日插值法,将 $t$ 组 $(x_i, y_i)$ 代入下式即可

将 $t$ 组 $(x_i, y_i)$ 代入即可得到 $s$。

BGW协议

假设 BGW 协议的参与者一共有 $n$ 人,假设参与者 $P_i$ 需要输入秘密 $a$,则参与者 $P_i$ 首先利用 Shamir(t,n) 门限秘密共享机制将秘密 $a$ 共享给其他所有参与者,阈值 $t$ 的选择根据具体使用情景下的安全性要求决定。

当所有参与者的输入都通过 Shamir(t, n) 门限秘密共享机制分享后,每个参与者都掌握了协议输入的子秘密。假设一个门的输入分别为 $a$ 和 $b$,秘密 $a$ 和 $b$ 已经分别由秘密分配函数

分配完成,$f_a(0) = a, f_b(0) = b$,参与者 $P_i$ 掌握 $a$ 和 $b$ 的子秘密 $a_i, b_i$。在布尔电路上,可将异或门和与门分别看成在有限域 $F_2$ 上的加法和乘法。将异或用模为 $2$ 的加法进行计算,与用模为 $2$ 的乘法进行计算。

加法

考虑一个加法门,具有输入线 $\alpha$,$\beta$ 和输出线 $\gamma$。各方共同持有输入线 $[v_\alpha]$ 和 $[v_\beta]$ 的共享,目标是获得 $[v_\alpha + v_\beta]$ 的共享。假设传入的共享分别对应于多项式 $p_\alpha$ 和 $p_\beta$。如果每一方在本地将他们的份额 $p_\alpha(i) + p_\beta(i)$ 相加,则结果是每一方在多项式 $p_\gamma (x) \overset{\rm{def}}{=} p_\alpha(x) + p_\beta(x)$ 上持有一个点。由于 $p_\gamma$ 的次数也为 $t$,因此这些新值构成有效的共享 $p_\gamma(0) = p_\alpha(0) + p_\beta(0) = v_\alpha + v_\beta$。

请注意,加法门不需要各方之间进行通信。所有步骤都是本地计算。同样的想法也适用于将秘密共享值乘以公共常量——每一方只需在本地将其份额乘以该常量即可。

乘法

考虑具有输入线 $\alpha$,$\beta$ 和输出线 $\gamma$ 的乘法门。各方共同持有输入线 $[v_\alpha]$ 和 $[v_\beta]$ 的共享,目标是获得 $[v_\alpha \cdot v_\beta]$ 的共享。如上所述,各方可以在本地乘以各自的份额,结果是每一方都持有多项式 $q(x) = p_\alpha(x) \cdot p_\beta(x)$ 上的一个点。然而,在这种情况下,得到的多项式的次数可能高达 $2t
$,这太高了。

为了纠正这种秘密分享过高的次数,双方进行了次数降低的步骤。每一方 $P_i$ 值为 $q(i)$,其中 $q$ 是次数为 $2t$ 的多项式。目标是获得 $q(0)$ 的有效秘密共享,但具有正确的门限。

主要观察到,$q(0)$可以写成各方份额的线性函数。特别地,

其中 $λ_i$ 项是适当的拉格朗日系数。因此,降低度数的步骤如下所示:

  1. 每个 $P_i$ 生成并分配阈值 $t$ 共享 $[q(i)]$。为了简化记法,本文没有给出低于这些份额的多项式。然而,重要的是要记住,每一方 $P_i$ 选择一个次数为 $t$ 的多项式,其常系数为 $q(i)$。
  2. 各方在本地计算 $[q(0)] = \sum^{2t+1}_{i=1} \lambda_i[q(i)]$。请注意,该表达式是应用于秘密共享值的加法和乘以常量。

由于值 $[q(i)]$ 是具有阈值 $t$ 的共享,因此 $[q(0)]$ 的最终共享也如所希望的那样具有阈值 $t$。

注意,BGW协议中的乘法门需要通信/交互,形式是各方发送 $[q(i)]$ 的份额。还要注意,我们需要 $2t+1 \leq n$,否则 $n$ 方集体没有足够的信息来确定值 $q(0)$,因为 $q$ 可能具有 $2t$ 次。因此,对于 $2t<n$(即诚实的多数),BGW协议是针对 $t$ 个被破坏方是安全的。

零知识证明与Sigma协议

Sigma协议

Sigma协议是Alice想要向Bob证明一些东西的协议(Alice知道一些秘密)。他们有下面的一般范式:Alice知道一个秘密,Alice和Bob都分享了一些相同的信息。因此:

  • Alice给Bob发送了一个值,这个值叫做承诺(commitment)。
  • Bob均匀的随机选择一个挑战(challenge)发送给Alice。
  • Alice计算一个回应(response)发送给Bob。
  • Bob检查回应,接受或者拒绝Alice的解释。

传说中,如果你把上面的过程画成一个图,这个图看起来像sigma($σ$),所以这个协议就叫Sigma协议。

在密码学中,希望Sigma协议有下面的属性:

  • 正确性,如果每个人都做了他们应该做的,Bob应该接受。
  • 公正性,如果Alice撒谎了,Bob可以知道(Alice不能欺骗Bob让他接受错误的结果)。
  • 零知识性,如果Alice说真话了,那么Bob不能知道她的秘密输入是什么。

基本定义

Definition 1: (Effective relation). Effective relation 指的是一组二元关系 $R \subseteq X \times Y$ 其中 $X,Y,R$ 为有效的可辨认的有限集合。$Y$ 中的元素被称作statements。如果 $(x,y) \in R$,则称 $x$ 为 $y$ 的witness。

Definition 2: (Sigma protocol). 设 $R \subseteq X \times Y$ 是一个effective relation。那么一对 $(P,V)$ 构建在 $R$ 上的一个 Sigma protocol 为:

  • $P$ 是一个叫做 $prover$ 的交互式协议,其输入为一个witness-statement对 $(x,y) \in R$
  • $V$ 是一个叫做 $verifier$ 的交互式协议,其输入为一个statement $y \in Y$
  • $P$ 和 $V$ 的交互过程为:
    1. 首先 $P$ 计算一个承诺(commitment) $t$,将其发送给 $V$;
    2. 在收到了来自 $P$ 的消息 $t$ 后,$V$ 在有限的挑战空间 $C$ 中随机选取一个挑战元素(challenge),并将其发送给 $P$;
    3. 在接收到来自 $V$ 的挑战 $c$ 后,$P$ 计算出一个反馈(response) $z$,将其发送给 $V$;
    4. 在收到了来自 $P$ 的消息 $t$ 后,$V$ 输出accept或者reject。$V$ 的输出由statement $y$ 和交互中的消息 $conversation(t,c,z)$ 严格计算得出。

例子——Schnorr’s identification protocol

协议过程

设 $\mathbb{G}$ 是一个阶为素数 $q$ 的循环群,其生成元为 $g \in \mathbb{G}$。设证明人 $P$ 保存私钥 $\alpha \in \mathbb{Z}_q$,对应的公钥为 $u = g^\alpha \in \mathbb{G}$。$P$ 需要向 $V$ 证明其拥有 $\alpha$。这里 $\alpha$ 是witness,$u = g^\alpha$ 是statement。Shnorr’s identification protocol的协议过程为:

  • 密钥生成算法产生公私钥:

    其中验证密钥 $vk := u$,私钥为 $sk := \alpha$。

  • $P$ 使用 $sk := \alpha$ 初始化,$V$ 使用 $vk := u$ 初始化,$P$ 和 $V$ 之间的交互过程为:

    1. $P$ 计算 $\alpha_t \overset{R}{\leftarrow} \mathbb{Z}_q, \ u_t \overset{R}{\leftarrow} g^\alpha_t$,并将 $u_t$ 发送给 $V$;
    2. $V$ 计算 $c \overset{R}{\leftarrow} C, \ C \subset \mathbb{Z}_q$,并将 $c$ 发送给 $P$;
    3. $P$ 计算 $\alpha_z \leftarrow \alpha_t + \alpha c$,并将 $\alpha_z$ 发送给 $V$;
    4. $V$ 进行检查:如果 $g^{\alpha_z} = u_t \cdot u^c$,$V$ 输出 accept,否则输出 reject。

零知识证明

零知识证明 zero-knowledge proofs,指的是证明者能够在不向验证者提供任何有用信息的情况下,使验证者相信某个论断是正确的。允许证明者 prover、验证者 verifier 证明某项提议的真实,却不必泄露除了「提议是真实的」之外的任何信息。

其实质是一种涉及两方或更多方的协议,即两方或更多方完成一项任务所需采取的一系列步骤。证明者向验证者证明并使其相信自己知道或拥有某一消息,但证明过程不能向验证者泄漏任何关于被证明消息的信息。大量事实证明,零知识证明在密码学中非常有用,尤其在 NP 问题、身份验证、数字签名、水印检测、密钥交换等,可以有效解决许多问题。加密数字货币与区块链为零知识证明的应用提供了新的方向。

综上,零知识证明是一种特殊的交互式证明,其中证明者知道问题的答案,他需要向验证者证明「他知道答案」这一事实,但是要求验证者不能获得答案的任何信息。

零知识证明的性质

根据零知识证明的定义和有关例子,可以得出零知识证明具有以下三个性质:

  1. 完备性 completeness:如果证明方和验证方都是诚实的,并遵循证明过程的每一步,进行正确的计算,那么这个证明一定是成功的,验证方一定能够接受证明方。
  2. 合理性 soundness:没有人能够假冒证明方,使这个证明成功。
  3. 零知识性 zero-knowledge:证明过程执行完之后,验证方只获得了「证明方拥有这个知识」的信息,而没有获得关于这个知识本身的任何信息。

零知识证明及其相关的协议的优点

1.随着零知识证明的使用,安全性不会降级,因为该证明具有零知识性质。

2.高效性。该过程计算量小,双方交换的信息量少。

3.安全性依赖于未解决的数学难题,如离散对数、大整数因子分解、平方根等。

4.许多零知识证明相关的技术避免了直接使用有政府限制的加密算法,为相关产品的出口带去优势。

例子

地图三染色问题和数独问题。

不经意传输

不经意传输是安全计算协议的基本构建块,也是一种固有的非对称协议。Impagliazzo和Rudich(1989)证明了从OT到对称密钥协议(单向函数,PRF)的约化意味着 $P \neq NP$。然而,正如Beaver(1996)首次观察到的那样,OT的批量执行只需要少量的公钥操作。Beaver的构造是非黑盒的,因为PRF需要被表示为一个电路,并被评估为MPC。因此,Beaver的研究结果主要是理论上的兴趣。Ishai等人。(2003年)提出了一种非常高效的批处理OT,它只需要对整个批处理进行 $\kappa$ 的公钥操作,每个OT只需要两到三个哈希。

设S有一个秘密,想以1/2的概率传递给R,即B有50%的机会收到这个秘密,另外50%的机会什么也没有收到,协议执行完后,B知道自己是否收到了这个秘密,但S却不知道R是否收到了这个秘密。这种协议就称为不经意传输协议。

基于公钥的OT

该结构的安全性假设存在公钥加密,能够在不获得相应私钥的情况下对随机公钥进行采样。该方案在半诚实模型下是安全的。发送方 $\mathcal{S}$ 只看到 $\mathcal{R}$ 发送的两个公钥,因此不能以比 $\frac{1}{2}$ 更高的概率预测哪个密钥是在不知道私钥的情况下生成的。因此,可以简单地通过发送两个随机选择的公钥来模拟 $\mathcal{S}$ 的视图。

接收器 $\mathcal{R}$ 看到两个密文,并且具有仅解密其中一个的秘密密钥。在给定 $\mathcal{R}$ 的输入和输出的情况下,也可以很容易地模拟 $\mathcal{R}$ 的视图。$\mathsf{Sim}_{\mathcal{S}}$ 将生成公钥对和随机公钥,并将模拟接收到的密文设置为

  1. 在生成的密钥对下对接收到的秘密进行加密;
  2. 在随机选择的密钥下对 $0$ 进行加密。

由于与实际执行的区别仅在于第二次加密,因此模拟进行,并且由于加密安全性的保证,将不会区分加密的 $0$ 和另一个值。注意,该半诚实协议不提供针对恶意接收者的安全性——接收者 $\mathcal{R}$ 可以生成两个公私钥对 $(sk_0, pk_0)$ 和 $(sk_1,pk_1)$ 并将 $(pk_0, pk_1)$ 发送给 $\mathcal{S}$,并且解密两个接收到的密文以学习 $x_1$ 和 $x_2$。

OT中的公钥操作

图3.7中的简单协议要求发送方和接收方对每个选择位都进行一次公钥操作。正如在基于布尔电路的MPC协议(例如姚氏GC)中使用的那样,有必要为执行电路的一方的每一个输入位执行OT。对于像GMW这样的协议,评估每个门都需要OT。因此一些研究集中在减少公钥操作的数量以执行大量的OT。

Beaver的非黑盒构造

Beaver(1996)建议对Yao的GC协议进行自举,从少量的公钥操作生成多项式的OT。用于计算电路 $\mathcal{C}$ 的GC协议需要 $m$ 个OT,其中 $m$ 是由 $P_2$ 提供的输入比特数。下面是OT中的记号,将 $P_1$ (GC中的生成者)称为发送方 $\mathcal{S}$,将 $P_2$ (GC中的评估者)称为接收方 $\mathcal{R}$。设 $m$ 是现在将作为批处理执行的所需的OT数量。$\mathcal{S}$ 的输入将是 $m$ 对秘密 $(x^0_1, x^1_1),…,(x^0_m, x^1_m)$,而 $\mathcal{R}$ 的输入将是 $m$ 位选择字符串 $b = (b_1, …, b_m)$。

我们现在构造一个实现函数 $F$ 的电路 $\mathcal{C}$,该函数 $F$ 仅从 $\mathcal{R}$ 获得少量的输入比特,但是将多项式数量的OT的结果输出给 $\mathcal{R}$。$\mathcal{R}$ 到 $F$ 的输入将是随机选择的 $\kappa$ 比特串 $r$。设 $G$ 是将 $\kappa$ 比特扩展成 $m$ 比特的伪随机生成器。$\mathcal{R}$ 将用伪随机字符串 $b \oplus G(r)$ 将其输入字符串发送给 $\mathcal{S}$。那么,$\mathcal{S}$ 对 $F$ 的输入将是 $m$ 对秘密 $(x^0_1, x^1_1),…,(x^0_m,x^1_m)$ 以及 $m$ 位串 $b\oplus G(r)$。函数 $F$ 计算 $m$ 比特展开 $G(r)$,并对输入 $b \oplus G(r)$ 进行去屏蔽,得到选择串 $b$,然后 $F$ 简单地将对应的秘密 $x_{b_i}$ 输出给 $\mathcal{R}$。电路评估者 $\mathcal{R}$ 只提供 $\kappa$ 输入位,因此执行 $m$ 个OT只需要固定数量的 $\kappa$ OT。

减少公钥操作次数

Beaver(1996)的构造展示了一种简单的方法,可以将执行 $m$ OT所需的非对称操作的数量减少到固定的安全参数,但由于需要执行大型GC,因此在实践中效率不高。回想一下,我们的目标是使用少量 $k$ 个基本OT,加上仅对称密钥运算,来实现 $m \gg k$ 个有效的OT。这里,$k$ 的选择取决于计算安全参数 $\kappa$;下面说明如何选择 $k$。下面描述Ishai等人的OT扩展(2003),在半诚实的敌手存在的情况下,实现了 $m$ 个随机串的二选一OT。

假设接收器 $\mathcal{R}$ 具有选择位 $r \in \{0,1\}^m$,$\mathcal{R}$ 选择两个 $m \times k$ 矩阵($m$ 行,$k$ 列),$T$ 和 $U$。设 $\boldsymbol{t}_j, \boldsymbol{u}_j \in \{0,1 \}^k$ 分别表示 $T$ 和 $U$ 的第 $j$ 行。矩阵是随机选择的,因此:

发送者 $\mathcal{S}$ 选择随机串 $s \in \{0,1 \}^k$。各方参与二选一OT的 $k$ 个实例,其角色颠倒,以根据发送者在其选择的串 $s$ 中的比特 $s_i$ 将 $T$ 或 $U$ 的列传送给发送者 $\mathcal{S}$。在第 $i$ 个OT中,$\mathcal{R}$ 提供输入 $\boldsymbol{t}^i$ 和 $\boldsymbol{u}^i$,其中它们分别指 $T$ 和 $U$ 的第 $i$ 列。$\mathcal{S}$ 使用 $s_i$ 作为其选择位,并接收输出 $\boldsymbol{q}^i \in \{\boldsymbol{t}^i, \boldsymbol{u}^i \}$。请注意,这些OT串的长度 $m \gg k$ ——OT消息的长度很容易扩展,例如通过加密和发送两个 $m$ 位长的字符串,并在短字符串上使用OT来发送正确的解密密钥。

现在设 $Q$ 表示发送者获得的矩阵,其列为 $\boldsymbol{q}^i$。让 $\boldsymbol{q}_j$ 表示第 $j$ 行。关键是观察到

令 $H$ 为一个随机预言机,于是 $\mathcal{S}$ 就能计算两个随机串 $H(\boldsymbol{q}_j)$ 和 $H(\boldsymbol{q}_j \oplus s)$,而 $\mathcal{R}$ 只能通过 $H(\boldsymbol{t}_j)$,根据其选择计算一个。实际上,根据等式3.2,$\boldsymbol{q}_j$ 等于 $\boldsymbol{t}_j$ 或 $\boldsymbol{t}_j \oplus s$,这取决于 $\mathcal{R}$ 的选择位 $r_j$。则根据 $\mathcal{R}$ 的选择位 $r_j$,$\boldsymbol{t}_j$ 等于 $\boldsymbol{q}_j$ 或 $\boldsymbol{q}_j \oplus s$。请注意,$\mathcal{R}$ 没有关于 $s$ 的信息,因此直观上它只能学习两个随机字符串 $H(\boldsymbol{q}_j)$ 和 $H(\boldsymbol{q}_j \oplus s)$ 中的一个。因此,矩阵的 $m$ 行中的每一行都可用于产生随机串的单个二选一OT。

为了将其扩展到两个给定秘密 $s_0, s_1$ 的更常见的二选一OT,在上面添加以下步骤。现在,$\mathcal{S}$ 另外用两个密钥 $H(\boldsymbol{q}_j)$ 和 $H(\boldsymbol{q}_j \oplus s)$ 来加密两个OT秘密,并将这两个加密(例如 $H(\boldsymbol{q}_j) \oplus s_0$ 和 $H(\boldsymbol{q}_j \oplus s) \oplus s_1$)发送给 $\mathcal{R}$。由于 $\mathcal{R}$ 可以恰好获得 $H(\boldsymbol{q}_j)$ 和 $H(\boldsymbol{q}_j \oplus s)$ 中的一个,所以他只能获得相应的秘密 $s_i$。

OT扩展

上面提到的方案为IKNP,IKNP第一个、也是最重要的步骤是将 $n$ 个OT规约为传输 $n$ 比特字符的 $k$ 个OT。这一步骤将引入额外的、线性数量级的对称密码学操作。下一步是长度扩展步骤,我们之前已经讲解过这一步骤了。这可以让我们把长字符串OT协议归约为短字符串OT协议。这一步骤进一步引入了线性数量级的对称密码学操作。

在核心规约步骤中,IKNP让接收方随机选择一个 $n \times k$ 的矩阵 $T$,然后发送方选择一个随机的行向量 $s$。接下来,接收方和发送方执行 $k$ 个OT协议,但此OT协议中两个参与方的角色互换。在每个OT协议中,接收方要选择长度为 $n$ 的两列比特值。每对比特值中,第一列为矩阵 $T$ 的某一列,第二列为第一列比特值与接收方的选择向量 $r$ 的异或结果。发送方实际上应用他随机选择的行向量在接收方的两列比特值中选择一列。

这样,发送方通过OT协议得到了一个矩阵 $Q$。$Q$ 满足如下性质:

  • 如果 $r_i = 0$,则 $q_i = t_i$;
  • 如果 $r_i = 1$,则 $q_i = t_i \oplus s$。

在第一种情况下,接收方知道 $t_i$,但无法知道 $t_i \oplus s$。因此在第一种情况下,接收方能得到 $q_i$,但无法得到 $q_i \oplus s$。在第二种情况下,接收方能得到 $q_i \oplus s$,也就是 $t_i$,但无法得到 $q_i$。这意味着或许可以使用 $q_i$ 和 $q_i \oplus s$ 作为OT协议中的数据加密密钥。但需要注意,必须要破坏矩阵中 $q_i$ 和 $q_i \oplus s$ 的相互关系。应用随机预言机 $H$ 来破坏 $q_i$ 和 $q_i \oplus s$ 的相互关系。最后,接收方根据 $t_i$ 选择得到他的输出,也就是应用 $t_i$ 进行解密。