第 9 章 恶意安全性
本章,我们介绍恶意安全的协议。 我们首先介绍GMW编译器 [Gol et al., 1987]。这是一个通用的编译器,它使用零知识证明技术(zero-knowledge proofs) [Gol et al., 1985],可以将任意半诚实安全的协议转化为恶意安全的协议。 接着,我们介绍切分选择技术(cut-and-choose),它的思想是让某个参与方(假设为 \(P_1\))生成多个副本,然后由另一个参与方(假设为 \(P_2\))随机选择一部分副本让 \(P_1\) 打开,如果这部分都是正确的,双方才使用剩余的副本继续执行协议,从而避免 \(P_1\) 做出违背协议的行为。使用切分选择技术使姚氏混淆电路协议获得恶意安全性,是切分选择的一个典型应用。 接下来我们介绍恶意安全的BGW协议。在Ben-Or,Goldwasser,Wigderson(BGW)的论文 [Ben et al., 1988]中,对于半诚实敌手和恶意敌手分别设计了协议,而「BGW协议(半诚实安全)」一节介绍的是半诚实安全的协议。恶意安全的BGW协议使用了可验证秘密分享(verifiable secret sharing),对于 \(t < n/3\) 的(恶意的)被攻陷方,实现了完美的安全性。 最后,我们介绍BDOZ [BDOZ, 2011]和SPDZ [DPSZ, 2012]协议。它们使用了消息认证码(message authentication codes, MACs)以获得恶意安全性。
GMW编译器
GMW编译器~[Gol et al., 1987]
使用零知识证明技术~[Gol et al., 1985],可以将任意的半诚实安全的协议转化为恶意安全的协议。零知识证明是密码学中的一个重要工具,它可以让证明者(prover)向验证者(verifier)证明某个陈述(statement)为真,但不泄露陈述的正确性以外的任何信息。这个工具乍一看可能会令读者感到非常神奇和神秘,我们先通过一个简单的例子来带领读者了解零知识证明。
一个零知识证明的例子。形式化地说,零知识证明是一个两方协议,其中一方为证明者,另一方为验证者。证明者希望证明某个陈述为真。我们将这个陈述记为 \(x\). 在数学上,陈述为真意味着存在见证(witness) \(w\),满足 \(\mathcal{R}(x, w) = 1\),其中 \(\mathcal{R}\) 是一个二元NP关系(relation)。 而证明过程不能向验证者泄露 \(w\) 以及其他任何信息。
下面,我们给出一个零知识证明的具体例子。它的公共陈述是一个Pedersen承诺和一个Lifted ElGamal密文,证明者要证明承诺的值和加密的值是相同的。这个协议可能的具体场景是这样的:参与方首先用Pedersen承诺方案对自己的输入 \(m\) 进行承诺,然后协议的第一步需要对输入 \(m\) 加密,参与方需要证明自己遵循协议加密了承诺的值,当然,他不能泄露自己的输入。
我们在第2章已经介绍过Pedersen承诺(「承诺」一节)和ElGamal加密方案(「严格的安全性证明」一节)。简单回顾一下。首先,公共参数包括一个阶为 \(q\) 的循环群 \(\mathbb{G}\). 我们将Pedersen承诺的承诺密钥记为 \(\mathsf{ck} \in \mathbb{G}\),Pedersen承诺定义为 \(\mathsf{Com}_{\mathsf{ck}}(m) = g^m \mathsf{ck}^r\),其中 \(g\) 是群 \(\mathbb{G}\) 的生成元,\(r \leftarrow_{\$} \mathbb{Z}_q\) 是均匀随机选择的。Lifted ElGamal加密是ElGamal加密的变体。我们将公钥记为 \(\mathsf{pk}, \mathsf{pk} = g^\mathsf{sk}\). Lifted ElGamal加密定义为 \(\mathsf{Enc}_{\mathsf{pk}}(m) = (c_1, c_2) = (g^r, g^m \mathsf{pk}^r)\),其中 \(g\) 是群 \(\mathbb{G}\) 的生成元,\(r \leftarrow_{\$} \mathbb{Z}_q\) 是均匀随机选择的。不难看出,Pedersen承诺和Lifted ElGamal加密都具有加法同态的性质。此外,由于对Lifted ElGamal密文解密时需要计算 \(\mathsf{DLog}(c_2 / c_1^\mathsf{sk}) = m\),因此实际使用中 \(m\) 的值不能太大。
我们将证明者的Pedersen承诺记为 \(c, \; c = g^m \mathsf{ck}^s\);将Lifted ElGamal密文记为 \((c_1, c_2), \; (c_1, c_2) = (g^t, g^m \mathsf{pk}^t)\). 验证者对于 \(c\) 中的承诺值和 \((c_1, c_2)\) 中的加密值一无所知(根据Pedersen承诺的隐藏性和ElGamal加密的IND-CPA安全性),证明者知道 \(m, s, t\)(但不知道私钥 \(\mathsf{sk}\)),他希望证明承诺值等于加密值,并且不泄露任何额外信息(特别是不能泄露 \(m\))。
在这个场景下,陈述是所有公开的信息,包括 \((g, \mathsf{ck}, \mathsf{pk}, c, c_1, c_2)\),见证是证明者的私有信息 \(m, s, t\),关系 \(\mathcal{R}\) 的定义如下
我们给出关系 \(\mathcal{R}\) 的零知识证明协议,如图 9.1所示。
零知识证明需要满足三个性质:完备性(completeness),可靠性(soundness)和零知识性(zero-knowledge)。完备性指的是:如果证明者和验证者都是诚实的,那么验证者接受证明的概率为1;可靠性指的是:如果验证者接受了证明者的证明,那么(以压倒性的概率)陈述为真;零知识性指的是:验证者不能获得除了陈述为真以外的任何信息。
我们发现,图 9.1的协议分为3步:证明者先发送初始消息 \(a = (a_1, a_2, a_3)\),验证者再发送随机值 \(e\),然后证明者发送回答消息 \(z = (z_1, z_2, z_3)\). 其中,验证者发送的消息是随机值,与证明者发送的消息无关。如果零知识证明协议中验证者的消息都是均匀随机选取的,那么它被称为公共硬币(public-coin)的协议。 像图 9.1这类3步的公共硬币零知识证明协议被称为Sigma协议(Sigma protocols)。 下面,我们形式化地定义Sigma协议以及它的完备性、可靠性、零知识性。
完备性很容易理解:在证明者和验证者都诚实执行协议的情况下,验证者接受证明的概率为1. 2-特殊可靠性的直观含义是:给定陈述 \(x\),如果对于同一个初始消息 \(a\),有两组可以通过验证的会话 \((a, e, z)\) 和 \((a, e', z')\),那么提取器 \(\mathcal{X}\) 就能够提取出见证 \(w\). 换句话说,我们可以构造这样的提取器,它先与证明者 \(P\) 执行协议,得到 \((a, e, z)\),再将 \(P\) 倒带(rewind)到第2步,发送一个新的挑战值 \(e'\),得到第二组会话 \((a, e', z')\),即可提取出见证 \(w\). 诚实验证者零知识性要求存在一个模拟器 \(\mathcal{S}\),给定挑战值 \(e\),\(\mathcal{S}\) 需要在不知道见证 \(w\) 的情况下模拟协议会话 \((a, e, z)\),且与真实的协议会话不可区分。因为 \(\mathcal{S}\) 不知道 \(w\),但可以模拟出与真实会话不可区分的协议会话,那么我们可以知道:真实的协议会话不会泄露 \(w\).
从模拟器 \(\mathcal{S}\) 的定义中,我们可以看出消息顺序的微妙之处。在实际执行协议时,证明者必须先发送初始消息 \(a\),再接收随机挑战值 \(e\),最后发送回答消息 \(z\);而模拟器是先知道了挑战值 \(e\),再模拟出消息 \(a\) 和 \(z\). 也就是说,证明者在发送初始消息 \(a\) 的时候必须不知道挑战值 \(e\),协议才有可靠性;而如果先知道了挑战值 \(e\),模拟器就可以在不知道见证 \(w\) 的情况下模拟出协议会话 \((a, e, z)\),这体现了协议的零知识性。
下面,我们证明图 9.1中的协议的安全性。
从这个简单的例子可以看出,零知识证明确实是可以构造的,它并不神秘。实际上,对于任意的NP关系,都存在零知识证明协议 [Gol et al., 1986]。因此,在安全多方计算中,参与方也可以通过零知识证明协议来证明自己诚实地遵循协议执行。
GMW编译器。给定一个半诚实安全的协议 \(\Pi\),GMW编译器将其转化为恶意安全的协议 \(\Pi'\). \(\Pi'\) 的执行过程如下。
输入承诺:每个参与方对自己的输入值进行承诺。即参与方 \(P_i\) 计算承诺值 \(c_i = \mathsf{Com}(x_i, \rho_i)\),其中 \(x_i\) 是 \(P_i\) 的输入,\(\rho_i\) 是随机数。\(P_i\) 将 \(c_i\) 公开。
抛硬币:每个参与方 \(P_i\) 均匀选择随机数 \(r_{i, i}\) 并承诺,将承诺公开。其他参与方 \(P_j, \; j \neq i\) 均匀选择随机数 \(r_{i, j}\) 并承诺。所有参与方完成承诺后,\(P_j, \; j \neq i\) 将 \(r_{i, j}\) 打开。协议执行过程中,\(P_i\) 使用 \(r_i = \bigoplus\limits_{j=1}^n r_{i, j}\) 作为随机数。这样的构造使得只要有一个参与方是诚实的,那么 \(r_i\) 就是均匀随机的。
执行协议:在协议执行过程中,当参与方 \(P_i\) 发送消息时,通过零知识证明协议证明该消息是使用 \(x_i\) 为输入,\(r_i\) 为随机数,诚实地遵循协议执行得到的。
GMW编译器给出了一个理论上完美的结论:任何半诚实安全的协议都可以转化为恶意安全的协议。但是,使用这样的通用方法得到的协议往往运行效率较低,不适用于实际场景。
切分选择
直观思想
姚氏混淆电路协议对于半诚实的敌手是安全的,但是无法抵御恶意敌手。具体而言,协议中电路生成方 \(P_1\) 需要为电路 \(\mathcal{C}\) 生成混淆电路,恶意的 \(P_1\) 可以生成另一个电路 \(\mathcal{C}'\) 的混淆电路并发送给 \(P_2\). 对 \(\mathcal{C}'\) 求值可能会泄露额外的信息,甚至直接泄露 \(P_2\) 的输入!
切分选择(cut-and-choose)技术(注:cut-and-choose这个名称,最初类比的是互不信任的双方公平地分蛋糕的方法 [Brassard et al., 1988]:一方将蛋糕切为两块(cut),另一方选择自己的那份(choose)。姚氏混淆电路协议cut-and-choose的过程与分蛋糕已经有所不同。)的基本思想是:\(P_1\) 对电路 \(\mathcal{C}\) 生成多个混淆电路的副本,然后 \(P_2\) 随机选择一部分要求 \(P_1\) 打开。只要有一个被打开的电路是错误的,\(P_2\) 就知道 \(P_1\) 在作弊,协议中止。如果打开的电路都是正确的,那么 \(P_1\) 和 \(P_2\) 使用未被打开的电路继续执行协议,此时,\(P_2\) 有信心认为未被打开的电路大多数是正确的。
如果电路的计算结果不一致?当 \(P_1\) 和 \(P_2\) 使用切分选择技术执行协议时,假设 \(P_1\) 打开的电路全部都是正确的,那么他们将继续执行协议,对所有未打开的电路进行计算。此时,有两种可能的情况:(1) 所有电路的计算结果都一致;(2) 电路的计算结果不一致。对于情况1,\(P_2\) 可以将这个结果作为协议的输出发送给 \(P_1\). 对于情况2,出现不一致的计算结果的唯一可能就是 \(P_1\) 在作弊,我们的第一反应也许是:\(P_2\) 应该立刻中止协议。
然而,这样做是不安全的,\(P_1\) 有如下的攻击方式。假设协议中 \(P_1\) 需要生成 \(s\) 个混淆电路,\(P_2\) 随机选择 \(s/2\) 个电路让 \(P_1\) 打开。\(P_1\) 构造一个特殊的混淆电路,当 \(P_2\) 的输入的第一个比特为1时,它会输出错误的结果,如果 \(P_2\) 的输入的第一个比特为0,那么它的输出是正确的。然后,对于其余 \(s - 1\) 个混淆电路,\(P_1\) 正确地生成。此时,当 \(P_2\) 随机选择 \(s/2\) 个电路时,这个错误的混淆电路被检测到的概率为1/2. 如果它没有被检测到,协议将继续运行,这会泄露 \(P_2\) 的输入的第一个比特:如果这个比特是1,电路将出现不一致的计算结果,\(P_2\) 将中止协议;如果这个比特是0,\(P_2\) 将完成协议运行。也就是说,\(P_1\) 有1/2的概率可以获得 \(P_2\) 的输入的第一个比特。
如果我们希望这个概率小于 \(2^{-40}\),只需取 \(s = 164\) 即可。
输入一致性(input consistency)。在基于切分选择技术的协议中,\(P_2\) 要对多个混淆电路的副本进行计算。我们需要确保每个混淆电路的输入是相同的,即输入一致性。\(P_2\) 的输入一致性比较容易实现:对于 \(P_2\) 的每个输入比特,\(P_1\) 和 \(P_2\) 仅执行一次OT协议一次性地发送所有混淆电路中该输入导线的密钥。但是,\(P_1\) 有可能在不同的混淆电路提供不同的输入,从而试图获取额外信息。例如,假设 \(P_1\) 和 \(P_2\) 的输入为 \(x, y \in \{0, 1\}^n\),他们希望计算 \(x\) 和 \(y\) 的内积,即 \(f(x, y) = \langle x, y \rangle = x_1 y_1 + … + x_n y_n\),其中 \(x_i\) 是 \(x\) 的第 \(i\) 位,\(y_i\) 是 \(y\) 的第 \(i\) 位。假设 \(P_1\) 和 \(P_2\) 恰好需要计算 \(n\) 个混淆电路。对于第 \(i\) 个混淆电路,\(P_1\) 将其输入的第 \(i\) 位设置为1,其余位为设置为0. 于是,\(P_2\) 计算第 \(i\) 个电路得到的结果就是 \(y_i\). 然后,\(P_2\) 输出大多数电路的结果,这将泄露 \(P_2\) 的输入中大多数比特是0还是1.
零知识证明可以解决 \(P_1\) 的输入一致性问题。一种可行(但不太高效的)方法如下:假设 \(P_1\) 生成了 \(s\) 个混淆电路。在进行切分选择检查之前,对于 \(P_1\) 的每条输入导线,\(P_1\) 对每个电路中该导线值0对应的密钥和1对应的密钥进行承诺,所有承诺值构成了“0集合”和“1集合”(“0集合”和“1集合”的大小均为 \(s\))。然后,\(P_2\) 随机选择 \(s/2\) 个电路让 \(P_1\) 打开。\(P_1\) 在打开电路的同时也打开“0集合”和“1集合”中对应电路的密钥,\(P_2\) 检查打开的电路导线值0的密钥确实在“0集合”中,导线值1的密钥确实在“1集合”中。最后,当 \(P_1\) 向 \(P_2\) 发送 \(P_1\) 的输入在未打开的电路中的密钥时,\(P_1\) 用零知识证明协议证明:这些密钥都在“0集合”中或这些密钥都在“1集合”中。不难看出,这样的构造确保了用于计算的大多数电路中,\(P_1\) 的输入是一致的。然而,证明密钥都在“0集合”中或都在“1集合”中的零知识证明协议是比较低效的,我们将在「LP11协议」一节介绍一种更高效的零知识证明构造。
选择性中止攻击(selective abort attack/selective failure attack)。现在,我们通过零知识证明确保了 \(P_1\) 的输入一致性。但是,\(P_2\) 的输入对应的密钥需要 \(P_1\) 在OT协议中提供,恶意的 \(P_1\) 可以在OT协议中提供错误的输入来获取额外信息。假设 \(w_i\) 是 \(P_2\) 的一条输入导线,它的密钥是 \(k_i^0, k_i^1\),\(P_1\) 应该将 \((k_i^0, k_i^1)\) 作为OT协议的输入(注:这里做了简化,实际上应该有 \(s/2\) 对密钥。)。但是,\(P_1\) 可以将OT协议的输入设置为 \((k_i^0, 0)\). 这样一来,如果 \(P_2\) 的这个输入比特是0,他将完成协议,不会发现任何异常;如果 \(P_2\) 的这个输入比特是1,他就没有得到对应的密钥,无法计算混淆电路,只能中止协议。\(P_1\) 通过观察 \(P_2\) 是否中止协议从而知道 \(P_2\) 的输入比特。
为了抵御选择性中止攻击,我们需要让 \(P_1\) 在执行OT协议的同时对OT协议的输入进行承诺(这种OT称为committing OT [Kiraz, 2006]),然后在进行切分选择检查时将打开的电路对应的承诺一起打开。具体而言,\(P_1\) 和 \(P_2\) 首先对 \(P_2\) 的每个输入比特执行committing OT协议。然后,\(P_1\) 发送 \(s\) 个混淆电路给 \(P_2\),\(P_2\) 随机选择 \(s/2\) 个电路让 \(P_1\) 打开。\(P_1\) 同时打开这些电路在committing OT协议中的两个输入(利用committing OT的绑定性),\(P_2\) 检查这些输入都是正确的。这样的方法可以确保 \(P_1\) 在大多数OT协议中使用了正确的输入。
\(P_1\) 的输出真实性(output authenticity)。上述方法可以确保 \(P_2\) 进行电路计算后大多数电路的输出(以压倒性的概率)是正确的。在混淆电路协议中,\(P_2\) 在最后一步将协议输出发送给 \(P_1\),在半诚实敌手模型下,这没有任何问题,但是,在恶意敌手模型下,恶意的 \(P_2\) 可以发送任意的错误输出给 \(P_1\).
需要注意的是,在恶意敌手模型下进行两方安全计算时,我们无法实现公平性(fairness) [Cleve, 1986]。也就是说,协议无法使参与双方同时获得输出,恶意的参与方可以在获得输出后停止执行协议,使诚实参与方不获得输出。以混淆电路协议为例,我们无法阻止 \(P_2\) 在获得输出后停止执行协议。但是,我们能够实现的是:如果 \(P_2\) 向 \(P_1\) 发送协议输出,\(P_1\) 可以检查输出的真实性(authenticity)。
这里采用的技术是消息认证码(message authentication codes, MACs),并且,如果我们能安全地计算任意单一输出功能 \(f(x, y)\) 使得只有 \(P_2\) 得到输出,那么我们可以基于其构造一个实现功能 \(f = (f_1, f_2)\) 的协议,其中 \(P_1\) 得到 \(f_1(x, y)\),\(P_2\) 得到 \(f_2(x, y)\).
协议构造如下。令 \(f = (f_1, f_2)\) 是一个功能。我们需要构造一个安全的协议使 \(P_1\) 得到 \(f_1(x, y)\),\(P_2\) 得到 \(f_2(x, y)\);我们有一个能够安全计算任何功能的协议,但是只有 \(P_2\) 能获得输出。令 \(\mathbb{F}\) 是包含 \(f_1\) 所有取值 \(\{f_1(x, y)\}_{x, y \in \{0, 1\}^n}\) 的域,令 \(p, a, b \leftarrow_{\$} \mathbb{F}\) 是在 \(\mathbb{F}\) 上均匀随机选取的值。定义单一输出功能 \(g\) 如下:\(g((p, a, b, x), y) = (\alpha, \beta, f_2(x, y))\),其中 \(\alpha = p + f_1(x, y), \; \beta = a \cdot \alpha + b\),运算符号 \(\langle +, \cdot \rangle\) 由域 \(\mathbb{F}\) 所定义。这里的 \(\alpha\) 是以 \(p\) 为密钥使用“一次一密”加密的密文,\(\beta\) 是 \(\alpha\) 的消息认证码。双方使用只有 \(P_2\) 能获得输出的协议计算功能 \(g\),然后 \(P_2\) 将 \((\alpha, \beta)\) 发给 \(P_1\). \(P_1\) 检查 \(\beta \stackrel{?}{=} a \cdot \alpha + b\),如果是,输出 \(\alpha - p\),否则输出 \(\bot\).
显然,“一次一密”的完美安全性保证了 \(P_2\) 不知道 \(f_1(x, y)\),而 \(P_2\) 成功伪造消息认证码 \(\beta = a \cdot \alpha + b\) 的概率为 \(1 / |\mathbb{F}|\). 回顾一下,在「独立模型」一节中,(独立模型下)对于恶意敌手的安全性定义考虑的是两个参与方都获得输出的情况。根据上述构造,我们可以使用一种更简单的等价定义,这种定义下只有一个参与方获得输出。我们在之后的协议构造和证明中,也会采用这种更简单的定义。
协议概览。综合以上所有构造,基于切分选择技术的混淆电路协议整体流程如下。
\(P_1\) 生成 \(s\) 个混淆电路。
对于 \(P_2\) 的每个输入比特,\(P_1\) 和 \(P_2\) 执行committing OT协议使 \(P_2\) 获得对应的密钥。
\(P_1\) 向 \(P_2\) 发送 \(s\) 个混淆电路,以及 \(P_1\) 的输入导线密钥的承诺值。
\(P_2\) 随机选择 \(s/2\) 个电路让 \(P_1\) 打开。
\(P_1\) 打开这些电路,同时打开这些电路在committing OT协议中的输入,打开这些电路中 \(P_1\) 的输入导线密钥的承诺。\(P_2\) 检查正确性。
\(P_1\) 向 \(P_2\) 发送未打开的电路中 \(P_1\) 的输入导线密钥,并证明输入一致性。
\(P_2\) 对未打开的电路进行计算,取大多数电路的计算结果为输出。
(如果 \(P_1\) 也需要获得输出)\(P_2\) 向 \(P_1\) 发送 \(P_1\) 的输出和消息认证码,\(P_1\) 检查消息认证码。
上述流程是基于切分选择的协议的概览。实际上,研究人员对切分选择协议做了大量的优化 [Lin & Pin, 2007; She & She, 2011; She & She, 2013; Kreshe & She, 2012; Lin & Pin, 2011; Hua et al., 2013; Lindell, 2013; Brandao, 2013; Fre et al., 2014; AMPR, 2014]。本书将介绍Lindell和Pinkas在2011年提出的一个比较有代表性的切分选择协议 [Lin & Pin, 2011],并给出安全性证明。
LP11协议
LP11协议 [Lin & Pin, 2011]也遵循上述基本流程,但有以下两点不同:
在第2步中,LP11协议没有执行committing OT,而是引入了一个新的原语——切分选择OT(Cut-and-Choose OT, CCOT). 在切分选择OT中,发送方的输入是 \((x_1^0, x_1^1), …, (x_s^0, x_s^1)\),接收方的输入是选择比特 \(\sigma_1, …, \sigma_s\) 以及一个大小为 \(s/2\) 的集合 \(\mathcal{J} \subset [s]\). 对于 \(i \in [s]\),接收方得到 \(x_i^{\sigma_i}\)(就像普通的OT那样);对于 \(j \in \mathcal{J}\),接收方得到发送方的两个值 \((x_j^0, x_j^1)\). 发送方不能得到 \(\sigma_1, …, \sigma_s\) 和 \(\mathcal{J}\) 的任何信息。 这里的集合 \(\mathcal{J}\) 实际上就是要打开的电路的索引。切分选择OT将OT协议与切分选择检查结合在一起,有效地抵御了选择性中止攻击(实际上,切分选择OT和committing OT具有类似的作用)。
LP11协议设计了更高效的零知识证明以证明 \(P_1\) 的输入一致性。假设 \(P_1\) 的输入长度为 \(\ell\) 比特,\(P_1\) 选择值 \(g^{a_1^0}, g^{a_1^1}, …, g^{a_\ell^0}, g^{a_\ell^1}\) 以及 \(g^{r_1}, …, g^{r_s}\),然后将第 \(i\) 个输入比特在第 \(j\) 个电路中的密钥设置为 \(g^{a_i^0 \cdot r_j}, g^{a_i^1 \cdot r_j}, \; i \in [\ell], \; j \in [s]\). 基于DDH假设,在已知所有的 \(\{g^{a_i^0}, g^{a_i^1}, g^{r_j}\}\) 和 \(P_1\) 的输入对应的密钥的情况下,其余密钥仍是伪随机的。这样的构造使得 \(P_1\) 的输入一致性零知识证明非常高效。
下面,我们详细介绍这两点。
切分选择OT
切分选择OT理想功能。直观地说,切分选择OT协议是一个批处理的OT协议(它能够对多对输入同时执行OT协议),但有一个额外属性:接收方可以选择一个子集,对于这个子集中的索引,接收方获得两个值。在基于切分选择的协议中,这样的构造非常自然。接收方选择的子集就是让 \(P_1\) 打开的电路的索引,接收方获得这些电路在OT协议中的两个输入,防止 \(P_1\) 进行选择性中止攻击。
图 9.15展示了切分选择OT的理想功能 \(\mathcal{F}_{\mathsf{CCOT}}\) 以及单一选择切分选择OT(single-choice cut-and-choose OT),记为 \(\mathcal{F}_{\mathsf{CCOT}}^S\). 在单一选择切分选择OT中,接收方必须在每一个OT中使用相同的选择比特 \(\sigma\)(这是为了保证切分选择协议中 \(P_2\) 的输入一致性)。
切分选择OT构造思路。切分选择OT基于Peikert,Vaikuntanathan,Waters (PVW)的OT协议 [Pei et al., 2008]构造。PVW协议是在公共参考字符串(Common Reference String, CRS)(注:公共参考字符串是从某个分布中预先随机选择的字符串,它对协议的所有参与方公开;朴素模型(plain model)没有任何初始设置。相比于朴素模型,在公共参考字符串模型下可以构造出实现更强理想功能的协议。)模型下构造的,它的CRS是元组 \((g_0, g_1, h_0, h_1)\),其中 \(g_0\) 是一个阶为 \(q\) 的群的生成元(DDH问题在该群中是困难的),\(g_1 = (g_0)^y\),\(y\) 是一个随机数,\(h_0 = (g_0)^a, \; h_1 = (g_1)^b\) 且 \(a \neq b\). 而切分选择OT协议可以在朴素模型(plain model)下构造,这是因为协议让接收方选择元组 \((g_0, g_1, h_0, h_1)\),其中 \(h_0 = (g_0)^a, \; h_1 = (g_1)^b\),然后证明它满足 \(a \neq b\)(也就是证明它不是Diffie-Hellman元组);具体而言,协议设置 \(b = a + 1\),然后用Sigma协议证明 \((g_0, g_1, h_0, \frac{h_1}{g_1})\) 是Diffie-Hellman元组,使得该证明非常高效。
此外,当 \((g_0, g_1, h_0, h_1)\) 是Diffie-Hellman元组(即 \(a = b\))时,PVW协议的接收方可以获得发送方的两个输入。这恰恰符合切分选择OT的需要!我们让接收方选取 \(s/2\) 对满足 \(a \neq b\) 的 \((h_0, h_1)\)(他只能获得一个输入),选取 \(s/2\) 对满足 \(a = b\) 的 \((h_0, h_1)\)(他可以获得两个输入),这就构成了切分选择OT的雏形。当然,接收方需要证明有 \(s/2\) 对 \((h_0, h_1)\) 满足 \(a \neq b\),也就是需要证明 \(s\) 对 \((h_0, h_1)\) 中有一部分满足某个陈述,这是一个部分知识的证明(proof of partial knowledge),可以通过CDS组合 [Cra et al., 1994]高效地实现。下面,我们对上述思路的每一部分详细阐释。
PVW协议(的变体)。图 9.2展示了PVW协议在朴素模型下的变体。
我们先分析DH元组的零知识证明协议(图 9.3)。它实质上是在Sigma协议的基础上让验证者对挑战值进行承诺,以实现(面对任意验证者的)零知识性。DH元组Sigma协议的初始消息是 \(A = (g_0)^r, \; B = (g_1)^r\),挑战值是 \(s\),回答消息是 \(z = s \cdot w + r\),验证者最后验证 \((g_0)^z \stackrel{?}{=} A \cdot u^s, \; (g_1)^z \stackrel{?}{=} B \cdot v^s\). 在此基础上,协议的第1、2步让验证者对挑战值 \(s\) 使用Pedersen承诺方案(参见「承诺」一节)进行承诺,Pedersen承诺方案的承诺密钥为 \(\alpha = (g_0)^a\) 由证明者选取;在协议的第4、5步,证明者需要额外打开Pedersen承诺(公布 \(s, t\));在协议的第6步,证明者需要额外公布承诺密钥 \(\alpha\) 的离散对数 \(a\). 这样做的目的是:Sigma协议仅满足诚实验证者零知识性(special honest verifier zero-knowledge),但对于任意的验证者,模拟器无法预知挑战值;图 9.3的协议让验证者首先对挑战值进行承诺,使协议获得了(面对任意验证者的)零知识性(注:对挑战值进行承诺,使得模拟器将验证者倒带后,得到的仍是同样的挑战值,感兴趣的读者可以参阅书 [Hazay et al., 2010], Chapter 6中完整的证明。)。
关于安全性,这基于 \(\mathsf{RAND}\) 函数的性质:如果 \(\mathsf{RAND}\) 的输入不是DH元组,那么它的输出是两个独立的均匀随机分布的群元素。因此,\((u_0, w_0)\) 和 \((u_1, w_1)\) 中有一个是均匀随机分布的,所以接收方只能获得发送方的一个输入。相反,如果 \((g_0, g_1, h_0, h_1)\) 是DH元组且接收方知道 \(y = \log_{g_0} g_1\),那么接收方可以获得发送方的两个输入。例如,对于 \(\sigma = 0\) 的情况,接收方可以首先执行协议步骤计算 \(x_0\);并且,接收方还可以计算 \(x_1 = w_1 / (u_1)^{r y^{-1}}\),这是因为
同理,对于 \(\sigma = 1\) 的情况,接收方可以执行协议步骤计算 \(x_1\),并通过计算 \(w_0 / (u_0)^{ry}\) 得到 \(x_0\). 协议中,接收方需要通过零知识证明协议证明 \((g_0, g_1, h_0, \frac{h_1}{g_1})\) 是DH元组,从而确保接收方只能获得发送方的一个输入。
安全性证明需要分别考虑发送方 \(P_s\) 和接收方 \(P_r\) 被攻陷的情况。当发送方 \(P_s\) 被攻陷时,模拟器 \(\mathcal{S}\) 需要提取 \(P_s\) 的两个输入。\(\mathcal{S}\) 设置 \(\alpha_1 = \alpha_0\)(即 \((g_0, g_1, h_0, h_1)\) 是DH元组)并且“伪造”它的零知识证明,从而提取 \(P_s\) 的两个输入。当接收方 \(P_r\) 被攻陷时,模拟器 \(\mathcal{S}\) 可以提取零知识证明中的见证 \(\alpha_0\) 并计算 \(\alpha_1 = \alpha_0 + 1\). 通过检查 \(h = g^{\alpha_0}\) 还是 \(h = g^{\alpha_1}\),模拟器 \(\mathcal{S}\) 可以提取出接收方的选择比特 \(\sigma\).(注:我们对这里的“伪造证明”和“提取见证”作一点补充说明:考虑图 9.3的协议。需要“伪造证明”时,\(\mathcal{S}\) 先与验证者交互得到挑战值 \(s\),然后将验证者倒带,此时 \(\mathcal{S}\) 预先知道了 \(s\),就可以模拟出会话 \((A, B, s, z)\),它与真实会话不可区分(参考定理 9.1的证明)。需要“提取见证”时,\(\mathcal{S}\) 先与证明者交互得到会话 \((A, B, s, z)\),然后将证明者倒带,将挑战值换成 \(s'\),得到会话 \((A, B, s', z')\),基于2-特殊可靠性,可以提取见证 \(w\)(参考定理 9.1的证明),同时,因为在第一次与证明者交互时获得了 \(\alpha\) 的离散对数 \(a\),所以 \(\mathcal{S}\) 在第二次交互时可以将Pedersen承诺 \(c\) 打开为 \(s'\).)
证明某个子集是DH元组(CDS组合)。之前讲到,在切分选择OT中,接收方需要构造 \(s\) 对 \((h_0, h_1)\),并证明有 \(s/2\) 对不是DH元组。证明“不是DH元组”较为困难,接收方实际上证明 \((g_0, g_1, h_0, \frac{h_1}{g_1})\) 是DH元组。也就是说,接收方首先构造 \(\{(h_0^j, h_1^j)\}_{j \in [s]}\),然后证明有 \(s/2\) 个元组 \((g_0, g_1, h_0^j, \frac{h_1^j}{g_1})\) 是DH元组。为了符号的简洁,我们可以将接收方构造的元组记为 \(\{(h_0^j, \tilde{h}_1^j)\}_{j \in [s]}\),令 \(h_1^j = \frac{\tilde{h}_1^j}{g_1}\). 于是,我们需要构造关系 \(\mathcal{R}\) 的零知识证明来证明某个子集是DH元组,其中
我们刚才已经构造了DH元组的零知识证明(图 9.3)。现在,我们需要证明某个大小为 \(s/2\) 的子集是DH元组,并且不泄漏这个子集。这里采用的方法是Cramer,Damgård,Schoenmakers提出的CDS组合 [Cra et al., 1994]。CDS组合将Sigma协议与秘密分享相结合,构成了部分知识的证明(proof of partial knowledge)。协议如图 9.4所示。
协议中执行了 \(s\) 个DH元组的零知识证明的实例,但实际上只有 \(s/2\) 个元组是DH元组。对于这 \(s/2\) 个元组,证明者正常地执行DH元组的零知识证明协议;对于另外 \(s/2\) 个元组,证明者调用模拟器的算法模拟协议的会话,但这需要证明者先知道挑战值。为此,CDS组合巧妙地与秘密分享相结合:将验证者的总挑战值 \(c\) 看作秘密,将子挑战值 \(c_1, …, c_s\) 看作秘密份额。如果采用的是 \((s/2, s)\)-门限秘密分享方案,那么证明者可以自由选择 \(s/2\) 个秘密份额,从而模拟这些实例的会话;如果证明者自由选择了超过 \(s/2\) 个秘密份额,那么这些秘密份额就已经决定了秘密值 \(c\),它恰好与验证者随机选择的挑战值相等的概率是可忽略的。因此,上述协议具有可靠性。同时,模拟的协议会话和真实的协议会话不可区分,因此验证者无法知道哪些实例是DH元组,哪些实例是模拟的,确保了协议的零知识性。
切分选择OT的构造。至此,我们介绍了切分选择OT的所有子部件。我们给出切分选择OT协议的描述,如图 9.5所示。
注意,这里的“安全实现”考虑的是独立模型。根据前文所述的思路,模拟器 \(\mathcal{S}\) 的构造非常直接。当发送方 \(P_s\) 被攻陷时,\(\mathcal{S}\) 模拟接收方构造 \(s\) 对 \(\{(h_0^j, h_1^j)\}_{j \in [s]}\),它们全都是DH元组,然后“伪造”零知识证明,从而提取 \(P_s\) 的两个输入。当接收方 \(P_r\) 被攻陷时,\(\mathcal{S}\) 从 \(P_r\) 的零知识证明中提取出见证,从而提取出集合 \(\mathcal{J}\) 和 \(\{\sigma_j\}_{j \notin \mathcal{J}}\). 这里不再给出完整的证明,留作读者练习(注:如果读者在证明时遇到问题,本书的前言中有我的邮箱,欢迎与我交流。)。
单一选择切分选择OT. 如果我们希望接收方在所有OT实例中使用同样的选择比特 \(\sigma\),很自然地,图 9.5中的协议中传输阶段的第1步应该修改为:
这里的零知识证明协议证明的是:存在 \(r \in \mathbb{Z}_q\) 满足“ \(g' = (g_0)^r\) 且对于 \(j \in [s]\) 有 \(h_j = (h_0^j)^r\) ”或“ \(g' = (g_1)^r\) 且对于 \(j \in [s]\) 有 \(h_j = (h_1^j)^r\) ”。换句话说,需要证明 \(\{(g_0, g', h_0^j, h_j)\}_{j \in [s]}\) 都是DH元组或者 \(\{(g_1, g', h_1^j, h_j)\}_{j \in [s]}\) 都是DH元组。该协议如图 9.6所示。
该定理的证明同样非常直接,留作读者练习。
批处理单一选择切分选择OT. 最后,我们的协议需要让计算方对每一条导线执行单一选择切分选择OT,并且在每一个实例中使用同样的集合 \(\mathcal{J}\). 我们将这个理想功能记为 \(\mathcal{F}_{\mathsf{CCOT}}^{S, B}\),如图 9.16所示。
要实现理想功能 \(\mathcal{F}_{\mathsf{CCOT}}^{S, B}\),我们只运行一次切分选择OT协议(图 9.5)的准备阶段,这样就确保了在所有实例中都使用了相同的集合 \(\mathcal{J}\). 然后,对于每个 \(i \in [\ell]\),运行单一选择切分选择OT协议的传输阶段(可以并行地运行)。如此,我们就完成了批处理单一选择切分选择OT协议的构造。
总结。本节,我们从PVW协议开始,利用其特殊的性质(当公共参考字符串是DH元组时可以获得两个输入),构造了切分选择OT. 然后,我们又在此基础上构造了单一选择切分选择OT和批处理单一选择切分选择OT. 在协议中,我们多次使用了基于Sigma协议的零知识证明。至此,我们完成了协议中最重要的原语的构造。
输入一致性零知识证明
接下来,我们来构造另一个原语——输入一致性零知识证明。我们前面讲过,LP11协议中,\(P_1\) 首先选择值 \(g^{a_1^0}, g^{a_1^1}, \dots, g^{a_\ell^0}, g^{a_\ell^1}\) 以及 \(g^{r_1}, \dots, g^{r_s}\),然后将第 \(i\) 个输入比特在第 \(j\) 个电路中的密钥设置为 \(g^{a_i^0 \cdot r_j}, g^{a_i^1 \cdot r_j}, \; i \in [\ell], \; j \in [s]\). 对于每个输入比特(即对于每个 \(i \in [\ell]\)),将 \(P_1\) 的密钥记为 \(k_{i, 1}, \dots, k_{i, s}\). 令 \(h_{i, 0} = g^{a_i^0}, \; h_{i, 1} = g^{a_i^1}, \; u_1 = g^{r_1}, \dots, u_s = g^{r_s}\). 该零知识证明协议证明的是:存在 \(a \in \mathbb{Z}_q\) 满足“ \(h_{i, 0} = g^a\) 且对于 \(j \in [s]\) 有 \(k_{i, j} = (u_j)^a\) ”或“ \(h_{i, 1} = g^a\) 且对于 \(j \in [s]\) 有 \(k_{i, j} = (u_j)^a\) ”。该证明与图 9.6的零知识证明非常类似,如图 9.7所示。
协议描述
现在,我们给出LP11协议的完整描述。我们首先给出协议每一步的直观解释。我们将打开的电路称为“检查电路”(check-circuit),未打开的电路称为“计算电路”(evaluation-circuit)。
步骤1:\(P_1\) 构造 \(s\) 个混淆电路。这些混淆电路中,\(P_1\) 的输入导线密钥通过特殊的方式来选择:\(P_1\) 首先选择随机数 \(a_1^0, a_1^1, …, a_\ell^0, a_\ell^1\)(\(P_1\) 的输入长度为 \(\ell\))和 \(r_1, …, r_s\),然后将第 \(j\) 个电路中的第 \(i\) 个输入导线的密钥设置为 \(g^{a_i^0 \cdot r_j}, g^{a_i^1 \cdot r_j}\). 此时,\(g^{a_1^0}, g^{a_1^1}, …, g^{a_\ell^0}, g^{a_\ell^1}, g^{r_1}, …, g^{r_s}\) 构成了 \(P_1\) 的输入密钥的承诺(注:实际上,\(P_1\) 的密钥设置为 \(H(g^{a_i^0 \cdot r_j}), H(g^{a_i^1 \cdot r_j})\),\(H\) 是随机数提取器,参见图 9.8的协议描述。)。
步骤2:参与双方执行批处理单一选择切分选择OT,其中 \(P_1\) 的输入是所有电路中 \(P_2\) 的所有输入导线的密钥,\(P_2\) 的输入是他的协议输入和大小为 \(s/2\) 的随机集合 \(\mathcal{J} \subset [s]\). 于是,对于“检查电路”(索引在 \(\mathcal{J}\) 中的电路),\(P_2\) 获得两个密钥,对于“计算电路”,\(P_2\) 获得其输入对应的密钥。
步骤3:\(P_1\) 给 \(P_2\) 发送 \(s\) 个混淆电路以及 \(P_1\) 的输入密钥的承诺 \(g^{a_1^0}, g^{a_1^1}, …, g^{a_\ell^0}, g^{a_\ell^1}, g^{r_1}, …, g^{r_s}\). 此时,\(P_1\) 已经对 \(s\) 个电路做了承诺,但还不知道要打开哪些电路。
步骤4:\(P_2\) 向 \(P_1\) 展示“检查电路”的集合 \(\mathcal{J}\),并发送这些电路中 \(P_2\) 的第一个输入比特对应的两个密钥以证明其正确性。注意,只有“检查电路” \(P_2\) 才能知道两个密钥。
步骤5:对于“检查电路”,\(P_2\) 需要知道 \(P_1\) 的输入导线密钥才能检查正确性。因此,对于 \(j \in \mathcal{J}\),\(P_1\) 发送 \(r_j\) 给 \(P_2\). 于是,\(P_2\) 可以根据 \(g^{a_i^0}, g^{a_i^1}, r_j\) 来计算 \(g^{a_i^0 \cdot r_j}, g^{a_i^1 \cdot r_j}\),并且这不会泄露“计算电路”中的密钥。
步骤6:\(P_2\) 检查 \(s/2\) 个“检查电路”的正确性,如果存在错误,\(P_2\) 终止协议。如果“检查电路”都是正确的,那么大多数“计算电路”(以压倒性的概率)是正确的。
步骤7:\(P_1\) 向 \(P_2\) 发送“计算电路”中 \(P_1\) 的输入密钥,即,对于“计算电路” \(j\) 的第 \(i\) 条导线,\(P_1\) 向 \(P_2\) 发送 \(g^{a_i^{x_i} \cdot r_j}\),其中 \(x_i\) 是 \(P_1\) 的第 \(i\) 个输入比特。\(P_1\) 通过上述输入一致性零知识证明(图 9.7) 高效地证明所有密钥使用了相同的 \(a_i^{x_i}\).
步骤8:\(P_2\) 计算所有“计算电路”,取大多数电路的输出作为协议输出。注意,即使输出不一致,\(P_2\) 也不能中止协议,否则可能泄露信息(见「直观思想」一节)。由于在恶意敌手模型下,双方获得输出和只有一个参与方获得输出是等价的,因此我们考虑只有 \(P_2\) 获得输出的简单情况(见「直观思想」一节)。
协议描述如图 9.8所示。
安全性证明
直观上看,如果所有的“检查电路”都是正确的,那么大多数“计算电路”以压倒性的概率是正确的。另一方面,基于DDH假设,\(P_2\) 从 \(g^{a_1^0}, g^{a_1^1}, \dots, g^{a_\ell^0}, g^{a_\ell^1}, g^{r_1}, \dots, g^{r_s}\) 不能获得输入导线密钥的任何信息。因此,协议有两个安全参数:混淆电路的数量 \(s\) 是统计安全参数,\(n = |q|\) 是计算安全参数,其中 \(q\) 是群 \(\mathbb{G}\) 的阶。
下面,我们首先在独立模型下给出严格的安全性证明(考虑只有 \(P_2\) 获得输出的等价定义)。然后,我们讨论协议的UC安全性。
该断言在「直观思想」一节已经推导过。
UC安全性。到目前为止,本节的所有定理考虑的都是独立模型下的安全性。但是,注意到我们的证明中,只有提取零知识证明的见证时使用了倒带技术,其他步骤无需将敌手倒带。因此,如果能将Sigma协议替换成UC安全的零知识证明协议,那么整个协议就变成UC安全的了。在公共参考字符串(Common Reference String, CRS)模型下,存在将Sigma协议转化为UC安全的零知识证明的高效构造 [Dod et al., 2008; Gar et al., 2003]。于是,我们有以下定理。
BGW协议(恶意安全)
直观思想
在第3章和「BGW协议(半诚实安全)」一节,我们介绍了BGW协议的半诚实安全版本,它对于半诚实的敌手具有完美安全性。然而,如果敌手是恶意的,那么他有多种攻击协议的方式。假设参与方 \(P_1\) 是被攻陷的,且输入为 \(s\). 首先,在输入分享阶段,\(P_1\) 应该选择一个 \(t\) 阶(注:更准确地说,“\(t\) 阶”应该是“至多 \(t\) 阶”。在均匀随机选取的情况下,多项式阶数不为 \(t\) 的概率为 \(1 / |\mathbb{F}|\),其中 \(\mathbb{F}\) 是使用的域。为了表述的简洁,本章中通常省略“至多”。)多项式 \(q(\cdot)\),满足 \(q(0) = s\),并将秘密份额 \(q(\alpha_i)\) 发送给 \(P_i\). 但是,恶意的 \(P_1\) 可以选择一个阶数大于 \(t\) 的多项式 \(q(\cdot)\),将 \(q(\alpha_i)\) 发送给 \(P_i\),这样一来,任意 \(t + 1\) 个秘密份额都会重建出不同的值,因而 \(P_1\) 的输入是没有被良好定义的。其次,在输出重建阶段,假设输出值为 \(y\),参与方持有 \(y\) 的秘密份额,他们应该公布这些秘密份额来重建输出。但是,恶意的参与方可以公布错误的秘密份额,其他参与方无法知道哪些份额是正确的,哪些是错误的。因此,协议必须提供以下性质:假设一共有 \(n\) 个参与方,被攻陷的参与方不超过 \(t\) 个,输出重建时可以基于 \(n - t\) 个正确的份额和 \(t\) 个错误的份额重建输出值。
对于前一种攻击,解决方案为可验证秘密分享(Verifiable Secret Sharing, VSS)。顾名思义,可验证秘密分享VSS允许其他参与方“验证”(恶意的)秘密分发者(dealer)正确地分享了某个秘密,即秘密值是被良好定义的(注:对于恶意的参与方,我们无法阻止其替换自己的输入。)。对于后一种攻击,解决方案为纠错码(error-correcting code)。一个纠错码的码字(codeword)包含多个元素,当其中有部分元素丢失或错误时(注:一个具体的例子是,在通信传输的过程中,可能有部分信息发生丢失或错误。),如果数量不超过阈值,我们就可以将其“纠正”为原始的正确码字。(注:本节参考了文献[Ash & Lin, 2017]。)
可验证秘密分享。回想一下,在 \((t, n)\)-Shamir秘密分享方案中,参与方首先选定 \(n\) 个互不相同且不为0的值 \((\alpha_1, …, \alpha_n)\). 要分享某个值 \(s\),秘密分享算法首先选择阶数最多为 \(t\) 的随机多项式 \(q(\cdot)\),满足 \(q(0) = s\),然后将秘密份额 \(q(\alpha_i)\) 发送给 \(P_i\). 然而,恶意的秘密分发者可能会违背协议,例如,选择阶数大于 \(t\) 的多项式 \(q(\cdot)\),要想可验证地进行秘密分享,我们可能有以下想法:
参与方共同确定一个以 \(g\) 为生成元的循环群 \(\mathbb{G}\). 算法随机选择 \(q(x) = a_0 + a_1 x + \dots + a_t x^t\),其中 \(a_0 = s\),并公布验证值 \(A_k = g^{a_k}, \; k = 0, \dots, t\),然后将秘密份额 \(s_i = q(\alpha_i)\) 发送给 \(P_i\). \(P_i\) 验证
\[g^{s_i} \stackrel{?}{=} \prod\limits_{k=0}^t (A_k)^{(\alpha_i)^k}\]这种方式被称为Feldman VSS.参与方共同确定一个以 \(g\) 为生成元的循环群 \(\mathbb{G}\),以及元素 \(h\),满足 \(\log_g h\) 未知。算法随机选择 \(q(x) = a_0 + a_1 x + \dots + a_t x^t\) 和 \(q'(x) = b_0 + b_1 x + \dots + b_t x^t\),其中 \(a_0 = s\),并公布验证值 \(C_k = g^{a_k} h^{b_k}, \; k = 0, \dots, t\),然后将秘密份额 \((s_i, s'_i) = ( q(\alpha_i), q'(\alpha_i) )\) 发送给 \(P_i\). \(P_i\) 验证
\[g^{s_i} h^{s'_i} \stackrel{?}{=} \prod\limits_{k=0}^t (C_k)^{(\alpha_i)^k}\]这种方式被称为Pedersen VSS.
直观上看,上述两种VSS方案在离散对数(Discrete-Log)假设下,对于多项式时间的敌手实现了可验证性(注:可验证性指:如果验证通过,那么任意 \(t + 1\) 个秘密份额插值将得到同样的(不超过 \(t\) 阶的)多项式,即秘密分发者正确地进行了秘密分享。)(注:如果 \(P_i\) 发现秘密份额不满足验证条件,他将提出投诉(complaint),然后,参与方将执行协议的“投诉解决”机制,这部分并非本段的重点,因此略去,读者可参阅文献 [GJKR, 2007]。 )。然而,它们都不能实现完美安全性。对于Feldman VSS,如果参与方有无限的计算力,他可以求解 \(A_k = g^{a_k}\) 的离散对数,得到 \(a_k\),从而打破隐私性;对于Pedersen VSS,虽然验证值 \(C_k = g^{a_k} h^{b_k}\) 完美地隐藏了 \(a_k\),但如果秘密分发者有无限的计算力,他求解 \(h\) 的离散对数,然后就可以任意选择 \(s_i\),再计算满足 \(g^{s_i} h^{s'_i} = \prod\limits_{k=0}^t (C_k)^{(\alpha_i)^k}\) 的 \(s'_i\),从而打破正确性。
BGW的可验证秘密分享在 \(t < n/3\) 的条件下实现了完美安全性,这是因为Shamir秘密分享本质上是Reed-Solomon纠错码。下面,我们详细阐述。
纠错码(Reed-Solomon码)。Reed-Solomon码是一种线性码(linear code),线性码是一种特殊的纠错码,线性码的码字的线性组合也是合法的码字。线性码有三个参数 \([n, k, d]\). 在大小为 \(q\) 的有限域 \(\mathbb{F}\) 上的 \([n, k, d]\)-线性码,指的是其长度为 \(n\)(每个码字包含 \(n\) 个域上的元素),维度(dimension)为 \(k\)(共有 \(q^k\) 个不同的码字),距离为 \(d\)(两个码字的汉明距离(Hamming distance)至少为 \(d\))。
BGW协议需要构造一种长度为 \(n\),维度为 \(k = t + 1\),距离为 \(n - t\) 的线性码。其对应的Reed-Solomon码构造如下。令 \(\mathbb{F}\) 是一个有限域,满足 \(|\mathbb{F}| > n\). 令 \(\alpha_1, …, \alpha_n\) 为域上各不相同的值。令 \(m = (m_0, …, m_t)\) 是要被编码的消息,其中 \(m_i \in \mathbb{F}, \; i \in [t]\). 编码算法如下:
定义最高 \(t\) 阶的多项式 \(p_m(x) = m_0 + m_1 x + … + m_t x^t\).
计算码字 \(C(m) = \langle p_m(\alpha_1), …, p_m(\alpha_n) \rangle\).
不难看出,该编码的距离为 \(n - t\)(因为任意两个至多 \(t\) 阶的多项式,最多有 \(t\) 个 \(\alpha\) 点满足 \(p_1(\alpha) = p_2(\alpha)\). 而两个不同的消息 \(m \neq m'\) 定义了两个不同的多项式 \(p_m \neq p_{m'}\),故 \(C(m)\) 和 \(C(m')\) 最多有 \(t\) 处相同)。用 \(d(x, y)\) 来表示码字 \(x, y \in \mathbb{F}^n\) 的汉明距离,我们有以下编码理论中著名的定理。
当 \(t < n/3\) 时,\(n \geq 3t + 1\). 将 \(n = 3t + 1\) 代入上述定理可知,此时我们可以高效地纠正 \(\frac{3t+1-t-1}{2} = t\) 个错误。在BGW协议中,参与方使用Shamir秘密分享方案。假设 \(n\) 个参与方持有秘密份额 \(\{q(\alpha_i)\}_{i \in [n]}\),其中 \(q(\cdot)\) 是至多 \(t\) 阶的多项式,\(q(0) = s\). 我们可以把秘密份额 \(\langle q(\alpha_1), …, q(\alpha_n) \rangle\) 看成Reed-Solomon码字。当需要重建秘密值时,参与方直接广播自己的秘密份额。诚实的参与方一定会广播正确的份额,而被攻陷方可能会广播错误值。但是,由于被攻陷方的数量 \(t < n/3\),最多有 \(t\) 个错误值,因此诚实方可以运行Reed-Solomon解码算法高效地恢复出正确的多项式 \(q(\cdot)\),并计算 \(q(0) = s\).
我们用 \(\mathcal{B}^{s, t}\) 表示常数项为 \(s\) 的 \(t\) 阶二元多项式的集合。那么,对于一个属于 \(\mathcal{B}^{s, t}\) 的二元多项式,它的系数的数量为 \((t + 1)^2 - 1 = t^2 + 2t\)(总共有 \((t + 1)^2\) 个系数,但常数项已经被固定为 \(s\))。
在第3章中,我们论证了:\(t + 1\) 个(横坐标不同的)点唯一确定一个 \(t\) 阶多项式,即,给定 \(t + 1\) 个点 \(\{(\alpha_k, \beta_k)\}_{k=1}^{t+1}\),存在唯一的 \(t\) 阶多项式 \(f\) 满足 \(f(\alpha_k) = \beta_k\). 将其推广到二元多项式,直觉上,我们可能会猜测以下结论成立:\(t + 1\) 个 \(t\) 阶一元多项式唯一确定一个 \(t\) 阶二元多项式。具体而言,对于 \(t\) 阶二元多项式 \(S(x, y)\),固定 \(y\) 为某个值 \(\alpha\) 就得到一个 \(t\) 阶一元多项式 \(f(x) = S(x, \alpha)\). 于是,\(t + 1\) 个(互不相同的)值 \(\alpha_1, …, \alpha_{t+1}\) 定义了 \(t + 1\) 个 \(t\) 阶一元多项式 \(f_k(x) = S(x, \alpha_k)\). 反过来,给定 \(t + 1\) 个(互不相同的)值 \(\alpha_1, …, \alpha_{t+1}\) 和 \(t + 1\) 个 \(t\) 阶一元多项式 \(f_1(x), …, f_{t+1}(x)\),应该存在唯一的 \(t\) 阶二元多项式 \(S(x, y)\),满足 \(S(x, \alpha_k) = f_k(x), \; k = 1, …, t + 1\). 我们把上述猜想形式化地写成以下引理。
可以提前告诉读者:该引理是正确的。但为了在本节一次性地连贯介绍BGW协议的总体思路,我们将该引理的证明放在下一小节。
使用二元多项式进行可验证秘密分享。沿着引理 9.1的思路,我们首先将 \(t\) 阶一元多项式 \(q(z)\) “嵌入”二元多项式 \(S(x, y)\) 中,其中 \(q(0) = s\). 具体而言,\(S(x, y)\) 是均匀随机选择的 \(t\) 阶二元多项式,但满足条件 \(S(0, z) = q(z)\). 于是,\(q(\alpha_1), …, q(\alpha_n)\) 就是嵌入 \(S(x, y)\) 的Shamir秘密份额。然后,秘密分发者向 \(P_i\) 发送两个一元多项式 \(f_i(x) = S(x, \alpha_i), \; g_i(y) = S(\alpha_i, y)\). 根据定义,它们满足 \(f_i(\alpha_j) = S(\alpha_j, \alpha_i) = g_j(\alpha_i), \; g_i(\alpha_j) = S(\alpha_i, \alpha_j) = f_j(\alpha_i)\). 这样一来,任意两个参与方 \(P_i\) 和 \(P_j\) 就可以通过检查 \(f_i(\alpha_j) \stackrel{?}{=} g_j(\alpha_i)\) 和 \(g_i(\alpha_j) \stackrel{?}{=} f_j(\alpha_i)\) 来验证他们收到的多项式是否两两一致(consistent)。\(P_i\) 还需要检查自己的多项式是否满足 \(f_i(\alpha_i) \stackrel{?}{=} g_i(\alpha_i)\). 如果验证均通过,\(P_i\) 输出自己的秘密份额为 \(f_i(0) = q(\alpha_i)\).
接下来,我们分析一下该方案的正确性和隐私性。
基于引理 9.1,不难证明引理 9.2是正确的。同样,我们将该引理的证明放在下一小节。
我们还需要证明隐私性,也就是说,被攻陷方接收到的多项式 \(\{f_i(x), g_i(y)\}_{i \in I}, | I | \leq t\) 不会泄露关于 \(s\) 的信息。实际上,我们可以证明一个更强的引理:对于任意两个多项式 \(q_1, q_2\),满足 \(q_1(\alpha_i) = q_2(\alpha_i) = f_i(0)\) 对 \(i \in I\) 都成立,当 \(S(x, y)\) 基于 \(q_1(z)\) 选择时,多项式集合 \(\{f_i(x), g_i(y)\}_{i \in I}\) 的分布与 \(S(x, y)\) 基于 \(q_2(z)\) 选择时 \(\{f_i(x), g_i(y)\}_{i \in I}\) 的分布是相同的。由此得到的推论是:\(\{f_i(x), g_i(y)\}_{i \in I}\) 不会泄露关于秘密是 \(s_1 = q_1(0)\) 还是 \(s_2 = q_2(0)\) 的任何信息。
该引理的证明与一元多项式的情形类似,实际上是二元情形的推广。同样,我们将该引理的证明放在下一小节。
如果有人提出投诉(complaint)?按照上述协议,如果所有验证都通过,没有参与方提出投诉,那么一切非常美好——被分享的秘密是良好定义的,且不会泄露任何信息。但是,如果有参与方提出投诉,表示他接收到的份额不满足 \(f_i(\alpha_j) = g_j(\alpha_i)\) 和 \(g_i(\alpha_j) = f_j(\alpha_i)\),此时,协议该如何处理呢?
这里我们假设存在认证的(authenticated)广播信道(即广播者的身份是已知的)。对于参与方 \(P_j\),按照协议,他从 \(P_i\) 处收到 \(f_i(\alpha_j), g_i(\alpha_j)\),如果 \(f_j(\alpha_i) \neq g_i(\alpha_j)\) 或 \(g_j(\alpha_i) \neq f_i(\alpha_j)\),这有可能是因为秘密分发者是被攻陷的,或 \(P_i\) 是被攻陷的。此时,\(P_j\) 广播 \((j, i, f_j(\alpha_i), g_j(\alpha_i))\) 来提出投诉. 注意,这里的 \(f_j(\alpha_i), g_j(\alpha_i)\) 是由秘密分发者发给 \(P_j\) 的多项式 \(f_j(x), g_j(y)\) 所定义的。然后,秘密分发者检查 \(f_j(\alpha_i), g_j(\alpha_i)\) 的值是否正确,如果正确,那就什么都不做;如果不正确,秘密分发者广播正确的多项式 \(f_j(x), g_j(y)\),然后其他参与方检查 \(f_j(x), g_j(y)\) 与自己的多项式是否一致。
在秘密分发者是诚实的情况下,容易看出上述方案是可行的。因为这种情况下,所有诚实方一定会获得一致的多项式,投诉只可能是因为被攻陷方提出错误的投诉(此时秘密分发者会广播他的多项式,这不会给被攻陷方带来更多信息),或者被攻陷方向诚实方发送错误的值(此时秘密分发者不会广播诚实方的多项式)。但是,在秘密分发者是被攻陷的情况下,协议必须保证:在投诉解决阶段,除非秘密分发者重新向所有诚实方发送了一致的多项式,否则所有诚实方都应该拒绝并输出 \(\bot\). 因此,投诉解决的方案需要小心的设计。我们先给出完整的协议,如图 9.9所示,然后再解释其原理。
首先,对于秘密分发者是诚实的情况,正如上面的分析,所有诚实方都将获得一致的多项式,因此至少 \(n - t\) 个参与方会广播 \(\mathsf{consistent}\)(至少有 \(n - t\) 个诚实方),最后诚实的参与方 \(P_j\) 将输出 \(f_j(0) = S(0, \alpha_j) = q(\alpha_j)\).
对于秘密分发者是被攻陷的情况,诚实方 \(P_j\) 和 \(P_k\) 有可能收到不一致的多项式。如果他们收到了不一致的多项式,即 \(f_j(x), g_j(y)\) 和 \(f_k(x), g_k(y)\) 满足 \(f_j(\alpha_k) \neq g_k(\alpha_j)\) 或 \(g_j(\alpha_k) \neq f_k(\alpha_j)\),那么他们都会投诉,构成 \(\mathsf{joint \text{ } complaint}\). 然后,秘密分发者必须对此广播一条 \(\mathsf{reveal}\) 消息来解决投诉。要让 \(n - t\) 个参与方广播 \(\mathsf{consistent}\),至少要有 \((n - t) - t \geq t + 1\) 个诚实方广播 \(\mathsf{consistent}\). 这也就代表着,\(t + 1\) 个(或更多)诚实方在第1轮就收到了与 \(\mathsf{reveal}\) 消息中的新多项式两两一致的多项式,根据引理 9.2,这 \(t + 1\) 个(或更多)多项式已经唯一确定了二元多项式 \(S(x, y)\).
最后,我们还需要说明:那些没有广播 \(\mathsf{consistent}\) 的诚实方的多项式,也是来自同样的二元多项式 \(S(x, y)\) 的。这里用反证法。假设存在诚实方 \(P_j\) 满足 \(f_j(x) \neq S(x, \alpha_j)\)(\(g_j(y) \neq S(\alpha_j, y)\) 的情况同理),由于 \(f_j(x)\) 至多为 \(t\) 阶,因此 \(f_j(\alpha_k) = S(\alpha_k, \alpha_j)\) 最多对于 \(t\) 个 \(\alpha_k\) 成立。所以,\(P_j\) 的多项式上的点最多与 \(t\) 个广播了 \(\mathsf{consistent}\) 的诚实方相一致(广播了 \(\mathsf{consistent}\) 的诚实方都有 \(g_k(\alpha_j) = S(\alpha_k, \alpha_j)\))。而现在至少有 \(t + 1\) 个诚实方广播了 \(\mathsf{consistent}\),因此,\(P_j\) 必定和某个广播了 \(\mathsf{consistent}\) 的诚实方有 \(\mathsf{joint \text{ } complaint}\),并且已经被 \(\mathsf{reveal}\) 消息解决了,那么,\(P_j\) 更新后的多项式也是与 \(S(x, y)\) 相一致的。至此,我们完成了BGW可验证秘密分享的分析。
乘法协议。但是协议到这里还没有结束,回想一下,在半诚实安全的BGW协议中,对输入进行秘密分享后,我们需要逐个计算电路中的算术门。加法门与常数乘法门是线性操作,可以在本地完成,我们还需要设计一个对于恶意敌手安全的乘法协议。
假设乘法门的输入导线值为 \(a\) 和 \(b\),参与方 \(P_i\) 持有 \(t\) 阶的秘密份额 \(a_i\) 和 \(b_i\). 秘密份额的乘积 \(a_i \cdot b_i\) 定义了一个 \(2t\) 阶的多项式,其常数项为 \(a \cdot b\). 在半诚实安全的BGW协议中,\(P_i\) 对份额 \(a_i \cdot b_i\) 再进行秘密分享,然后将子份额线性重组,从而降阶为 \(t\) 阶多项式,其常数项仍为 \(a \cdot b\). 在恶意敌手模型下,难题在于:被攻陷方不一定会秘密分享正确的 \(a_i \cdot b_i\). 上文的可验证秘密分享只能保证被分享的秘密是被良好定义的,我们还需要一个机制来强制参与方秘密分享 \(a_i \cdot b_i\).
为此,乘法协议总体分为三步:
每个参与方首先可验证地秘密分享他们输入导线上的份额,即,\(P_i\) 对秘密份额 \(a_i\) 和 \(b_i\) 进行秘密分享。因为输入份额位于 \(t\) 阶多项式上,它们构成以 \([n, t + 1, n - t]\) 为参数的Reed-Solomon码,因此可以通过纠错码的性质纠正最多 \(t\) 个错误,使每个参与方得到正确的子份额。
然后,每个参与方秘密分享 \(a_i \cdot b_i\). 由于上一步已经对 \(a_i\) 和 \(b_i\) 正确地秘密分享,因此这一步也能够可验证的进行。换句话说,此步骤中,参与方在已知 \(a_i\) 和 \(b_i\) 的子份额的情况下,验证秘密分发者正确地秘密分享了 \(a_i \cdot b_i\).
最后,每个参与方持有了 \(a_i \cdot b_i\) 的(\(t\) 阶的)子份额。与半诚实安全的BGW协议中相同,他们将子份额线性重组,得到的份额落在新的 \(t\) 阶多项式上,其常数项为 \(a \cdot b\).
这里,步骤1和2讲得有些模糊,因为协议较为复杂,实在无法用几句话概括总体思想。后文中会对其详细阐释。
协议概览。最后,我们总结一下恶意安全的BGW协议的总体流程。假设被攻陷方的数量不超过 \(t\),\(t < n/3\),参与方存在点对点的安全信道和认证的广播信道。
输入分享:每个参与方使用上文所述的可验证秘密分享协议分享自己的输入。
逐门计算:对于加法门和常数乘法门,在本地对秘密份额进行相应的计算;对于乘法门,调用乘法协议进行计算。
输出重建:对于输出值 \(y\),每个参与方广播自己的秘密份额 \(y_i\),然后调用Reed-Solomon解码算法恢复出 \(y\) 值。
下面,我们开始进行形式化的协议描述和安全性证明。我们将采用模块化的方式,将可验证秘密分享和乘法协议抽象为理想功能 \(\mathcal{F}_{\mathsf{VSS}}\) 和 \(\mathcal{F}_{\mathsf{mult}}\),然后在 \(\{\mathcal{F}_{\mathsf{VSS}}, \mathcal{F}_{\mathsf{mult}}\}\)-混合模型下实现安全计算协议。
准备工作——Shamir秘密分享的性质与引理证明
在开始正式的协议描述之前,让我们先做一些准备工作:我们给出关于Shamir秘密分享性质的几个引理和推论,以及在上一节中省略的引理证明。
Shamir秘密分享的性质。在「Shamir秘密分享」一节中,我们证明了:任意 \(t\) 个Shamir秘密份额是 \(\mathbb{F}^t\) 上的均匀分布。我们用 \(\mathcal{P}^{s, t}\) 表示常数项为 \(s\),阶数不超过 \(t\) 的所有多项式的集合。上述性质可以写成如下引理。
很直接地,对于任意的两个秘密 \(s, s'\),有如下推论。
在实际协议中,每个参与方都需要分享自己的输入。假设共有 \(m\) 个输入,被攻陷方将收到 \(m \cdot | I |\) 个秘密份额。我们将上述结论推广:\(m \cdot | I |\) 个秘密份额也不会泄露关于秘密的任何信息。这是因为这些份额服从 \(\mathbb{F}^{m \cdot | I |}\) 上的均匀分布。
在Shamir秘密分享方案中,秘密分发者随机选取至多 \(t\) 阶的多项式,其常数项为秘密 \(s\). 我们考虑另一种选取多项式的方式,它将最高次项系数(leading coefficient)固定为秘密 \(s\),即 \(f(x) = a_0 + a_1 x + … + a_{t-1} x^{t-1} + s x^t\). 我们用 \(\mathcal{P}^\mathsf{lead}_{s, t}\) 表示最高次项 \(x^t\) 系数为 \(s\) 的所有 \(t\) 阶多项式的集合。与引理 9.4的证明过程类似,此时的秘密份额 \(\{ f(\alpha_i) \}_{i \in I}\) 仍为 \(\mathbb{F}^{| I |}\) 上的均匀随机分布。(注:这个引理是为证明后文中的定理做准备。)
\(\) 引理 9.9. (BGW VSS正确性)令 \(K \subseteq [n]\) 是索引的集合,满足 \(|K| \geq t + 1\),令 \(\{f_k(x), g_k(y)\}_{k \in K}\) 是 \(t\) 阶多项式对的集合,令 \(\{\alpha_k\}_{k \in K}\) 是域 \(\mathbb{F}\) 上互不相同的非0元素。如果对于所有 \(i, j \in K\),都有 \(f_i(\alpha_j) = g_j(\alpha_i)\),那么存在唯一的 \(t\) 阶二元多项式 \(S\),满足 \(f_k(x) = S(x, \alpha_k)\) 和 \(g_k(y) = S(\alpha_k, y)\) 对所有 \(k \in K\) 都成立。
其中,\(S_1(x, y)\) 和 \(S_2(x, y)\) 是在约束条件 \(S_1(0, z) = q_1(z)\) 和 \(S_2(0, z) = q_2(z)\) 下均匀随机选择的 \(t\) 阶二元多项式。
BGW可验证秘密分享
接下来,我们正式进入BGW协议的介绍。我们首先介绍BGW可验证秘密分享,它的协议已经在上文的讨论中给出,如图 9.9所示。现在,我们要形式化地证明其安全性。
首先,我们定义理想功能 \(\mathcal{F}_{\mathsf{VSS}}\),如图 9.17所示。
在理想功能 \(\mathcal{F}_{\mathsf{VSS}}\) 中,秘密分发者的输入是多项式 \(q(x)\),其他参与方没有输入;协议的输出是 \(P_i\) 获得秘密份额 \(q(\alpha_i)\). 这里的“可验证性”体现在:(1) 如果 \(q\) 的阶数高于 \(t\),那么所有参与方都会拒绝并输出 \(\bot\);(2) 秘密 \(s = q(0)\) 被隐式地定义了,因而一定是良好定义的。当参与方需要可验证地分享秘密 \(s\) 时,秘密分发者首先随机选取多项式 \(q \leftarrow_{\$} \mathcal{P}^{s, t}\),然后以 \(q(x)\) 为输入运行 \(\mathcal{F}_{\mathsf{VSS}}\) 即可。
注意,这里的 \(\mathcal{F}_{\mathsf{VSS}}\) 是专门为BGW协议而定义的,我们也可以定义一种更广义的VSS(类似于多方场景下的承诺)。但因为BGW协议只需要对秘密份额 \(q(\alpha_1), …, q(\alpha_n)\) 做计算,所以我们采用这种更简单的定义方式。
我们有以下安全性定理。
乘法协议
假设乘法门的输入导线值为 \(a\) 和 \(b\),参与方 \(P_i\) 持有 \(t\) 阶的秘密份额 \(a_i\) 和 \(b_i\). 前文讲过,乘法协议分为三步:
每个参与方 \(P_i\) 可验证地秘密分享他们输入导线上的份额 \(a_i\) 和 \(b_i\).
在持有 \(a_i\) 和 \(b_i\) 的子份额的情况下,每个参与方 \(P_i\) 可验证地秘密分享 \(a_i \cdot b_i\).
将 \(a_i \cdot b_i\) 的子份额线性重组,得到的份额落在新的 \(t\) 阶多项式上,其常数项为 \(a \cdot b\).
下面,我们详细介绍每一步的具体实现。我们的协议描述采用模块化的方式:步骤1被抽象为理想功能 \(\mathcal{F}_{\mathsf{VSS}}^\mathsf{subshare}\)(见「实现子份额秘密分享理想功能 F_VSS^subshare」一节),为实现该理想功能,我们先定义并行可验证秘密分享理想功能 \(\mathcal{F}_{\mathsf{VSS}}^n\)(见「定义并行可验证秘密分享理想功能 F_VSS^n」一节)以及实现矩阵乘法理想功能 \(\mathcal{F}_{\mathsf{mat}}^{\boldsymbol A}\)(见「实现矩阵乘法理想功能 F_mat^ A」一节);步骤2被抽象为理想功能 \(\mathcal{F}_{\mathsf{VSS}}^\mathsf{mult}\)(见「实现乘积子份额秘密分享理想功能 F_VSS^mult」一节),为实现该理想功能,我们需要先实现多项式求值理想功能 \(\mathcal{F}_{\mathsf{eval}}\)(见「实现多项式求值理想功能 F_eval」一节);最后,基于 \(\mathcal{F}_{\mathsf{VSS}}^\mathsf{subshare}\) 与 \(\mathcal{F}_{\mathsf{VSS}}^\mathsf{mult}\),再加上步骤3,我们在「实现乘法理想功能 F_mult」一节实现了乘法理想功能 \(\mathcal{F}_{\mathsf{mult}}\).
定义并行可验证秘密分享理想功能 \(\mathcal{F}_{\mathsf{VSS}}^n\)
在BGW协议的输入分享阶段,每个参与方作为秘密分发者运行可验证秘密分享协议,分发自己输入的秘密份额。也就是说,参与方运行 \(n\) 个VSS实例,在第 \(i\) 个实例中 \(P_i\) 是秘密分发者并以 \(q_i(x)\) 作为协议输入。我们需要定义一个理想功能来描述并行地运行VSS所满足的安全性。直观上看,它应该保证所有被分享的秘密是互相独立的,我们可能有以下初步的想法,如图 9.18所示:
直观上看,该理想功能似乎刻画了并行VSS所应该满足的安全性质。然而,在实际执行中,由于 \(n\) 个VSS实例是并行运行的,敌手可能采取这样的行为:他首先接收诚实方发送的秘密份额,然后再决定他要分享的秘密。也就是说,敌手可以在看到诚实方发给被攻陷方的秘密份额后,再基于这些秘密份额选择被攻陷方的输入多项式(这类敌手被称为rushing adversary)。具体而言,令 \(P_j\) 是一个诚实方,其输入为 \(q_j(x)\),令 \(P_i\) 是一个被攻陷方。在实际执行中,敌手可以首先看到 \(P_i\) 的份额 \(q_j(\alpha_i)\),然后选择输入多项式 \(q_i(x)\),满足 \(q_i(\alpha_i) = q_j(\alpha_i)\). 但是在理想世界中,敌手无法这么做,因为 \(\mathcal{F}_{\mathsf{VSS}}^n\) 的定义使被攻陷方在提供输入多项式之前无法得到关于诚实方多项式的任何信息。
因此,并行地调用 \(n\) 次 \(\mathcal{F}_{\mathsf{VSS}}\) 无法安全实现 \(\mathcal{F}_{\mathsf{VSS}}^n\)(因为在真实世界中存在某种攻击方式,在理想世界中无法实现),我们需要修改协议或理想功能的定义(或两者都修改)。让我们再次审视敌手的攻击方式,可以发现,这种攻击实际上并不会造成协议的不安全,因为秘密份额 \(q_j(\alpha_i)\) 与常数项 \(q_j(0)\) 是相互独立的,敌手让 \(q_i(\alpha_i)\) 依赖于 \(q_j(\alpha_i)\) 并不会对整个协议造成实际影响。因此,我们可以让协议保持不变(仍为并行调用 \(n\) 次 \(\mathcal{F}_{\mathsf{VSS}}\)),而是将理想功能修改如下:令 \(I\) 是被攻陷方的集合。首先,诚实方发送输入多项式 \(q_j(x), \; j \notin I\);然后,模拟器(理想敌手)收到诚实方向被攻陷方发送的秘密份额 \(q_j(\alpha_i), \; j \notin I, \; i \in I\);最后,被攻陷方向理想功能发送他们的输入多项式 \(q_i(x), \; i \in I\). 这样一来,修改后的理想功能就刻画了敌手(rushing adversary)可以基于 \(q_j(\alpha_i)\) 来选择输入多项式的能力。形式化地,并行VSS理想功能 \(\mathcal{F}_{\mathsf{VSS}}^n\) 定义如图 9.19所示。
实现矩阵乘法理想功能 \(\mathcal{F}_{\mathsf{mat}}^{\boldsymbol A}\)
接下来,我们首先实现一个较简单的理想功能——矩阵乘法,它将输入向量 \(\boldsymbol{x}\) 映射到 \(\boldsymbol{x} \cdot \boldsymbol{A}\),其中 \(\boldsymbol{A}\) 是一个公开的固定矩阵,第 \(i\) 个参与方 \(P_i\) 持有 \(x_i\),所有参与方都以 \(\boldsymbol{x} \cdot \boldsymbol{A}\) 作为输出。之后,我们会把它作为实现理想功能 \(\mathcal{F}_{\mathsf{VSS}}^\mathsf{subshare}\) 的子协议。
让我们首先讨论一下 \(\mathcal{F}_{\mathsf{mat}}^{\boldsymbol A}\) 的定义。\(\mathcal{F}_{\mathsf{mat}}^{\boldsymbol A}\) 使得参与方安全地计算长度为 \(m\) 的向量 \((y_1, …, y_m) = (x_1, …, x_n) \cdot \boldsymbol{A}\),其中 \(x_1, …, x_n \in \mathbb{F}\) 是各参与方的输入,\(\boldsymbol{A} \in \mathbb{F}^{n \times m}\). (这里 \(m = 1\) 的情况也是有意义的,但在协议中我们需要取 \(m = 2t\).)注意到,矩阵乘法是线性运算(仅包括加法和常数乘法),我们可以沿用半诚实场景下的思路:参与方首先(可验证地)秘密分享各自的输入,然后每个参与方在本地对秘密份额进行线性运算,最后,公布计算后的份额来进行输出重建。与半诚实的协议相比,仅有的不同之处在于——输入分享时使用了可验证秘密分享,以及输出重建时使用了Reed-Solomon解码。因此,矩阵乘法理想功能可以通过以下方式安全地计算:
输入分享阶段:每个参与方 \(P_i\) 选择随机多项式 \(g_i(x)\),满足条件 \(g_i(0) = x_i\). 然后,\(P_i\) 调用理想功能 \(\mathcal{F}_{\mathsf{VSS}}\) 秘密分享 \(g_i(x)\). 多项式分享结束后,参与方 \(P_i\) 持有份额 \(g_1(\alpha_i), …, g_n(\alpha_i)\).
计算阶段:参与方 \(P_i\) 计算输出向量的秘密份额 \(\boldsymbol{y}^i = (g_1(\alpha_i), \dots, g_n(\alpha_i)) \cdot {\boldsymbol A}\). 注意到:
\[\boldsymbol{y}^i = (g_1(\alpha_i), \dots, g_n(\alpha_i)) \cdot {\boldsymbol A} = \begin{bmatrix} g_1(\alpha_i), \dots, g_n(\alpha_i) \end{bmatrix} \cdot \begin{bmatrix} a_{1,1} & \dots & a_{1, m} \\ a_{2,1} & \dots & a_{2, m} \\ \vdots & & \vdots \\ a_{n,1} & \dots & a_{n, m} \\ \end{bmatrix}\]因此 \(\boldsymbol{y}^i\) 的第 \(j\) 个元素为 \(\sum_{\ell=1}^n g_\ell(\alpha_i) \cdot a_{\ell, j}\). 将 \(\boldsymbol{y}^i\) 的第 \(j\) 个元素记为 \(y_j^i\),那么 \(y_j^1, \dots, y_j^n\) 是 \(\boldsymbol{y} = (g_1(0), \dots, g_n(0)) \cdot {\boldsymbol A}\) 的第 \(j\) 个元素的Shamir秘密份额。- 输出重建阶段:
每个参与方 \(P_i\) 将 \(\boldsymbol{y}^i\) 发给其他参与方。
每个参与方 \(P_i\) 根据收到的秘密份额,运行Reed-Solomon解码算法重建输出 \(\boldsymbol{y} = (g_1(0), \dots, g_n(0)) \cdot {\boldsymbol A}\). 注意到,参与方的秘密份额构成如下的矩阵:
\[\begin{bmatrix} \leftarrow \boldsymbol{y}^1 \rightarrow \\ \leftarrow \boldsymbol{y}^2 \rightarrow \\ \vdots \\ \leftarrow \boldsymbol{y}^n \rightarrow \\ \end{bmatrix} = \begin{bmatrix} \sum_{\ell=1}^n g_\ell(\alpha_1) \cdot a_{\ell, 1} & \dots & \sum_{\ell=1}^n g_\ell(\alpha_1) \cdot a_{\ell, m} \\ \sum_{\ell=1}^n g_\ell(\alpha_2) \cdot a_{\ell, 1} & \dots & \sum_{\ell=1}^n g_\ell(\alpha_2) \cdot a_{\ell, m} \\ \vdots & & \vdots \\ \sum_{\ell=1}^n g_\ell(\alpha_n) \cdot a_{\ell, 1} & \dots & \sum_{\ell=1}^n g_\ell(\alpha_n) \cdot a_{\ell, m} \\ \end{bmatrix}\]矩阵的第 \(j\) 列构成 \(\sum_{\ell=1}^n g_\ell(0) \cdot a_{\ell, j}\) 的Shamir秘密份额,而 \(\sum_{\ell=1}^n g_\ell(0) \cdot a_{\ell, j}\) 就是输出向量的第 \(j\) 个元素。参与方对矩阵的每一列运行Reed-Solomon解码算法得到正确的输出。
直观上看,上述协议满足对于恶意敌手的安全性:\(\mathcal{F}_{\mathsf{VSS}}\) 确保被攻陷方的输入是良好定义的,而Reed-Solomon解码使得被攻陷方无法影响协议输出。然而,正如前面所提到的,我们要将 \(\mathcal{F}_{\mathsf{mat}}^{\boldsymbol A}\) 作为实现 \(\mathcal{F}_{\mathsf{VSS}}^\mathsf{subshare}\) 的子协议,因此 \(\mathcal{F}_{\mathsf{mat}}^{\boldsymbol A}\) 的定义需要更复杂些:首先,每个参与方的输入不是 \(x_i\),而是 \(t\) 阶多项式 \(g_i(x)\) 满足 \(g_i(0) = x_i\)(这是由于 \(\mathcal{F}_{\mathsf{VSS}}^\mathsf{subshare}\) 的需要);其次,参与方的输出不仅仅是 \(\boldsymbol{y} = (g_1(0), …, g_n(0)) \cdot {\boldsymbol A}\),除此之外 \(P_i\) 还需要输出收到的秘密份额 \(g_1(\alpha_i), …, g_n(\alpha_i)\). 于是,理想功能 \(\mathcal{F}_{\mathsf{mat}}^{\boldsymbol A}\) 定义如下:
其中 \(\boldsymbol{y} = (g_1(0), …, g_n(0)) \cdot {\boldsymbol A}\). 尽管只是作了很小的改动,但这使得协议和理想功能的定义需要变得更复杂。
下面,我们分析一下为什么上述改动会造成影响。上文的矩阵乘法协议中,在输出重建阶段,参与方 \(P_i\) 要发送输出向量的秘密份额 \(\boldsymbol{y}^i\). 注意到,向量 \(\boldsymbol{y}^1, …, \boldsymbol{y}^n\) 是完全由输入多项式 \(g_1(x), …, g_n(x)\) 所决定的。但是,在理想世界中,模拟器只能获得(被攻陷方的)部分秘密份额/输入多项式,因此不能模拟 \(\boldsymbol{y}^1, …, \boldsymbol{y}^n\). 具体而言,假设只有 \(P_1\) 是被攻陷方。此时,模拟器可以知道 \(P_1\) 的输出 \(\boldsymbol{y} = (g_1(0), …, g_n(0)) \cdot {\boldsymbol A}\) 和 \(g_1(\alpha_1), …, g_n(\alpha_1)\) 以及 \(P_1\) 的输入多项式 \(g_1(x)\),但不知道诚实方的输入多项式。然而,在真实执行中,敌手可以看到诚实方发送的所有向量 \(\boldsymbol{y}^2, …, \boldsymbol{y}^n\),它们是基于 \(g_1(x), …, g_n(x)\) 和矩阵 \({\boldsymbol A}\) 的一个确定性函数,因此理想世界的模拟器必须模拟诚实方发送完全一致的消息,但基于模拟器拥有的信息,这不可能做到!
让我们审视一下这里遇到的问题:真实协议中的 \(\boldsymbol{y}^1, …, \boldsymbol{y}^n\) 泄露了输入多项式的一些信息,但理想功能并没有这样的泄露。然而,\(\mathcal{F}_{\mathsf{mat}}^{\boldsymbol A}\) 的目的是安全地实现 \(\mathcal{F}_{\mathsf{VSS}}^\mathsf{subshare}\)(见「实现子份额秘密分享理想功能 F_VSS^subshare」一节的图 9.22),敌手知道 \(\boldsymbol{y}^1, …, \boldsymbol{y}^n\) 对协议的安全性并没有什么影响。实际上,我们甚至可以允许敌手知道向量 \(\boldsymbol{Y}(x) = (Y_1(x), …, Y_m(x)) = (g_1(x), …, g_n(x)) \cdot {\boldsymbol A}\). 因此,我们采取与定义 \(\mathcal{F}_{\mathsf{VSS}}^n\) 时同样的方式:修改理想功能,允许 \(\mathcal{F}_{\mathsf{mat}}^{\boldsymbol A}\) 泄漏 \(\boldsymbol{Y}(x)\) 给敌手。于是,矩阵乘法理想功能 \(\mathcal{F}_{\mathsf{mat}}^{\boldsymbol A}\) 定义如图 9.20所示。注意,由于 \(\mathcal{F}_{\mathsf{mat}}^{\boldsymbol A}\) 让 \(P_i\) 输出了秘密份额 \(\{g_\ell(\alpha_i)\}_{\ell=1}^n\),与上一节相同,我们考虑rushing adversary,允许敌手基于收到的秘密份额选择输入多项式。
经过修改,上文中的协议就可以安全地实现理想功能 \(\mathcal{F}_{\mathsf{mat}}^{\boldsymbol A}\) 了。我们给出协议在 \(\mathcal{F}_{\mathsf{VSS}}^n\)-混合模型下的形式化描述,如图 9.21所示。
\(P_i\) 收到的向量构成的矩阵,对每一列执行Reed-Solomon解码
实现子份额秘密分享理想功能 \(\mathcal{F}_{\mathsf{VSS}}^\mathsf{subshare}\)
在半诚实场景下,这很容易做到:每个参与方 \(P_i\) 选择常数项为 \(f(\alpha_i)\) 的随机多项式 \(g_i(x)\),然后向 \(P_j\) 发送 \(g_i(\alpha_j)\). 但是,在恶意敌手场景下,主要的难点在于:如何强制被攻陷方 \(P_i\) 分享正确的 \(f(\alpha_i)\) 而不是其他值。注意,此时有超过 \(t\) 个诚实方,它们的秘密份额唯一确定了 \(f(x)\),因此可以令 \(f(x)\) 为诚实方的秘密份额所确定的 \(t\) 阶多项式,它是良好定义的。我们要确保被攻陷方 \(P_i\) 在分发子份额时使用了常数项为 \(f(\alpha_i)\) 的 \(t\) 阶多项式。
我们先给出 \(\mathcal{F}_{\mathsf{VSS}}^\mathsf{subshare}\) 的定义。当某个被攻陷方 \(P_i\) 向 \(\mathcal{F}_{\mathsf{VSS}}^\mathsf{subshare}\) 提供了不合法的输入时(\(g_i(x)\) 超过 \(t\) 阶或 \(g_i(0) \neq f(\alpha_i)\)),\(\mathcal{F}_{\mathsf{VSS}}^\mathsf{subshare}\) 将其替换为常数多项式 \(g'_i(x) = f(\alpha_i)\). 这确保了 \(P_i\) 的输入多项式的常数项总是 \(f(\alpha_i)\). 另外,由于我们在实现 \(\mathcal{F}_{\mathsf{VSS}}^\mathsf{subshare}\) 的协议中调用了理想功能 \(\mathcal{F}_{\mathsf{mat}}^{\boldsymbol A}\) 来乘以Reed-Solomon码校验矩阵(parity-check matrix) \({\boldsymbol H}\)(的转置),因此 \(\mathcal{F}_{\mathsf{VSS}}^\mathsf{subshare}\) 需要向模拟器 \(\mathcal{S}\) 泄漏 \(\boldsymbol{Y}(x) = (g_1(x), …, g_n(x)) \cdot {\boldsymbol H}^\mathrm{T}\) 使其能够模拟 \(\mathcal{F}_{\mathsf{mat}}^{\boldsymbol A}\). 最后,与前面相同,我们考虑rushing adversary,允许敌手基于诚实方向被攻陷方发送的秘密份额来选择输入多项式。\(\mathcal{F}_{\mathsf{VSS}}^\mathsf{subshare}\) 的定义如图 9.22所示。
令 \(f(x) = \sum_{\ell=0}^t a_\ell \cdot x^\ell\) 是一个 \(t\) 阶多项式,对向量 \(\boldsymbol{a} = (a_0, …, a_t) \in \mathbb{F}^{t + 1}\) 的Reed-Solomon编码即为向量 \(\langle f(\alpha_1), …, f(\alpha_n) \rangle\). 令 \({\boldsymbol H} \in \mathbb{F}^{2t \times n}\) 是 \(G\) 的校验矩阵,即 \({\boldsymbol H}\) 的秩(rank)为 \(2t\),满足 \(G \times {\boldsymbol H}^\mathrm{T} = 0^{(t+1) \times 2t}\). 注意,\({\boldsymbol H}\) 完全由 \(\alpha_1, …, \alpha_n\) 所决定,因此是一个公开的常量矩阵。码字 \(\boldsymbol{\beta} \in \mathbb{F}^n\) 的伴随式(syndrome)为 \(S(\boldsymbol{\beta}) = \boldsymbol{\beta} \cdot {\boldsymbol H}^\mathrm{T} \in \mathbb{F}^{2t}\). 对于一个正确的码字 \(\boldsymbol{\beta} = \boldsymbol{a} \cdot G\),一定有 \(S(\boldsymbol{\beta}) = 0^{2t}\);对于任意错误向量 \(\boldsymbol{e} \in \mathbb{F}^n\),有 \(S(\boldsymbol{\beta} + \boldsymbol{e}) = S(\boldsymbol{e})\). 如果 \(\boldsymbol{e}\) 与 \(0^{n}\) 的距离不超过 \(t\),那么我们可以对 \(\boldsymbol{\beta} + \boldsymbol{e}\) 进行纠错得到原始向量 \(\boldsymbol{\beta}\). 在Reed-Solomon解码算法中,存在一个子程序可以从伴随式 \(S(\boldsymbol{e})\) 中提取 \(\boldsymbol{e}\). 也就是说,给定一个可能损坏的码字 \(\boldsymbol{\gamma} = \boldsymbol{\beta} + \boldsymbol{e}\),首先计算其伴随式 \(S(\boldsymbol{\gamma}) = \boldsymbol{\gamma} \cdot {\boldsymbol H}^\mathrm{T} = S(\boldsymbol{e})\),然后将 \(S(\boldsymbol{e})\) 输入子程序提取 \(\boldsymbol{e}\). 最后,根据 \(\boldsymbol{e}\) 和 \(\boldsymbol{\gamma}\) 可以提取原始向量 \(\boldsymbol{\beta} = \boldsymbol{\gamma} - \boldsymbol{e}\).
协议构造。协议中,每个参与方 \(P_i\) 选择随机多项式 \(g_i(x)\),其常数项为协议输入值(秘密份额) \(\beta_i\). 令 \(\boldsymbol{\beta} = (\beta_1, …, \beta_n)\). 因为这些输入值位于某个多项式 \(f(x)\) 上,所以对于所有诚实方 \(P_j\) 都有 \(g_j(0) = \beta_j = f(\alpha_j)\). 但是对于被攻陷方 \(P_i\),他的多项式的常数项 \(g_i(0)\) 没有任何保证。令 \(\boldsymbol{\gamma} = (g_1(0), …, g_n(0))\),那么 \(\boldsymbol{\gamma}\) 与 \(\boldsymbol{\beta} = (\beta_1, …, \beta_n)\) 的距离最多为 \(t\). 而 \(\boldsymbol{\beta}\) 的长度为 \(n = 3t + 1\),因此可以通过Reed-Solomon纠错算法来给 \(\boldsymbol{\gamma}\) 纠错。参与方首先将多项式 \((g_1(x), …, g_n(x))\) 发给 \(\mathcal{F}_{\mathsf{mat}}^{\boldsymbol H}\)(它是图 9.20定义的理想功能,将参数矩阵换为校验矩阵 \({\boldsymbol H}\) 的转置),然后每个参与方 \(P_i\) 得到输出 \((g_1(\alpha_i), …, g_n(\alpha_i))\) 和 \((s_1, …, s_{2t}) = \boldsymbol{\gamma} \cdot {\boldsymbol H}^\mathrm{T}\). 这里 \((s_1, …, s_{2t}) = \boldsymbol{\gamma} \cdot {\boldsymbol H}^\mathrm{T}\) 就是 \(\boldsymbol{\gamma}\) 的伴随式 \(S(\boldsymbol{\gamma})\). 每个参与方基于该伴随式提取错误向量 \(\boldsymbol{e} = (e_1, …, e_n) = \boldsymbol{\gamma} - \boldsymbol{\beta}\). 注意,\(\boldsymbol{e}\) 满足 \(g_i(0) - e_i = f(\alpha_i)\) 对 \(i \in [n]\) 都成立,且 \(\boldsymbol{e}\) 可以由参与方在本地基于 \(S(\boldsymbol{\gamma})\) 提取出来。于是,错误向量 \(\boldsymbol{e}\) 为诚实方提供了计算输出所需要的信息。具体而言,如果 \(e_i = 0\),那么 \(P_i\) 使用了正确的多项式 \(g_i(x)\),参与方可以直接输出 \(\mathcal{F}_{\mathsf{mat}}^{\boldsymbol H}\) 的输出 \(g_i(\alpha_j)\);如果 \(e_i \neq 0\),那么参与方就知道 \(P_i\) 是被攻陷的,他们互相发送 \(P_i\) 的秘密份额 \(g_i(\alpha_j)\),重建 \(g_i(x)\)(通过Reed-Solomon解码),然后计算 \(g_i(0) - e_i = f(\alpha_i)\). 最后,参与方设置 \(g'_i(x) = f(\alpha_i)\),与理想功能 \(\mathcal{F}_{\mathsf{VSS}}^\mathsf{subshare}\) 相一致。完整的协议如图 9.23所示。
在进行安全性证明时,有一点需要注意:协议中泄漏了伴随式 \(\boldsymbol{\gamma} \cdot {\boldsymbol H}^\mathrm{T}\),模拟器 \(\mathcal{S}\) 需要在理想世界中模拟该消息。不过,\(\mathcal{F}_{\mathsf{VSS}}^\mathsf{subshare}\) 向模拟器 \(\mathcal{S}\) 泄漏了 \(\boldsymbol{Y}(x) = (g_1(x), …, g_n(x)) \cdot {\boldsymbol H}^\mathrm{T}\),而伴随式就等于 \(\boldsymbol{Y}(0)\),因此 \(\mathcal{S}\) 可以模拟该条消息。
实现多项式求值理想功能 \(\mathcal{F}_{\mathsf{eval}}\)
在「实现乘积子份额秘密分享理想功能 F_VSS^mult」一节的协议(实现 \(\mathcal{F}_{\mathsf{VSS}}^\mathsf{mult}\))中,参与方需要解决“投诉”(complaint)(因为被攻陷方可能提供错误的值)。解决这些投诉的方式是:计算多项式在投诉方的点处的值。具体而言,给定多项式 \(f(x)\) 的份额 \(f(\alpha_1), …, f(\alpha_n)\),参与方需要计算 \(f(\alpha_k)\),其中 \(k\) 是一个公开值,且不泄漏任何其他信息。
我们首先定义理想功能 \(\mathcal{F}_{\mathsf{eval}}^k\). 它的参数是索引 \(k\),\(k\) 指定了需要求多项式在哪个点处的值。\(\mathcal{F}_{\mathsf{eval}}^k\) 的形式化定义如图 9.24所示。在该定义中,\(\mathcal{F}_{\mathsf{eval}}^k\) 只接收了诚实方的输入,忽略了被攻陷方的输入。我们也可以让 \(\mathcal{F}_{\mathsf{eval}}^k\) 接收所有参与方的输入,然后运行Reed-Solomon解码算法。但实际上敌手的输入不会对输出有任何影响,因此我们采用这种更简洁的定义方式。
其中 \(f\) 是对 \((\beta_1, …, \beta_n)\) 进行Reed-Solomon解码的输出。注意,虽然 \(f(\alpha_i)\) 已经是 \(P_i\) 的输入了,但为了让模拟器可以进行模拟,我们还是需要将其作为输出的一部分(这只是为了安全性证明的需要,对实际协议不会有任何影响)。
Reed-Solomon编码背景知识。下面我们说明:\(f(\alpha_k)\) 是输入秘密份额 \((\beta_1, …, \beta_n)\) 的线性组合(注:这里的秘密份额 \((\beta_1, …, \beta_n)\) 是经过纠错的正确的秘密份额。)。定义参与方的输入向量为 \(\boldsymbol{\beta} = (\beta_1, …, \beta_n)\). 对于 \(j \notin I\),有 \(\beta_j = f(\alpha_j)\),因此,参与方的输入由下式计算
故存在常量向量 \(\boldsymbol{\alpha}_{k} \cdot V_{\boldsymbol{\alpha}}^{-1}\),它与输入向量 \(\boldsymbol{\beta}\) 的内积就是要计算的输出。也就是说,\(\mathcal{F}_{\mathsf{eval}}^k\) 只需对参与方的输入做线性运算。
协议构造。由于 \(\mathcal{F}_{\mathsf{eval}}^k\) 是对参与方的输入进行线性运算,我们似乎可以采用与 \(\mathcal{F}_{\mathsf{mat}}^{\boldsymbol A}\) 同样的方法。但是,请注意,\(\mathcal{F}_{\mathsf{mat}}^{\boldsymbol A}\) 允许被攻陷方输入任何值,而 \(\mathcal{F}_{\mathsf{eval}}^k\) 需要保证被攻陷方的输入是正确的秘密份额(即所有秘密份额位于相同的 \(t\) 阶多项式上)。幸运的是,我们可以调用理想功能 \(\mathcal{F}_{\mathsf{VSS}}^\mathsf{subshare}\) 来解决该问题——\(\mathcal{F}_{\mathsf{VSS}}^\mathsf{subshare}\) 保证了输入分享阶段中参与方正确地分发了秘密份额的子份额;协议的计算阶段与输出重建阶段与协议 \(\Pi_\mathsf{mat}^{\boldsymbol A}\) 完全一致。完整的协议如图 9.25所示。
直观上看,该协议是安全的,参与方调用 \(\mathcal{F}_{\mathsf{VSS}}^\mathsf{subshare}\) 获得了输入的子份额,而这些子份额不会泄露输入份额的任何信息。不过,在构造模拟器 \(\mathcal{S}\) 时,有一些细节需要考虑:\(\mathcal{F}_{\mathsf{VSS}}^\mathsf{subshare}\) 除了向 \(P_i\) 发送输出值 \(g'_1(\alpha_i), …, g'_n(\alpha_i)\),还向敌手泄露了向量 \(\boldsymbol{Y}(x) = (g_1(x), …, g_n(x)) \cdot {\boldsymbol H}^\mathrm{T}\),其中 \({\boldsymbol H}\) 是Reed-Solomon编码的校验矩阵,\(g_i(x)\) 是 \(P_i\) 的输入多项式(被攻陷方 \(P_i\) 的多项式 \(g_i(x)\) 如果常数项不正确,则 \(g_i(x) \neq g'_i(x)\);对于诚实方 \(P_j\) 都有 \(g_j(x) = g'_j(x)\))。模拟器需要模拟 \(\boldsymbol{Y}(x)\). 注意,\(\boldsymbol{Y}(0) = (g_1(0), …, g_n(0)) \cdot {\boldsymbol H}^\mathrm{T}\) 为输入值的伴随式。可以模拟的原因是伴随式仅依赖于错误向量 \(\boldsymbol{e}\). 下面展开说明。令 \(\boldsymbol{\gamma} = (\gamma_1, …, \gamma_n)\) 是参与方的输入向量(对于 \(i \in I\) 可能有 \(\gamma_i \neq f(\alpha_i)\))。令“正确的”输入向量为 \(\boldsymbol{\beta} = (f(\alpha_1), …, f(\alpha_n))\). 向量 \(\boldsymbol{\gamma}\) 决定了错误向量 \(\boldsymbol{e}\),\(\boldsymbol{e}\) 满足 \(\boldsymbol{\gamma} - \boldsymbol{e} = (f(\alpha_1), …, f(\alpha_n)) = \boldsymbol{\beta}\),且 \(\boldsymbol{e}\) 的汉明重量最多为 \(t\). 伴随式函数 \(S(\boldsymbol{x}) = \boldsymbol{x} \cdot {\boldsymbol H}^\mathrm{T}\) 满足 \(S(\boldsymbol{\gamma}) = S(\boldsymbol{\beta} + \boldsymbol{e}) = S(\boldsymbol{e})\),即 \((\gamma_1, …, \gamma_n) \cdot {\boldsymbol H}^\mathrm{T} = \boldsymbol{e} \cdot {\boldsymbol H}^\mathrm{T}\),而模拟器可以自己计算 \(\boldsymbol{e}\)(模拟器从 \(\mathcal{F}_{\mathsf{eval}}^k\) 的输出中得到被攻陷方的 \(f(\alpha_i), \; i \in I\),通过模拟 \(\mathcal{F}_{\mathsf{VSS}}^\mathsf{subshare}\) 获得被攻陷方的输入多项式 \(\{g_i(x)\}_{i \in I}\),而 \(e_i = g_i(0) - f(\alpha_i)\);对于 \(j \notin I\),都有 \(e_j = 0\))。故模拟器可以计算 \(\boldsymbol{e} \cdot {\boldsymbol H}^\mathrm{T} = \boldsymbol{\gamma} \cdot {\boldsymbol H}^\mathrm{T} = (g_1(0), …, g_n(0)) \cdot {\boldsymbol H}^\mathrm{T} = \boldsymbol{Y}(0)\).
上面我们说明了模拟器可以计算 \(\boldsymbol{Y}(0)\). 除此之外,对于 \(i \in I\),模拟器知道 \(g_1(\alpha_i), …, g_n(\alpha_i)\),它可以计算 \(\boldsymbol{Y}(\alpha_i) = (g_1(\alpha_i), …, g_n(\alpha_i)) \cdot {\boldsymbol H}^\mathrm{T}\). 我们将证明:\(\boldsymbol{Y}(x)\) 是在 \(\boldsymbol{Y}(0)\) 和 \(\{\boldsymbol{Y}(\alpha_i)\}_{i \in I}\) 的约束条件下的均匀随机 \(t\) 阶多项式向量(当 \(| I | = t\) 时有 \(t + 1\) 个约束条件,此时 \(\boldsymbol{Y}(x)\) 是确定的);对于 \(Q(x)\) 而言也是如此:\(Q(x)\) 是在 \(Q(0)\) 和 \(Q(\alpha_i) = \sum_{\ell=1}^n \lambda_\ell \cdot g'_\ell(\alpha_i), \; i \in I\) 的约束条件下的均匀随机多项式(当 \(| I | = t\) 时 \(Q(x)\) 是确定的)。故模拟器可以模拟协议中所有消息。
我们有以下定理。
实现乘积子份额秘密分享理想功能 \(\mathcal{F}_{\mathsf{VSS}}^\mathsf{mult}\)
理想功能 \(\mathcal{F}_{\mathsf{VSS}}^\mathsf{mult}\) 允许秘密分发者在已经分享了 \(t\) 阶多项式 \(A(x)\) 和 \(B(x)\) 的情况下,可验证地分享随机 \(t\) 阶多项式 \(C(x)\),满足 \(C(0) = A(0) \cdot B(0)\). 这是协议中关键的一步(参见「直观思想」一节的乘法协议概览)。\(\mathcal{F}_{\mathsf{VSS}}^\mathsf{mult}\) 的定义如图 9.26所示。
尽管秘密分发者 \(P_1\) 本来就应该知道 \(A(x), B(x)\),参与方 \(P_i\) 本来就应该知道 \(A(\alpha_i), B(\alpha_i)\),在上述定义中 \(\mathcal{F}_{\mathsf{VSS}}^\mathsf{mult}\) 还是将这些信息提供给了敌手 \(\mathcal{S}\),这是因为 \(\mathcal{S}\) 需要知道被攻陷方正确的份额才能够进行模拟。在整个乘法协议中,敌手原本就知道这些信息,因此 \(\mathcal{F}_{\mathsf{VSS}}^\mathsf{mult}\) 再次发送它们不会造成额外的信息泄露。
请读者注意,\(\mathcal{F}_{\mathsf{VSS}}^\mathsf{mult}\) 适用于参与方已经拥有(导线值的)秘密份额 \(a\) 和 \(b\) 时,通过 \(t\) 阶多项式 \(C(x)\)(满足 \(C(0) = a \cdot b\))可验证地分发 \(a \cdot b\) 的子份额。这里的 \(a\) 和 \(b\) 不是导线上的值,而是导线值的秘密份额。
协议思想。令 \(A(x)\) 和 \(B(x)\) 是用于分享 \(a\) 和 \(b\) 的多项式,满足 \(A(0) = a, B(0) = b\). 协议的思想是:秘密分发者首先选择 \(t\) 个多项式 \(D_1(x), …, D_t(x)\),它们均为 \(t\) 阶,使得 \(C(x) = A(x) \cdot B(x) - \sum_{\ell=1}^t x^\ell \cdot D_\ell(x)\) 是常数项为 \(a \cdot b\) 的随机 \(t\) 阶多项式。注意,\(A(x)\) 和 \(B(x)\) 均为 \(t\) 阶,故 \(A(x) \cdot B(x)\) 的阶数为 \(2t\),秘密分发者选择的 \(D_1(x), …, D_t(x)\) 需要使 \(A(x) \cdot B(x)\) 高于 \(t\) 阶的项全部被抵消,这样 \(C(x)\) 的阶数才能为 \(t\). 然后,秘密分发者分享多项式 \(D_1(x), …, D_t(x)\),每个参与方在本地计算 \(C(x)\) 的秘密份额。注意到,每一个 \(D_\ell(x)\) 都乘以了 \(x^\ell\),因此无论 \(D_1(x), …, D_t(x)\) 如何选择,\(C(x)\) 的常数项始终等于 \(A(0) \cdot B(0) = a \cdot b\). 也就是说,即使恶意的秘密分发者错误地选择 \(D_1(x), …, D_t(x)\),也不会影响 \(C(x)\) 的常数项,但 \(C(x)\) 的阶数可能超过 \(t\).
更具体地,在确定 \(D_1(x), …, D_t(x)\) 后,秘密分发者调用 \(\mathcal{F}_{\mathsf{VSS}}\) 分享这些多项式,\(\mathcal{F}_{\mathsf{VSS}}\) 保证了多项式的阶数为 \(t\) 且参与方持有正确的份额。而参与方本来就持有 \(A(x)\) 和 \(B(x)\) 的份额。给定 \(A(\alpha_j), B(\alpha_j)\) 以及 \(D_1(\alpha_j), …, D_t(\alpha_j)\),\(P_j\) 可以本地计算 \(C(\alpha_j) = A(\alpha_j) \cdot B(\alpha_j) - \sum_{\ell=1}^t (\alpha_j)^\ell \cdot D_\ell(\alpha_j)\). 此时,如果秘密分发者是诚实的,那么参与方的秘密份额位于常数项为 \(a \cdot b\) 的 \(t\) 阶多项式上;如果秘密分发者是被攻陷的,那么这些秘密份额仍然位于常数项为 \(a \cdot b\) 的多项式上(但阶数不能保证)。因此,只需要再设计一种方法使参与方验证 \(C(x)\) 确实是 \(t\) 阶多项式即可。
一个直接的想法是:让秘密分发者再调用 \(\mathcal{F}_{\mathsf{VSS}}\) 分享 \(C(x)\),然后参与方验证自己收到的份额与基于 \(A(\alpha_j), B(\alpha_j), D_1(\alpha_j), …, D_t(\alpha_j)\) 计算得到的 \(C(\alpha_j)\) 相等。具体而言,将 \(P_j\) 从 \(\mathcal{F}_{\mathsf{VSS}}\) 收到的份额记为 \(C'(\alpha_j)\),将计算 \(A(\alpha_j) \cdot B(\alpha_j) - \sum_{\ell=1}^t (\alpha_j)^\ell \cdot D_\ell(\alpha_j)\) 所得的值记为 \(C(\alpha_j)\). 如果 \(C(\alpha_j) \neq C'(\alpha_j)\),那么参与方就像VSS协议中(图 9.9)那样广播“投诉”。如果有超过 \(t\) 个参与方投诉,那么秘密分发者就是被攻陷的,所有参与方广播自己的份额以重建 \(A(x)\) 和 \(B(x)\),并输出 \(A(0) \cdot B(0)\). 但是,需要注意的是,\(C(x)\) 可以是阶数为 \(2t\) 的多项式,它与另一个 \(t\) 阶多项式 \(C'(x)\) 最多可以相交于 \(2t\) 个点。因此,恶意的秘密分发者可以通过 \(\mathcal{F}_{\mathsf{VSS}}\) 分享 \(t\) 阶多项式 \(C'(x)\),其中 \(C'(x)\) 与 \(C(x)\) 在 \(2t\) 个位置 \(\alpha_j\) 处的值相等,且 \(C'(0) \neq a \cdot b\). 由于诚实方的数量至少为 \(2t + 1\),此时,我们只能保证至少有1个诚实方会广播投诉,但投诉的数量不足以让参与方确定秘密分发者是被攻陷的并重建其份额。
这个问题的解决方法是:参与方要明确地解决每一个投诉,验证其是否为合法的。只要有一个合法的投诉,参与方就重建 \(a\) 和 \(b\) 并输出 \(a \cdot b\);如果投诉的不合法的,那么忽略它。这保证了如果没有诚实方提出合法的投诉,那么秘密分发者通过 \(\mathcal{F}_{\mathsf{VSS}}\) 分享的 \(t\) 阶多项式 \(C'(x)\) 与 \(C(x)\) 在至少 \(2t + 1\) 个点处的值一致,而 \(C(x)\) 的阶数最多为 \(2t\),所以一定满足 \(C(x) = C'(x)\),即 \(C(x)\) 的阶数为 \(t\).
这里,我们需要调用「实现多项式求值理想功能 F_eval」一节实现的理想功能 \(\mathcal{F}_{\mathsf{eval}}^k\) 来明确地解决投诉。当 \(P_k\) 提出投诉时,参与方调用 \(\mathcal{F}_{\mathsf{eval}}^k\) 来计算 \(A(\alpha_k), B(\alpha_k), D_1(\alpha_k), …, D_t(\alpha_k)\) 以及 \(C'(\alpha_k)\),然后检查 \(C'(\alpha_k) \stackrel{?}{=} A(\alpha_k) \cdot B(\alpha_k) - \sum_{\ell=1}^t (\alpha_k)^\ell \cdot D_\ell(\alpha_k)\). 如果等式不成立,那么秘密分发者就是被攻陷的,参与方重建 \(a \cdot b\) 并输出。上述方法可以明确地验证每个投诉是否为合法的。注意,参与方一定持有 \(C'(x), D_1(x), …, D_t(x)\) 的正确份额,因为它们是通过 \(\mathcal{F}_{\mathsf{VSS}}\) 分享的,而根据输入的假设,参与方持有的 \(A(x)\) 和 \(B(x)\) 的份额也是正确的,因此可以调用 \(\mathcal{F}_{\mathsf{eval}}^k\) 进行计算。
在秘密分发者是诚实的情况下,参与方不可能提出合法的投诉。此时,如果被攻陷方提出错误的投诉,投诉解决的过程只会公布(被攻陷的)投诉者自己的秘密份额,因而不会让敌手获得任何额外信息。
构造多项式 \(C(x)\). 上文中说到,秘密分发者需要选择特殊构造的 \(t\) 个 \(t\) 阶多项式 \(D_1(x), …, D_t(x)\) 使得 \(C(x) = A(x) \cdot B(x) - \sum_{\ell=1}^t x^\ell \cdot D_\ell(x)\) 是常数项为 \(a \cdot b\) 的随机 \(t\) 阶多项式,其中 \(a = A(0), b = B(0)\). 下面我们介绍选择这些多项式的方式。首先,定义多项式 \(D(x)\) 如下:
我们来分析一下多项式 \(\sum_{\ell=1}^t x^\ell \cdot D_\ell(x)\). 首先,它的阶数为 \(2t\),常数项为0. 我们将它的系数画成一张表,如表 9.1所示。
| \(D_{t-1}\) | \(…\) | \(r_{t-1, 1}\) | \(r_{t-1, 2}\) | \(r_{t-1, 3}\) | \(…\) | \(r_{t-1, t-1}\) | \(R_{t-1, t}\) | ||||
| \(D_{t-2}\) | \(…\) | \(r_{t-2, 2}\) | \(r_{t-2, 3}\) | \(r_{t-2, 4}\) | \(…\) | \(R_{t-2, t}\) | |||||
| \(\vdots\) | \(\iddots\) | \(\vdots\) | \(\vdots\) | \(\vdots\) | \(\iddots\) | ||||||
| \(D_3\) | \(r_{3,0}\) | \(…\) | \(r_{3,t-3}\) | \(r_{3,t-2}\) | \(r_{3, t-1}\) | \(…\) | |||||
| \(D_2\) | \(r_{2,0}\) | \(r_{2,1}\) | \(…\) | \(r_{2,t-2}\) | \(r_{2,t-1}\) | \(R_{2, t}\) | |||||
| \(D_1\) | \(r_{1,0}\) | \(r_{1,1}\) | \(r_{1,2}\) | \(…\) | \(r_{1,t-1}\) | \(R_{1,t}\) |
多项式 \(\sum_{\ell=1}^{t} x^\ell \cdot D_\ell(x)\) 的系数
根据式(式 9.11)中 \(R_{k, t}\) 的定义,这个值等于 \(d_{t + k}\). 而 \(d_{t + k}\) 是 \(D(x)\) 中 \(x^{t + k}\) 的系数,由此可知 \(C(x) = D(x) - \sum_{\ell=1}^t x^\ell \cdot D_\ell(x)\) 中大于 \(t\) 阶的项全部被抵消了,因此 \(C(x)\) 是 \(t\) 阶多项式。最后,我们注意到 \(x, x^2, …, x^t\) 的系数都是均匀随机的(因为对于 \(i = 1, …, t\),\(r_{i, 0}\) 都是均匀随机选取的)。故 \(C(x)\) 除了常数项为 \(A(0) \cdot B(0) = a \cdot b\),其他项的系数都是均匀随机的。
协议描述。我们在 \(\{\mathcal{F}_{\mathsf{VSS}}, \mathcal{F}_{\mathsf{eval}}^1, …, \mathcal{F}_{\mathsf{eval}}^n\}\)-混合模型下给出完整的协议描述,如图 9.27所示。为了简洁,我们用 \(\mathcal{F}_{\mathsf{eval}}\) 表示 \(n\) 个理想功能 \(\mathcal{F}_{\mathsf{eval}}^1, …, \mathcal{F}_{\mathsf{eval}}^n\).
\(\caption\){\(\{\mathcal{F}_{\mathsf{VSS}}, \mathcal{F}_{\mathsf{eval}}\}\)-混合模型下的 \(\Pi_\mathsf{VSS}^\mathsf{mult}\) 协议}
我们有以下定理。
实现乘法理想功能 \(\mathcal{F}_{\mathsf{mult}}\)
在实现了 \(\mathcal{F}_{\mathsf{VSS}}^\mathsf{subshare}\) 和 \(\mathcal{F}_{\mathsf{VSS}}^\mathsf{mult}\) 之后,我们终于可以对于恶意敌手实现乘法理想功能 \(\mathcal{F}_{\mathsf{mult}}\). 整体思路正如「直观思想」一节中所讲,参与方首先使用 \(\mathcal{F}_{\mathsf{VSS}}^\mathsf{subshare}\) 分发自己的输入份额的子份额,然后使用 \(\mathcal{F}_{\mathsf{VSS}}^\mathsf{mult}\) 分发输入份额乘积的子份额,最后,参与方在本地对子份额进行线性重组即可。
定义理想功能。我们首先在恶意敌手场景下定义理想功能。在半诚实场景下,\(\mathcal{F}_{\mathsf{mult}}\) 的函数表示如下:
其中 \(f_{ab}\) 是常数项为 \(a \cdot b\) 的均匀随机 \(t\) 阶多项式。
在恶意敌手场景下,理想功能 \(\mathcal{F}_{\mathsf{mult}}\) 的定义需要更加小心。在协议中,每个参与方需要作为秘密分发者调用 \(\mathcal{F}_{\mathsf{VSS}}^\mathsf{mult}\),然后参与方在本地计算子份额的线性组合。当被攻陷方作为秘密分发者时,它可以选择使用 \(\mathcal{F}_{\mathsf{VSS}}^\mathsf{mult}\) 分享的多项式 \(C(x)\). 我们考虑rushing adversary,他首先收到诚实方分发的子份额,然后再选择要分享的多项式 \(C(x)\),因此,敌手可以控制被攻陷方在输出多项式 \(f_{ab}\) 中持有的份额。不过,此时并不存在 \(f_{ab}\) 的秘密分发者,因此敌手只能决定被攻陷方自己的份额,而不能决定多项式 \(f_{ab}\). 理想功能 \(\mathcal{F}_{\mathsf{mult}}\) 的定义如图 9.28所示。
尽管 \(\mathcal{F}_{\mathsf{mult}}\) 的定义与半诚实的情况略有不同,但这个定义也足以实现安全的电路计算:这里敌手仅仅增加了决定被攻陷方的份额的能力,由于 \(f_{ab}\) 是 \(t\) 阶多项式,敌手决定 \(f_{ab}\) 的 \(t\) 个值不会泄露 \(f_{ab}(0) = a \cdot b\) 的任何信息。
协议构造。接下来,我们在 \(\{ \mathcal{F}_{\mathsf{VSS}}^\mathsf{subshare}, \mathcal{F}_{\mathsf{VSS}}^\mathsf{mult} \}\) 混合模型下构造乘法协议。参与方持有两条输入导线的秘密份额,每个参与方首先通过 \(\mathcal{F}_{\mathsf{VSS}}^\mathsf{subshare}\) 和 \(\mathcal{F}_{\mathsf{VSS}}^\mathsf{mult}\) 来分发秘密份额乘积的子份额,然后将这些子份额在本地线性重组,这与半诚实场景下的协议思路类似。具体而言,令 \(f_a(x)\) 和 \(f_b(x)\) 是两个 \(t\) 阶多项式,满足 \(f_a(0) = a, f_b(0) = b\). 令 \(h(x) = f_a(x) \cdot f_b(x) = a \cdot b + h_1 x + h_2 x^2 + … + h^{2t} x^{2t}\),令 \(V_{\boldsymbol{\alpha}}\) 是 \(\boldsymbol{\alpha}\) 的Vandermonde矩阵。因为Vandermonde矩阵是可逆的,我们有
因此 \(a \cdot b\) 是 \(f_a(\alpha_\ell) \cdot f_b(\alpha_\ell), \; \ell = 1, …, n\) 的线性组合。参与方首先通过 \(\mathcal{F}_{\mathsf{VSS}}^\mathsf{subshare}\) 和 \(\mathcal{F}_{\mathsf{VSS}}^\mathsf{mult}\) 分发 \(f_a(\alpha_\ell) \cdot f_b(\alpha_\ell)\) 的秘密份额,具体而言,令 \(C_1(x), …, C_n(x)\) 是满足 \(C_\ell(0) = f_a(\alpha_\ell) \cdot f_b(\alpha_\ell), \; \ell = 1, …, n\) 的随机 \(t\) 阶多项式,其中 \(C_\ell(x)\) 是 \(P_\ell\) 作为秘密分发者通过 \(\mathcal{F}_{\mathsf{VSS}}^\mathsf{mult}\) 分享的多项式。分享完成后,每个参与方 \(P_i\) 持有 \(C_1(\alpha_i), …, C_n(\alpha_i)\). 于是,每个参与方可以本地计算 \(Q(\alpha_i) = \sum_{\ell=1}^n \lambda_\ell \cdot C_\ell(\alpha_i)\),从而参与方持有了多项式 \(Q(x) = \sum_{\ell=1}^n \lambda_\ell \cdot C_\ell(x)\) 的秘密份额。因为 \(C_\ell(0) = f_a(\alpha_\ell) \cdot f_b(\alpha_\ell)\),故
此外,因为 \(C_\ell(x), \; \ell = 1, …, n\) 都是 \(t\) 阶多项式,所有 \(Q(x)\) 也是 \(t\) 阶多项式,即参与方持有了 \(a \cdot b\) 合法的秘密份额。完整的协议描述如图 9.29所示。
\(\caption\){\(\{\mathcal{F}_{\mathsf{VSS}}^\mathsf{subshare}, \mathcal{F}_{\mathsf{VSS}}^\mathsf{mult}\}\)-混合模型下的 \(\Pi_\mathsf{mult}\) 协议}
直观上看,\(\mathcal{F}_{\mathsf{VSS}}^\mathsf{subshare}\) 和 \(\mathcal{F}_{\mathsf{VSS}}^\mathsf{mult}\) 确保了参与方能获得正确的秘密份额且不泄露额外信息。不过,请注意,因为 \(\mathcal{F}_{\mathsf{VSS}}^\mathsf{subshare}\) 会向敌手泄露向量 \(\boldsymbol{Y}(x) = (g_1(x), …, g_n(x)) \cdot {\boldsymbol H}^\mathrm{T}\),其中 \(g_1, …, g_n\) 是定义了参与方的输入份额的多项式,\({\boldsymbol H}\) 是Reed-Solomon码的校验矩阵,所以在协议 \(\Pi_\mathsf{mult}\) 中敌手会获得 \(\boldsymbol{Y}_{A}(x) = (A_1(x), …, A_n(x)) \cdot {\boldsymbol H}^\mathrm{T}\) 和 \(\boldsymbol{Y}_{B}(x) = (B_1(x), …, B_n(x)) \cdot {\boldsymbol H}^\mathrm{T}\). 模拟器需要模拟这两条消息。这与 \(\mathcal{F}_{\mathsf{eval}}\) 的情形类似,模拟器能够进行模拟,因为 \(\boldsymbol{Y}_{A}(x)\) 和 \(\boldsymbol{Y}_{B}(x)\) 是在约束条件下的随机多项式向量。
我们有以下定理。
定理 9.3(在朴素模型(plain model)下UC-安全实现 \(\mathcal{F}_{\mathsf{VSS}}\))
定理 9.4(在 \(\mathcal{F}_{\mathsf{VSS}}^n\)-混合模型下UC-安全实现 \(\mathcal{F}_{\mathsf{mat}}^{\boldsymbol A}\))
定理 9.5(在 \(\mathcal{F}_{\mathsf{mat}}^{\boldsymbol A}\)-混合模型下UC-安全实现 \(\mathcal{F}_{\mathsf{VSS}}^\mathsf{subshare}\))
定理 9.6(在 \(\mathcal{F}_{\mathsf{VSS}}^\mathsf{subshare}\)-混合模型下UC-安全实现 \(\mathcal{F}_{\mathsf{eval}}\))
定理 9.7(在 \(\{\mathcal{F}_{\mathsf{VSS}}, \mathcal{F}_{\mathsf{eval}}\}\)-混合模型下UC-安全实现 \(\mathcal{F}_{\mathsf{VSS}}^\mathsf{mult}\))
定理 9.8(在 \(\{\mathcal{F}_{\mathsf{VSS}}^\mathsf{subshare}, \mathcal{F}_{\mathsf{VSS}}^\mathsf{mult}\}\)-混合模型下UC-安全实现 \(\mathcal{F}_{\mathsf{mult}}\))
根据通用组合定理(定理 4.3),我们有以下结论。
\(\{ \mathcal{F}_{\mathsf{VSS}}, \mathcal{F}_{\mathsf{mult}} \}\)-混合模型下的安全计算协议
现在,我们可以给出 \(\{ \mathcal{F}_{\mathsf{VSS}}, \mathcal{F}_{\mathsf{mult}} \}\)-混合模型下的安全计算协议,它对于控制了 \(t < n/3\) 个被攻陷方的静态恶意敌手UC-安全实现了函数计算功能。协议的思路与半诚实的情况非常类似,区别仅在于:(1) 在输入分享阶段,参与方调用理想功能 \(\mathcal{F}_{\mathsf{VSS}}\) 进行秘密分享;(2) 对于乘法门,参与方调用理想功能 \(\mathcal{F}_{\mathsf{mult}}\) 进行计算。 \(\mathcal{F}_{\mathsf{VSS}}\) 确保了恶意的被攻陷方也执行了正确的Shamir秘密分享,而 \(\mathcal{F}_{\mathsf{mult}}\) 确保了诚实方能获得乘法门的输出导线的正确份额。此外,根据 \(\mathcal{F}_{\mathsf{mult}}\) 的定义,它向敌手泄漏了被攻陷方在乘法门的输入导线上的份额,但是在协议中,敌手原本就知道这些信息,故 \(\mathcal{F}_{\mathsf{mult}}\) 不会造成任何额外的信息泄漏。最后,在输出重建阶段,对于每个输出值,参与方将秘密份额发送给输出值的接收方。此时,恶意的参与方可能会发送错误的份额(在半诚实场景下这不会发生),但是因为被攻陷方数量 \(t < n/3\),参与方可以调用Reed-Solomon解码算法重建正确的输出。
协议的形式化描述如图 9.30所示。
\(\caption\){\(\{ \mathcal{F}_{\mathsf{VSS}}, \mathcal{F}_{\mathsf{mult}} \}\)-混合模型下的安全函数计算协议 \(\Pi_\mathsf{sfe}\)}
我们有以下定理。
总结。在前文中,我们已经在朴素模型下实现了理想功能 \(\mathcal{F}_{\mathsf{VSS}}\) 和 \(\mathcal{F}_{\mathsf{mult}}\). 根据通用组合定理(定理 4.3),我们有以下结论。
至此,我们完成了BGW协议(恶意安全)的全部介绍与UC安全性证明。
BDOZ协议和SPDZ协议
「BGW协议(恶意安全)」一节的BGW协议在 \(t < n/3\)(诚实大多数)的场景下对于(静态)恶意敌手实现了完美的安全性。而BDOZ协议~[BDOZ, 2011]
和SPDZ协议~[DPSZ, 2012]能够对于控制 \(t = n - 1\) 个参与方的(静态)恶意敌手具有安全性。BDOZ协议和SPDZ协议都使用了Beaver三元组技术,在此基础上,通过消息认证码实现了恶意安全性。BDOZ协议的方法是对让每个参与方对每一个秘密份额都进行认证,即,当需要重建某个值时,各参与方公布自己的秘密份额以及它的 \(n - 1\) 个消息认证码标签,然后,每个参与方检查所有其他参与方的秘密份额的真实性(总通信量和计算量均为 \(O(n^2)\)). SPDZ消息认证码的设计更加巧妙,在重建某个值时,实现了线性的通信量和计算量。
下面,我们展开介绍。
BDOZ协议
直观思想
让我们以「基于Beaver三元组的MPC协议」一节的基于Beaver三元组的协议作为起点。为简单起见,我们先考虑两方计算的场景,并假设Beaver三元组是由可信第三方生成的。
敌手的攻击。我们已经证明,「基于Beaver三元组的MPC协议」一节的协议(图 7.1)是半诚实安全的。但是,如果参与方是恶意的,他可以进行怎样的攻击呢?假设参与方是 \(P_1\) 和 \(P_2\),其中 \(P_1\) 是恶意的被攻陷方。首先,对于输入分享阶段,假设 \(P_1\) 的输入为 \(x\),\(P_1\) 应该随机选取 \(x_1, x_2\),满足 \(x_1 + x_2 = x\),然后将 \(x_2\) 发给 \(P_2\). 恶意的 \(P_1\) 可以任意选取 \(x'_1, x'_2\),其中 \(x'_1 + x'_2 \neq x\),并将 \(x'_2\) 发给 \(P_2\). 但这不是问题,因为这等价于 \(P_2\) 将自己的输入替换为 \(x' = x'_1 + x'_2\). 我们之前讨论过,“输入替换”是敌手唯一被允许的影响。
然而,在计算乘法门和输出重建时,参与方需要公布自己的份额以进行秘密重建。此时,我们没有任何机制来确保恶意参与方公布正确的份额。以输出重建阶段为例,假设某个公共输出值为 \(y\),\(P_1\) 持有 \(y_1\),\(P_2\) 持有 \(y_2\),满足 \(y_1 + y_2 = y\). 此时,恶意的 \(P_1\) 可以发送另一个值 \(y'_1 \neq y_1\) 给 \(P_2\). 这样一来,\(P_2\) 得到的输出就变为 \(y' = y'_1 + y_2\). 这确实是一种对协议的攻击:该攻击使得 \(P_2\) 输出了错误的结果,但是在理想世界中,敌手无法做到这一点。在计算乘法门进行的秘密重建时,敌手也一样可以发起这种攻击,使参与方重建出错误的值。
因此,我们需要设计一种机制,使得参与方在秘密重建时必须公布正确的秘密份额。具体而言,假设参与方需要重建某个值 \(y\),其中 \(P_1\) 持有 \(y_1\),\(P_2\) 持有 \(y_2\). 当 \(P_1\)(\(P_2\)) 公布任何 \(y_1\)(\(y_2\)) 以外的其他值时都会被检测到,然后参与方终止协议。
消息认证码。回想一下,在「直观思想」一节的切分选择协议中,我们在实现输出真实性时也遇到了类似的问题,解决方法是使用消息认证码(Message Authentication Codes, MACs)。现在,我们再次使用该技术,让 \(P_2\) 对 \(P_1\) 的秘密份额进行认证(\(P_1\) 也对 \(P_2\) 的秘密份额进行认证)。我们使用的消息认证码的形式仍然是 \(\mathsf{Mac}_{\Delta, K}(x) = \Delta \cdot x + K\),其中 \(\Delta, K\) 是密钥,\(x\) 是认证的消息,\(\mathsf{Mac}_{\Delta, K}(x)\) 是标签,\(\Delta, K, x \in \mathbb{F}_p\). 不难看出,这是信息论安全的一次性消息认证码,敌手在不知道密钥的情况下成功伪造标签的概率为 \(1/p\)(“一次性”是因为如果敌手拥有同一密钥下的两个消息标签对 \((x_1, M_1), (x_2, M_2)\),他就可以求解密钥从而伪造标签)。
这个MAC的构造还具有一个很重要的性质。如果我们将不同密钥中的 \(\Delta\) 取相同的值(\(K\) 取不同的值),那么该MAC就具有了加法同态性。具体而言,设 \(M_1 = \mathsf{Mac}_{\Delta, K_1}(x_1) = \Delta \cdot x_1 + K_1, \; M_2 = \mathsf{Mac}_{\Delta, K_2}(x_2) = \Delta \cdot x_2 + K_2\),那么 \(M_1 + M_2 = \Delta \cdot (x_1 + x_2) + (K_1 + K_2)\),即 \(M_1 + M_2\) 是 \(x_1 + x_2\) 在密钥 \((\Delta, K_1 + K_2)\) 下合法的标签。而加法同态性正是我们计算算术电路时所需要的!
协议构造。让我们回到协议。我们称 \(\Delta\) 是全局MAC密钥,\(K\) 是本地MAC密钥。首先,\(P_1\) 应该持有全局密钥 \(\Delta_1\),\(P_2\) 持有全局密钥 \(\Delta_2\). 对于某个秘密值 \(x\),\(P_1\) 应该持有秘密份额 \((x_1, K_1, M_1)\),\(P_2\) 持有秘密份额 \((x_2, K_2, M_2)\),满足以下条件
\(x_1 + x_2 = x\)
\(M_1 = \Delta_2 \cdot x_1 + K_2\)
\(M_2 = \Delta_1 \cdot x_2 + K_1\)
即 \(x_1, x_2\) 是 \(x\) 的加法秘密分享,\(M_1\) 是 \(P_1\) 持有的(密钥 \((\Delta_2, K_2)\) 下的)\(x_1\) 的MAC标签,\(M_2\) 是 \(P_2\) 持有的(密钥 \((\Delta_1, K_1)\) 下的)\(x_2\) 的MAC标签。当需要重建 \(x\) 时,\(P_1\) 公布 \((x_1, M_1)\),\(P_2\) 公布 \((x_2, M_2)\),然后 \(P_1\) 检查 \(M_2 \stackrel{?}{=} \Delta_1 \cdot x_2 + K_1\),\(P_2\) 检查 \(M_1 \stackrel{?}{=} \Delta_2 \cdot x_1 + K_2\). 我们将该步骤称为秘密值的“打开”(可验证地)。如果需要将秘密值打开给某一个参与方而不是打开给所有人,只需将秘密份额和MAC标签发给那个参与方即可。
三元组的生成与输入分享。至此,我们对于BDOZ认证秘密分享成功实现了线性运算!并且MAC的加入使得秘密重建时参与方必须揭示正确的秘密份额,否则MAC验证将无法通过。如果我们还能够生成认证Beaver三元组和输入值的认证秘密分享,那么基于加法同态性和Beaver三元组的性质,我们就可以实现恶意安全的算术电路计算协议了!
在可信第三方的假设下,可以由可信第三方生成认证Beaver三元组 \(([a], [b], [c])\). 具体而言,可信第三方首先为 \(P_i\) 随机选择全局MAC密钥 \(\Delta_i, \; i = 1, 2\). 然后,他随机选择 \(a, b \leftarrow_{\$} \mathbb{F}\) 并计算 \(c = ab\). 接下来,可信第三方对 \(a, b, c\) 做加法秘密分享,并随机选择每一个本地MAC密钥,然后计算每一个秘密份额的MAC标签。最后,可信第三方向每个参与方分发全局MAC密钥 \(\Delta_i\) 以及认证秘密份额。
而对于输入值的分享,我们无法让参与方直接生成输入值的认证秘密分享。这里采取的方法是消耗一个随机值的认证秘密分享。协议如下:假设 \(P_1\) 的输入是 \(x_1\). 首先,可信第三方在生成认证Beaver三元组的同时还生成了足够的随机值的认证秘密分享。参与方选取一个随机值的认证秘密分享 \([a]\),然后将 \(a\) 打开给 \(P_1\). \(P_1\) 广播 \(\delta = x_1 - a\). 参与方计算 \([a] + \delta = [a + \delta] = [x_1]\),得到 \(x_1\) 的认证秘密分享。因为 \(a\) 是均匀随机的,所以 \(\delta = x_1 - a\) 不会泄漏 \(x_1\) 的任何信息。
两方协议小结。综上所述,假设由可信第三方生成Beaver三元组,在两方场景下,我们介绍了BDOZ协议的构造。我们做一个小结。
预处理(离线)阶段:
可信第三方生成足够的认证Beaver三元组和随机值的认证秘密分享。
在线阶段:
输入分享:设 \(P_i\) 的输入为 \(x_i\). 参与方取一个随机值的认证秘密分享 \([a]\),将 \(a\) 打开给 \(P_i\). \(P_i\) 广播 \(\delta = x_i - a\). 参与方计算 \([a] + \delta = [x_i]\).
- 逐门计算:
对于加法门、常数乘法门、常数加法门,分别计算
\[[x] + [y] = [x + y], \; \alpha[x] = [\alpha x], \; [x] + \alpha = [x + \alpha]\]对于乘法门,执行如下操作
取认证Beaver三元组 \(([a], [b], [c])\),本地计算 \([x] - [a] = [x - a], [y] - [b] = [y - b]\);
向所有参与方打开 \(d = x - a, \; e = y - b\);
参与方本地计算 \(d[b] + e[a] + [c] + de = [xy]\).
其中 \(K_{x_j}^i\) 是 \(P_i\) 持有的对(\(P_j\) 的秘密份额)\(x_j\) 认证的密钥,\(M_j(x_i) = \Delta_j \cdot x_i + K_{x_i}^j\) 是 \(x_i\) 在 \(P_j\) 的密钥下的MAC标签,\(\{ x_i, \{ K_{x_j}^i, M_j(x_i) \}_{j \in [n], j \neq i} \}\) 是 \(P_i\) 持有的 \(x\) 的秘密份额。也就是说,\(P_i\) 需要对每个参与方的份额都进行认证,同时 \(P_i\) 的份额也需要被每个其他参与方认证。当需要将 \([x]\) 打开给 \(P_j\) 时,每个参与方 \(P_i\) 发送 \(x_i, M_j(x_i)\) 给 \(P_j\),\(P_j\) 检查 \(M_j(x_i) \stackrel{?}{=} \Delta_j \cdot x_i + K_{x_i}^j\). 如果检查均通过,\(P_j\) 计算 \(x = \sum_{i=1}^n x_i\);否则,\(P_j\) 广播 \(\mathsf{fail}\). 如果要将 \(x\) 打开给所有人,那么对每个参与方执行上述打开操作。
在预处理阶段,由可信第三方生成所有认证Beaver三元组和随机值的认证秘密分享。在线阶段中,计算方式与两方场景完全相同。至此,我们在可信第三方生成认证Beaver三元组的假设下,完成了BDOZ协议的介绍。
协议描述
本节,我们给出BDOZ协议的形式化描述。这里,我们假设存在可信第三方生成Beaver三元组,并将其抽象为理想功能 \(\mathcal{F}_{\mathsf{prep}}\). 我们首先给出符号 \([\cdot]\) 的定义与运算规则,然后给出理想功能 \(\mathcal{F}_{\mathsf{prep}}\) 的定义,最后在 \(\mathcal{F}_{\mathsf{prep}}\)-混合模型下给出完整的协议描述。
符号表示与线性运算。对于消息 \(x \in \mathbb{F}_p\),密钥 \((\Delta, K) \in \mathbb{F}_p^2\),消息验证码MAC的定义为 \(\mathsf{Mac}_{\Delta, K}(x) = \Delta \cdot x + K\). 我们将 \(\Delta\) 称为全局MAC密钥,\(K\) 称为本地MAC密钥。每个参与方 \(P_i\) 持有全局MAC密钥的份额 \(\Delta_i\).(注:原始论文 [BDOZ, 2011]中,\(P_i\) 对每个参与方 \(P_j, \; j \neq i\) 生成了全局MAC密钥 \(\Delta^i_j\). 这没有必要,\(P_i\) 对所有其他参与方 \(P_j, \; j \neq i\) 只需使用同一个全局MAC密钥 \(\Delta_i\) 即可,因此本教材作了简化。)
其中,\(x = x_1 + … + x_n, \; M_j(x_i) = \mathsf{Mac}_{\Delta_j, K_{x_i}^j}(x_i)\).
对于秘密分享 \([ \cdot ]\),它的打开、加法、常数乘法、常数加法运算定义如图 9.12所示。
理想功能 \(\mathcal{F}_{\mathsf{prep}}\). 我们将预处理阶段中生成认证Beaver三元组(以及单个值的认证秘密分享)抽象为理想功能 \(\mathcal{F}_{\mathsf{prep}}\). \(\mathcal{F}_{\mathsf{prep}}\) 接受3种命令:\(\operatorname{Init}\), \(\operatorname{Singles}\), \(\operatorname{Triples}\),分别用于初始化、生成单个值的认证秘密分享、生成认证Beaver三元组。有两点需要注意:(1) \(\mathcal{F}_{\mathsf{prep}}\) 允许被攻陷方选择自己的秘密份额和MAC密钥,对于诚实方,这些值由 \(\mathcal{F}_{\mathsf{prep}}\) 随机选择;(2) \(\mathcal{F}_{\mathsf{prep}}\) 一次生成 \(u\) 个认证Beaver三元组(或单个值的认证秘密分享),其中 \(u\) 是一个参数。这是因为在实现 \(\mathcal{F}_{\mathsf{prep}}\) 的协议中,参与方一次生成 \(u\) 个认证Beaver三元组,\(\mathcal{F}_{\mathsf{prep}}\) 的定义需要与之吻合。
\(\mathcal{F}_{\mathsf{prep}}\) 的定义如图 9.31所示。
协议描述。下面,我们给出 \(\mathcal{F}_{\mathsf{prep}}\)-混合模型下,BDOZ协议的完整描述,如图 9.32所示。基于BDOZ认证秘密分享的线性同态性和可安全打开性,协议整体与基于Beaver三元组的协议非常类似,并实现了恶意安全性。
安全性证明
根据协议基于Beaver三元组的构造思想,不难发现,协议中泄漏的值都是均匀随机值。恶意敌手能够发动的攻击仅为公布错误的秘密份额。而根据MAC的构造,错误的秘密份额通过MAC验证的概率为 \(1/p\).
我们给出恶意敌手模型下的安全函数计算理想功能 \(\mathcal{F}_{\mathsf{sfe}}\),如图 9.33所示. 它与半诚实版本有两点区别:(1) 敌手 \(\mathcal{S}\) 可以随时终止协议;(2) 在输出阶段,敌手 \(\mathcal{S}\) 可以阻止诚实方获得输出。(注:注意,「BGW协议(恶意安全)」一节的协议虽然也是在恶意敌手模型下的,但是由于存在诚实大多数(\(t < n/3\)),因此敌手不能在协议执行时终止协议,也不能阻止诚实方获得输出。)
我们有以下定理。
预处理阶段的实现
本节,我们要移除可信第三方,通过安全多方计算的方式实现预处理阶段,即实现 \(\mathcal{F}_{\mathsf{prep}}\). 我们介绍BDOZ原文 [BDOZ, 2011]所提出的基于同态加密(semi-homomorphic encryption)(注:在学术界,同态加密(homomorphic encryption)通常指满足加法同态或乘法同态的加密方案,全同态加密(fully homomorphic encryption)指既满足加法同态又满足乘法同态的方案;在工业界,前者通常被称为半同态加密(partially homomorphic encryption)。这里的semi-homomorphic encryption实际上是homomorphic encryption,但额外要求被加密的值不能“太大”。我们仍将semi-homomorphic encryption称为同态加密而不是半同态加密,以避免混淆。)的方案。
同态加密定义。同态加密方案 \(\mathsf{PKE}\) 包含三个算法 \((\mathsf{Gen}, \mathsf{Enc}, \mathsf{Dec})\),其中:
\(\mathsf{Gen}(1^\kappa, p)\) 是一个随机算法,以安全参数 \(\kappa\) 和模数 \(p\) 为输入,输出公私钥对 \((\mathsf{pk}, \mathsf{sk})\) 以及参数 \(\mathcal{P} = (p, M, R, \mathcal{D}^d_\sigma, \mathbb{G})\). 其中,\(M, R\) 是整数,\(\mathcal{D}^d_\sigma\) 是一个算法,其生成长度为 \(d\) 的随机向量(作为加密算法的随机数)。我们要求 \(\mathcal{D}^d_\sigma\) 输出的向量 \(\boldsymbol{{r}}\) 以压倒性的概率满足 \(\| \boldsymbol{{r}} \|_\infty \leq \sigma\),其中 \(\| \boldsymbol{{r}} \|_\infty = \max(| r_1 |, …, | r_d |), \; \sigma < R\). \(\mathbb{G}\) 是密文所在的阿贝尔群。
\(\mathsf{Enc}_{\mathsf{pk}}(x, \boldsymbol{{r}})\) 是一个确定性算法,以整数 \(x \in \mathbb{Z}\) 和向量 \(\boldsymbol{{r}} \in \mathbb{Z}^d\) 为输入,输出密文 \(C \in \mathbb{G}\). 当随机数不重要时,我们将其简写为 \(\mathsf{Enc}_{\mathsf{pk}}(x)\). 给定 \(C_1 = \mathsf{Enc}_{\mathsf{pk}}(x_1, \boldsymbol{{r}}_1)\) 和 \(C_2 = \mathsf{Enc}_{\mathsf{pk}}(x_2, \boldsymbol{{r}}_2)\),有 \(C_1 + C_2 = \mathsf{Enc}_{\mathsf{pk}}(x_1 + x_2, \boldsymbol{{r}}_1 + \boldsymbol{{r}}_2)\). 对于密文 \(C\),如果存在 \(x, \boldsymbol{{r}}\) 满足 \(C = \mathsf{Enc}_{\mathsf{pk}}(x, \boldsymbol{{r}})\) 且 \(|x| \leq \tau, \; \| \boldsymbol{{r}} \|_\infty \leq \rho\),那么我们说 \(C\) 是一个 \((\tau, \rho)\)-密文。
\(\mathsf{Dec}_{\mathsf{sk}}(C)\) 是一个确定性算法,以密文 \(C \in \mathbb{G}\) 为输入,输出 \(x' \in \mathbb{Z}_p \cup \{ \bot \}\).
那么我们说它满足正确性。
IND-CPA安全性:同态加密方案 \(\mathsf{PKE}\) 的IND-CPA安全性如定义 2.1所示。
在实际使用中,Pailliar [Paillier, 1999]是一个著名的同态加密方案。
\(\Pi_\mathsf{PoPK}\)(Proof of Plaintext Knowledge):用于证明知道密文所加密的明文。
\(\Pi_\mathsf{PoCM}\)(Proof of Correct Multiplication):用于证明正确地进行了乘法运算。
形式化地说,\(\Pi_\mathsf{PoPK}\) 的陈述(statement)是公钥 \(\mathsf{pk}_{P}\) 和 \(u\) 个密文 \(C_k, \; k = 1, …, u\). 证明者证明所有密文 \(C_k\) 都是 \((2^{2u + \log u} \tau, 2^{2u + \log u} \rho)\)-密文。也就是说,\(\Pi_\mathsf{PoPK}\) 证明的关系为:
\(\Pi_\mathsf{PoCM}\) 的陈述是公钥 \(\mathsf{pk}_{P}, \mathsf{pk}_{V}\) 和 \(u\) 个密文三元组 \((A_k, B_k, C_k), \; k = 1, …, u\),其中 \(A_k\) 用 \(\mathsf{pk}_{P}\) 加密,\(B_k, C_k\) 用 \(\mathsf{pk}_{V}\) 加密(因此它们属于 \(\mathbb{G}_V\))。证明者证明 \(A_k = \mathsf{Enc}_{\mathsf{pk}_{P}}(a_k, \boldsymbol{{h}}_k)\),\(C_k = a_k B_k + \mathsf{Enc}_{\mathsf{pk}_{V}}(r_k)\),其中 \(r_k\) 为随机数。也就是说,\(\Pi_\mathsf{PoCM}\) 证明的关系为:
其中 \(\sum_{i=1}^n a_i = a\). 于是,参与方可以首先生成未认证的Beaver三元组 \(\langle a \rangle, \langle b \rangle, \langle c \rangle\).
接下来,参与方需要对秘密份额进行认证。参与方可以自行选择自己的全局MAC密钥和本地MAC密钥。然后,对于每一个份额,参与方需要获得其MAC标签 \(M_j(a_i) = \mathsf{Mac}_{\Delta_j, K_{a_i}^j}(a_i) = \Delta_j \cdot a_i + K_{a_i}^j\),其中 \(P_i\) 知道 \(a_i\),\(P_j\) 知道 \(\Delta_j, K_{a_i}^j\). 由于MAC标签的计算实质上也是OLE,我们似乎可以再次基于同态加密来实现。
然而,请注意,我们这里考虑的是恶意敌手场景,敌手可以任意地违背协议。因此,敌手不一定会将正确的秘密份额 \(a_i\) 作为OLE的输入。具体而言,对于被攻陷方 \(P_j\),假设他秘密份额是 \(a_j\),在为 \(a_j\) 计算MAC标签时,他首先可以向不同的参与方发送不同的值,此时,认证秘密分享 \([a]\) 就不是被良好定义的。
为此,我们可以要求 \(P_j\) 先对 \(a_j\) 进行承诺(或者加密,加密也是一种承诺的方式),从而强制 \(P_j\) 使用对不同参与方使用同样的值。但是,对于认证Beaver三元组,敌手仍然存在攻击的方式。考虑未认证的Beaver三元组 \(\langle a \rangle, \langle b \rangle, \langle c \rangle\),假设 \(P_j\) 持有 \(a_j, b_j, c_j\),满足 \(\sum a_i = a, \; \sum b_i = b, \; \sum c_i = c, \; c = ab\). 恶意的 \(P_j\) 可以不对 \(c_j\) 进行承诺,而是将其替换为 \(c'_j\),然后其他参与方都会对份额 \(c'_j\) 进行认证。这就使参与方实际上分享了 \(c' = c_1 + … + c'_j + … + c_n \neq c\),于是破坏了条件 \(c = ab\),也破坏了协议的正确性。
上述攻击表明,敌手有能力对Beaver三元组中的 \([c]\) 制造偏移量 \(\Delta\),使得 \(c = ab + \Delta\). 为了解决这个问题,协议通过“消耗”一个Beaver三元组来验证另一个Beaver三元组的正确性。具体如下。参与方取(不一定正确的)认证Beaver三元组 \(([a], [b], [c])\) 和 \(([f], [g], [h])\),他们希望验证 \(c = ab\). 首先,参与方产生(长度为 \(u\) 位)随机挑战值 \(e\),然后(可验证地)打开 \(\varepsilon = e[a] - [f], \; \delta = [b] - [g]\). 最后,参与方打开 \(e[c] - [h] - \delta[f] -\varepsilon[g] - \varepsilon \delta\),如果为0,那么输出 \(([a], [b], [c])\),否则,丢弃 \(([a], [b], [c])\). 上述检查的思路是:验证的式子 \(ec - h - \delta f -\varepsilon g - \varepsilon \delta\) 等于 \(e(c - ab) - (h - fg)\),如果 \(c = ab\) 且 \(h = fg\),那么验证一定通过;如果 \(c \neq ab\),那么验证通过等价于 \(e = (h - fg) / (c - ab)\),\(e\) 只有一个值能够满足该式,而 \(e\) 是长度为 \(u\) 的随机值,故上式成立的概率为 \(2^{-u}\).
协议描述。下面,我们给出预处理阶段的协议描述。
预处理阶段需要用到两个理想功能:
\(\caption\){子协议 \(\Pi_\mathsf{2\text{-}mult}\)}
我们将预处理阶段协议 \(\Pi_\mathsf{prep}\) 的一些部分写成子协议,它们分别是:
\(\caption\){子协议 \(\Pi_\mathsf{n\text{-}mult}\)}
最后,我们给出预处理阶段协议 \(\Pi_\mathsf{prep}\) 的描述,如图 9.40所示。
\(\caption\){\(\{ \mathcal{F}_{\mathsf{KeyReg}}, \mathcal{F}_{\mathsf{Rand}} \}\)-混合模型下的协议 \(\Pi_\mathsf{prep}\)}
为了正确解密,我们对同态加密方案的参数有一定的要求。如果一个同态加密方案能确保所有的密文都能被正确地解密,那么我们称这个同态加密方案是可容许的(admissible),即 \(M \geq 2^{5u + 2 \log u} \tau^2, \; R \geq 2^{4u + \log u} \tau \rho\).
我们有以下安全性定理。
该定理的证明通过归约到同态加密方案的一个性质,较为抽象,感兴趣的读者可以自行阅读文献 [BDOZ, 2011]。
最后,为了协议描述的完整性,我们给出零知识证明协议 \(\Pi_\mathsf{PoPK}\) 和 \(\Pi_\mathsf{PoCM}\) 的构造,如图 9.41和图 9.42所示。关于这两个协议的完备性、可靠性、零知识性的证明可参阅文献 [BDOZ, 2011]。
SPDZ协议
BDOZ协议中,参与方需要两两检验对方的秘密份额的MAC标签,因此存储量与参与方的数量成线性关系。SPDZ协议(读作``speedz'')由Damgård, Pastro, Smart, Zakarias提出~[DPSZ, 2012]
,协议通过更巧妙的设计,将认证秘密份额的存储量降低为常数级。
直观思想
对秘密份额认证并无必要。BDOZ协议通过对秘密份额进行认证来确保秘密值打开时的正确性。然而,我们实际上并不关心秘密份额是否正确,我们只需要打开的秘密值是正确的就可以了。基于这个观察,SPDZ协议直接对秘密值进行认证,它的消息认证码定义为 \(\mathsf{Mac}_\Delta(x) = \Delta \cdot x\),其中 \(x\) 是秘密值,\(\Delta\) 是(全局)MAC密钥。
不过,这样的改变带来了一个“先有鸡还是先有蛋”的问题——参与方必须知道MAC密钥才能检验MAC标签,但是知道了MAC密钥就可以任意地伪造MAC标签。为了解决这个问题,MAC密钥 \(\Delta\) 是被秘密分享的,参与方在重建密钥 \(\Delta\) 之前必须先对秘密份额和MAC标签进行承诺(commit)。这样一来,基于承诺的绑定性,当敌手知道 \(\Delta\) 时已经无法修改秘密份额和MAC标签,也就无法伪造MAC标签了。
也就是说,SPDZ协议中,秘密值 \(x\) 是被分享的,MAC密钥 \(\Delta\) 是被分享的,由于 \(\mathsf{Mac}_\Delta(x) = \Delta \cdot x\) 即 \(\Delta = \mathsf{Mac}_\Delta(x) / x\),为了使打开秘密值时不泄露 \(\Delta\)(计算乘法门时要进行秘密打开),MAC标签也需要是被分享的。我们用符号 \(\langle \cdot \rangle\) 来表示SPDZ认证秘密分享(注:本节中使用的符号含义与上一节不同,请读者避免混淆。),它的定义如下:
其中 \(x = x_1 + … + x_n\),\(M(x)_1, …, M(x)_n\) 是 \(\mathsf{Mac}_\Delta(x)\) 的加法秘密分享,即 \(M(x)_1 + … + M(x)_n = \mathsf{Mac}_\Delta(x) = \Delta \cdot x, \; \Delta = \Delta_1 + … + \Delta_n\),\(P_i\) 持有 \((x_i, M(x)_i)\) 和MAC密钥的份额 \(\Delta_i\).(注:在原始论文 [DPSZ, 2012]中,秘密分享的定义还包含了一个公开值 \(\delta\). 但这个值是不必要的,因此本教材的描述中将其删除了。)这样一来,参与方对一个秘密份额的存储量降为了常数级。
对于认证秘密分享 \(\langle x \rangle = ((x_1, \dots, x_n), (M(x)_1, \dots, M(x)_n)), \langle x' \rangle = ((x'_1, \dots, x'_n), (M(x')_1, \dots, M(x')_n))\) 和常数 \(\alpha \in \mathbb{F}_p\),定义加法、常数乘法、常数加法运算如下:
于是,我们可以对SPDZ认证秘密分享进行线性运算,并通过Beaver三元组技术计算乘法门。
部分打开。回想一下,在使用Beaver三元组计算乘法门时,假设两根输入导线上的值是 \(x\) 和 \(y\),计算过程是这样的:
取认证Beaver三元组 \((\langle a \rangle, \langle b \rangle, \langle c \rangle)\),参与方本地计算 \(\langle x \rangle - \langle a \rangle = \langle x - a \rangle, \langle y \rangle - \langle b \rangle = \langle y - b \rangle\);
向所有参与方打开 \(d = x - a, \; e = y - b\);
参与方本地计算 \(d \langle b \rangle + e \langle a \rangle + \langle c \rangle + de = \langle xy \rangle\).
注意到,计算过程中需要打开 \(d = x - a, \; e = y - b\). 对于SPDZ认证秘密分享,检验打开的秘密值需要重建MAC密钥 \(\Delta\),但是一旦MAC密钥被重建,之后敌手就可以任意伪造MAC标签了。也就是说,如果重建了MAC密钥 \(\Delta\),之后的乘法门计算和输出重建就无法保证正确性。
为了解决这个问题,SPDZ协议对乘法门中需要打开的值做“部分打开”,即,只重建秘密值,不重建MAC标签和MAC密钥。在协议最后的输出阶段,对所有打开过的值进行检验(这意味着协议过程中,参与方不一定正在对正确的值进行计算)。具体方式如下:
假设乘法门计算时需要打开 \(\langle d \rangle\),参与方执行“部分打开”:\(P_i\) 将 \(d_i\) 发送给 \(P_1\),\(P_1\) 计算 \(d = \sum_{i=1}^n d_i\) 并广播。
输出阶段,假设 \(a_1, …, a_T\) 是所有被部分打开的值,其中 \(\langle a_j \rangle = ((a_{j, 1}, …, a_{j, n}), (M(a_j)_1, …, M(a_j)_n))\). 参与方取一个随机值 \(e\),对于 \(i = 1, …, T\) 设置 \(e_i = e^i\),并计算 \(a = \sum_{j=1}^T e_j a_j\).
\(P_i\) 计算 \(M_i = \sum_{j=1}^T e_j \cdot M(a_j)_i\) 并对这个值进行承诺。
参与方打开全局MAC密钥 \(\Delta\).
\(P_i\) 打开承诺值 \(M_i\). 参与方检查 \(\Delta \cdot a \stackrel{?}{=} \sum_{i=1}^n M_i\). 若不满足,则终止协议。
其中 \(\Delta = \Delta_1 + … + \Delta_n, \; M(\Delta)_i^1 + … + M(\Delta)_i^n = \beta_i \Delta\). 参与方 \(P_i\) 持有 \(\Delta_i, \beta_i, M(\Delta)_1^i, …, M(\Delta)_n^i\). 这里,\(M(\Delta)_i = M(\Delta)_i^1 + … + M(\Delta)_i^n = \mathsf{Mac}_{\beta_i}(\Delta) = \beta_i \Delta\) 是 \(\Delta\) 在 \(P_i\) 的私有MAC密钥 \(\beta_i\) 下的MAC标签。因此,\([\![ \Delta ]\!]\) 可以向任一参与方可验证地打开:如果要向 \(P_i\) 打开 \([\![ \Delta ]\!]\),每个参与方 \(P_j\) 发送 \(\Delta_j, M(\Delta)_i^j\) 给 \(P_i\),然后 \(P_i\) 计算 \(\Delta = \Delta_1 + … + \Delta_n\) 并检查 \(\sum_{j=1}^n M(\Delta)_i^j \stackrel{?}{=} \beta_i \Delta\)(如果要打开给所有人,那么对每个参与方执行该操作)。注意,对于 \(\langle \cdot \rangle\) 秘密分享,每个参与方的存储量是常数;对于 \([\![ \cdot ]\!]\) 秘密分享,每个参与方的存储量是线性的。
输入分享。我们还需要解决输入分享的问题。假设 \(P_i\) 的输入为 \(x_i\),在BDOZ协议中,参与方取一个随机值的秘密分享 \([a]\) 并打开给 \(P_i\),然后 \(P_i\) 广播 \(\delta = x_i - a\),参与方计算 \([a] + \delta\). 基于符号 \(\langle \cdot \rangle\) 和 \([\![ \cdot ]\!]\) 的定义,我们可以采用类似的方法,通过一对秘密分享 \(\langle r \rangle, [\![ r ]\!]\) 来实现输入分享。方法如下:
设 \(P_i\) 的输入为 \(x_i\). 取随机值的一对秘密分享 \(\langle r \rangle, [\![ r ]\!]\).
将 \([\![ r ]\!]\) 打开给 \(P_i\).
\(P_i\) 广播 \(\delta = x_i - r\).
参与方计算 \(\langle r \rangle + \delta = \langle x_i \rangle\).
三元组正确性检验。最后,与「预处理阶段的实现」一节中类似,因为考虑的是恶意敌手,预处理阶段产生的Beaver三元组 \((\langle a \rangle, \langle b \rangle, \langle c \rangle)\) 不一定满足 \(c = ab\). 我们需要消耗另一个Beaver三元组 \((\langle f \rangle, \langle g \rangle, \langle h \rangle)\) 以检验其正确性。协议如下:
取两个Beaver三元组 \((\langle a \rangle, \langle b \rangle, \langle c \rangle)\) 和 \((\langle f \rangle, \langle g \rangle, \langle h \rangle)\);
参与方取随机值 \(t\);
部分打开 \(t \cdot \langle a \rangle - \langle f \rangle\),记为 \(\rho\);部分打开 \(\langle b \rangle - \langle g \rangle\),记为 \(\sigma\);
计算 \(t \cdot \langle c \rangle - \langle h \rangle - \sigma \cdot \langle f \rangle - \rho \cdot \langle g \rangle - \sigma \cdot \rho\),并将结果部分打开;
如果结果不为0,丢弃 \((\langle a \rangle, \langle b \rangle, \langle c \rangle)\);否则,输出 \((\langle a \rangle, \langle b \rangle, \langle c \rangle)\).
在协议的输出阶段,所有部分打开的值都需要检验正确性。
小结。我们对上述思路作一个小结,给出SPDZ协议的非形式化描述。
生成MAC密钥的认证秘密分享 \([\![ \Delta ]\!]\),足够的认证Beaver三元组 \((\langle a \rangle, \langle b \rangle, \langle c \rangle)\),足够的随机值的秘密分享对 \(\langle r \rangle, [\![ r ]\!]\),以及两个随机值的认证秘密分享 \([\![ t ]\!], [\![ e ]\!]\).
输入分享:设 \(P_i\) 的输入为 \(x_i\). 取随机值的秘密分享对 \(\langle r \rangle, [\![ r ]\!]\),将 \([\![ r ]\!]\) 打开给 \(P_i\). \(P_i\) 广播 \(\delta = x_i - r\). 参与方计算 \(\langle r \rangle + \delta = \langle x_i \rangle\).
- 逐门计算:
对于加法门、常数乘法门、常数加法门,分别计算
\[\langle x \rangle + \langle y \rangle = \langle x + y \rangle, \; \alpha\langle x \rangle = \langle \alpha x \rangle, \; \langle x \rangle + \alpha = \langle x + \alpha \rangle\]对于输入为 \(\langle x \rangle, \langle y \rangle\) 的乘法门,执行如下操作
检验三元组正确性:
取两个Beaver三元组 \((\langle a \rangle, \langle b \rangle, \langle c \rangle)\) 和 \((\langle f \rangle, \langle g \rangle, \langle h \rangle)\);
打开随机值 \([\![ t ]\!]\);
部分打开 \(t \cdot \langle a \rangle - \langle f \rangle\),记为 \(\rho\);部分打开 \(\langle b \rangle - \langle g \rangle\),记为 \(\sigma\);
计算 \(t \cdot \langle c \rangle - \langle h \rangle - \sigma \cdot \langle f \rangle - \rho \cdot \langle g \rangle - \sigma \cdot \rho\),并将结果部分打开;
如果结果不为0,丢弃 \((\langle a \rangle, \langle b \rangle, \langle c \rangle)\);否则,将 \((\langle a \rangle, \langle b \rangle, \langle c \rangle)\) 用于乘法门计算。
计算乘法门:
使用上一步检验过的三元组 \((\langle a \rangle, \langle b \rangle, \langle c \rangle)\),部分打开 \(\langle x \rangle - \langle a \rangle\),记为 \(d\),部分打开 \(\langle y \rangle - \langle b \rangle\),记为 \(\epsilon\);
参与方本地计算 \(d \langle b \rangle + \epsilon \langle a \rangle + \langle c \rangle + d \epsilon = \langle xy \rangle\).
假设 \(a_1, …, a_T\) 是所有被部分打开的值,其中 \(\langle a_j \rangle = ((a_{j, 1}, …, a_{j, n}), (M(a_j)_1, …, M(a_j)_n))\). 参与方打开随机值 \([\![ e ]\!]\),对于 \(i = 1, …, T\) 设置 \(e_i = e^i\),并计算 \(a = \sum_{j=1}^T e_j a_j\).
\(P_i\) 计算 \(M_i = \sum_{j=1}^T e_j \cdot M(a_j)_i\) 并对这个值进行承诺。对于 \(j = 1, …, n\),\(P_i\) 对 \(y_{j, i}\) 和 \(M(y_j)_i\) 进行承诺。
打开全局MAC密钥 \([\![ \Delta ]\!]\).
\(P_i\) 打开承诺值 \(M_i\). 参与方检查 \(\Delta \cdot a \stackrel{?}{=} \sum_{i=1}^n M_i\). 若不满足,则终止协议。
对于 \(j = 1, …, n\),\(P_i\) 向 \(P_j\) 打开承诺值 \(y_{j, i}\) 和 \(M(y_j)_i\). \(P_j\) 计算 \(y_j = \sum_{i=1}^n y_{j, i}\) 并检查 \(\sum_{i=1}^n M(y_j)_i \stackrel{?}{=} \Delta \cdot y_j\). 若检查通过,则 \(P_j\) 输出 \(y_j\).
协议描述
本节,我们将预处理阶段抽象为理想功能 \(\mathcal{F}_{\mathsf{prep}}\),将承诺方案抽象为理想功能 \(\mathcal{F}_{\mathsf{com}}\),然后在 \(\{ \mathcal{F}_{\mathsf{prep}}, \mathcal{F}_{\mathsf{com}} \}\)-混合模型下给出SPDZ协议的形式化描述。
符号表示。对于消息 \(x \in \mathbb{F}_p\),密钥 \(\Delta \in \mathbb{F}_p\),消息验证码MAC的定义为 \(\mathsf{Mac}_\Delta(x) = \Delta \cdot x\).
秘密分享 \(\langle \cdot \rangle\) 的定义如下:
其中 \(x = x_1 + … + x_n, \; M(x)_1 + … + M(x)_n = \mathsf{Mac}_\Delta(x) = \Delta \cdot x\),\(P_i\) 持有 \((x_i, M(x)_i)\) 和MAC密钥的份额 \(\Delta_i\),满足 \(\Delta = \Delta_1 + … + \Delta_n\).
秘密分享 \(\langle \cdot \rangle\) 的部分打开、加法、常数乘法、常数加法运算的定义如图 9.13所示。
其中 \(x = x_1 + … + x_n, \; M(x)_i^1 + … + M(x)_i^n = \mathsf{Mac}_{\beta_i}(x) = \beta_i x\). 参与方 \(P_i\) 持有 \(x_i, \beta_i, M(x)_1^i, …, M(x)_n^i\).
秘密分享 \([\![ \cdot ]\!]\) 的打开操作的定义如图 9.14所示。
理想功能 \(\mathcal{F}_{\mathsf{prep}}\). 我们将预处理阶段抽象为理想功能 \(\mathcal{F}_{\mathsf{prep}}\),它接受3种命令:\(\operatorname{Init}\), \(\operatorname{Pairs}\), \(\operatorname{Triples}\),分别用于初始化、生成认证秘密分享对、生成认证Beaver三元组。需要注意的是,\(\mathcal{F}_{\mathsf{prep}}\) 允许被攻陷方选择自己的秘密份额和MAC密钥份额,并且允许敌手在认证秘密分享中加入偏移量 \(\delta\). 也就是说,敌手有能力让 \(\mathcal{F}_{\mathsf{prep}}\) 生成错误的认证秘密分享,但是错误的认证秘密分享在协议运行中通过验证的概率是可忽略的。因此,这等价于敌手使协议终止。
\(\mathcal{F}_{\mathsf{prep}}\) 的定义如图 9.44所示。为了表示的方便,我们定义两个函数 \(\mathsf{Bracket}\) 和 \(\mathsf{Angle}\),分别用于生成 \([\![ \cdot ]\!]\) 秘密分享和 \(\langle \cdot \rangle\) 秘密分享。
理想功能 \(\mathcal{F}_{\mathsf{com}}\). 我们给出承诺理想功能 \(\mathcal{F}_{\mathsf{com}}\) 的定义,如图 9.43所示。\(\mathcal{F}_{\mathsf{com}}\) 允许参与方对某个值承诺,然后打开给所有参与方,或打开给某个指定参与方。其中,\(\mathsf{cid}\) 表示commitment id,用于给承诺编号。为了描述的简洁性,在协议描述中,我们直接称“\(P_i\) 调用 \(\mathcal{F}_{\mathsf{com}}\) 对 \(x_i\) 进行承诺”、“\(P_i\) 调用 \(\mathcal{F}_{\mathsf{com}}\) (向 \(P_i\))打开 \(x_i\)”。 \(\mathcal{F}_{\mathsf{com}}\) 可以通过任何UC安全的承诺方案来实现 [Dam et al.; Lindell, 2011]。
协议描述。下面,我们给出 \(\{ \mathcal{F}_{\mathsf{prep}}, \mathcal{F}_{\mathsf{com}} \}\)-混合模型下,SPDZ协议的形式化描述,如图 9.45所示。
\(\caption\){\(\{ \mathcal{F}_{\mathsf{prep}}, \mathcal{F}_{\mathsf{com}} \}\)-混合模型下的SPDZ协议 \(\Pi_\mathsf{SPDZ}\)}
安全性证明
我们给出SPDZ协议的安全性证明。因为SPDZ协议也是基于Beaver三元组技术构造的,所以证明思路以及模拟器的构造与BDOZ协议中类似。
预处理阶段的实现
(注:此部分授课老师/读者可以选择性地教学/阅读。)
本节将实现预处理阶段理想功能 \(\mathcal{F}_{\mathsf{prep}}\). 我们介绍SPDZ原文 [DPSZ, 2012]所提出的基于有限同态加密(somewhat homomorphic encryption)的方案。有限同态加密既满足加法同态也满足乘法同态,但是计算的次数是有限的,也就是要求计算的电路不能太大。因此它比较适合用于在预处理阶段计算大量的认证Beaver三元组。
有限同态加密定义。首先,定义密文空间 \(M = (\mathbb{F}_p)^s\). 我们用 \(+\) 和 \(\cdot\) 表示 \(M\) 中元素的逐项加法和逐项乘法。假设存在单射的编码函数 \(\mathsf{encode}\) 将 \((\mathbb{F}_p)^s\) 映射到环 \(R = \mathbb{Z}^N\),其中 \(N\) 是一个整数;假设存在解码函数 \(\mathsf{decode}\) 以 \(\mathbb{Z}^N\) 上的元素为输入,输出 \((\mathbb{F}_p)^s\) 上的元素。并且,对于所有 \(\boldsymbol{{m}} \in M\) 满足 \(\mathsf{decode}(\mathsf{encode}(\boldsymbol{{m}})) = \boldsymbol{{m}}\). 此外,解密操作与域的参数是兼容的,即,对于所有 \(\boldsymbol{{x}} \in \mathbb{Z}^N\) 有 \(\mathsf{decode}(\boldsymbol{{x}}) = \mathsf{decode}(\boldsymbol{{x}} \; (\bmod \; p))\). 最后,编码算法生成的向量是“短的”,即,对于所有 \(\boldsymbol{{m}} \in (\mathbb{F}_p)^s\) 有 \(\| \mathsf{encode}(\boldsymbol{{m}}) \|_\infty \leq \tau\),其中 \(\tau = p / 2\).
接下来的介绍中,当我们讨论明文空间 \(M\) 时,我们默认它隐含地带有某个整数 \(N\) 所对应的编码函数 \(\mathsf{encode}\) 和解码函数 \(\mathsf{decode}\). 对于 \(x \in \mathbb{F}_p\),定义 \(\mathsf{Diag}_{s}(x) = (x, x, …, x) \in (\mathbb{F}_p)^s\).
有限同态加密方案以 \(\kappa\) 为安全参数,包含5个算法 \((\mathsf{ParamGen}, \mathsf{KeyGen}, \mathsf{KeyGen}^*, \mathsf{Enc}, \mathsf{Dec})\).
\(\mathsf{ParamGen}(1^\kappa, M)\): 这是参数生成算法,它输出整数 \(N\),函数 \(\mathsf{encode}\) 和 \(\mathsf{decode}\) 的定义,以及随机化算法 \(D_\rho^d\) 的描述,其中 \(D_\rho^d\) 的输出是 \(\mathbb{Z}^d\) 中的向量。我们假设 \(D_\rho^d\) 输出的 \(\boldsymbol{{r}}\) 以压倒性的概率满足 \(\| \boldsymbol{{r}} \|_\infty \leq \rho\). \(D_\rho^d\) 给加密算法提供所需的随机数。算法 \(\mathsf{ParamGen}\) 还输出一个加法阿贝尔群 \(\mathbb{G}\)。群 \(\mathbb{G}\) 同时拥有一个乘法运算(不一定封闭),该运算是交换的,并且对 \(\mathbb{G}\) 上的加法满足分配律。假设密文位于群 \(\mathbb{G}\) 中。我们用符号 \(\boxplus\) 和 \(\boxtimes\) 来表示 \(\mathbb{G}\) 上的加法和乘法运算,并将这些运算自然地扩展到 \(\mathbb{G}\) 中元素构成的向量和矩阵上。最后,\(\mathsf{ParamGen}\) 输出一个允许的算术电路集合 \(C\),这些电路定义了能够在密文上计算的函数集合。我们假设所有其他算法都隐含地把 \(\mathsf{ParamGen}\) 的输出 \(P = (1^\kappa, N, \mathsf{encode}, \mathsf{decode}, D_\rho^d, \mathbb{G}, C)\) 作为输入。
\(\mathsf{KeyGen}()\): 该算法生成公钥 \(\mathsf{pk}\) 和私钥 \(\mathsf{sk}\).
\(\mathsf{Enc}_{\mathsf{pk}}(\boldsymbol{{x}}, \boldsymbol{{r}})\): 这是一个确定性算法,输入是 \(\boldsymbol{{x}} \in \mathbb{Z}^N, \boldsymbol{{r}} \in \mathbb{Z}^d\),输出是密文 \(c \in \mathbb{G}\). 这里的 \(\boldsymbol{{x}}\) 是 \(\mathsf{encode}\) 的输出,\(\boldsymbol{{r}}\) 是 \(D_\rho^d\) 的输出。因此对于 \(\boldsymbol{{m}} \in M\),我们可以用 \(\mathsf{Enc}_{\mathsf{pk}}(\boldsymbol{{m}})\) 表示对其加密。当随机数不重要时,我们简写为 \(\mathsf{Enc}_{\mathsf{pk}}(\boldsymbol{{x}})\). 为了使后续的零知识证明能够成立,我们要求对 \(V\) 个“干净”的密文(即 \(V\) 的值“较小”)进行相加时,所得密文等于将明文相加后再进行加密的结果,即
\(\mathsf{Dec}_{\mathsf{sk}}(c)\): 解密算法以私钥 \(\mathsf{sk}\) 和密文 \(c\) 为输入,输出 \(\boldsymbol{{m}} \in M\) 或符号 \(\bot\).
我们现在可以定义上述加密方案所需满足的各种性质。在此之前,先引入一些符号:对于某个函数 \(f \in C\),用 \(n(f)\) 表示函数 \(f\) 的变量个数,并用 \(\hat{f}\) 表示 \(f\) 在群 \(\mathbb{G}\) 上对应的函数。具体地说,给定 \(f\),我们将其表达式中的加法 \(+\) 替换为群 \(\mathbb{G}\) 上的加法运算 \(\boxplus\),乘法 \(\cdot\) 替换为群 \(\mathbb{G}\) 上的乘法运算 \(\boxtimes\),常数 \(c\) 替换为 \(\mathsf{Enc}_{\mathsf{pk}}(\mathsf{encode}(c), \boldsymbol{0})\) 得到 \(\hat{f}\). 此外,给定 \(n(f)\) 个向量 \(\boldsymbol{{x}}_1, …, \boldsymbol{{x}}_{n(f)}\),我们以自然的方式定义 \(f(\boldsymbol{{x}}_1, …, \boldsymbol{{x}}_{n(f)})\),指的是在每个索引上计算函数 \(f\).
那么,我们称它满足 \((B_{plain}, B_{rand}, C)\)-正确性。
如果一个密文可以在上述实验中作为密文 \(c\) 得到,那么我们称它是 \((B_{plain}, B_{rand}, C)\)-可容许的(admissible)。也就是说,该密文是通过将函数 \(f \in C\) 应用于(合法的)受 \(B_{plain}\) 限制的编码和 \(B_{rand}\) 限制的随机数生成的密文而得到的。
\(\mathsf{KeyGen}^*()\): 这是一个随机算法,输出一个无意义的公钥 \(\widetilde{\mathsf{pk}}\),满足对于任意消息 \(\boldsymbol{{x}}\),\(\mathsf{Enc}_{\widetilde{\mathsf{pk}}}(\boldsymbol{{x}})\) 与 \(\mathsf{Enc}_{\widetilde{\mathsf{pk}}}(\boldsymbol{0})\) 是统计上不可区分的。此外,令 \((\mathsf{pk}, \mathsf{sk}) \leftarrow \mathsf{KeyGen}(), \widetilde{\mathsf{pk}} \leftarrow \mathsf{KeyGen}^*()\),那么 \(\mathsf{pk}\) 与 \(\widetilde{\mathsf{pk}}\) 在计算上也是不可区分的。此性质暗含了该加密方案是 IND-CPA 安全的。
分布式解密:我们希望参与方能够实现分布式解密。对此,我们假设系统已经设置好了一个公钥,并且对应的私钥在参与方之间秘密分享(这是系统的初始设置(setup assumption)),使参与方可以共同对密文进行解密。我们假设参与方始终只对 \((B_{plain}, B_{rand}, C)\)-可容许的密文进行解密,这一约束由我们的协议所保证。
具体而言,我们假设存在理想功能 \(\mathcal{F}_{\mathsf{KeyGen}}\),如图 9.46所示。它的基本功能是生成一个密钥对,并让私钥在参与方之间秘密分享。这个秘密分享方案可以认为是加密系统的一个参数。
此外,我们还希望我们的加密系统能够实现理想功能 \(\mathcal{F}_{\mathsf{KeyGenDec}}\),如图 9.47所示。通过调用该理想功能,参与方可以共同解密 \((B_{plain}, B_{rand}, C)\)-可容许的密文,但只在被动攻击下安全。也就是说:敌手能够获得正确的解密结果,并且有能力决定诚实方最终得到的结果是什么。
现在,我们终于可以给出底层加密系统性质的定义。这是要在协议中使用该加密系统,必须满足的基本性质。这里我们引入信息论安全参数 \(u\),用于控制零知识证明协议中出现的误差。
集合 \(C\) 是协议所需的所有对密文的计算操作。我们始终假定 \(B_{plain}\) 和 \(B_{rand}\) 以上述形式基于参数 \(\tau, \rho, u\) 所定义。这是因为我们能够通过零知识证明协议强制被攻陷方遵守这些约束。
在实际使用中,BGV [Bra et al., 2012]是一个著名的有限同态加密/全同态加密方案。
零知识证明。预处理阶段协议需要用到一个关于明文知识的零知识证明(zero-knowledge Proof of Plaintext Knowledge),它的陈述是公钥 \(\mathsf{pk}\) 和 \(u\) 个密文,证明者证明自己知道密文中的明文和随机数,且它们满足 \(B_{plain}, B_{rand}\) 的界限约束。形式化地说,它证明的关系为:
零知识证明协议 \(\Pi_\mathsf{PoPK}\) 如图 9.48所示。
直观思想。因为有限同态加密既满足加法同态也满足乘法同态,是一个非常强大的密码学原语,因此基于它实现预处理阶段并不困难。简单来说,当生成认证Beaver三元组 \((\langle a \rangle, \langle b \rangle, \langle c \rangle)\) 时,参与方 \(P_i\) 首先在本地随机生成 \(a\) 和 \(b\) 的秘密份额 \(a_i\) 和 \(b_i\),然后所有参与方公布 \(\mathsf{Enc}_{\mathsf{pk}}(a_1), …, \mathsf{Enc}_{\mathsf{pk}}(a_n), \mathsf{Enc}_{\mathsf{pk}}(b_1), …, \mathsf{Enc}_{\mathsf{pk}}(b_n)\),并通过零知识证明 \(\Pi_\mathsf{PoPK}\) 证明合法性。基于加密方案的同态性,可以计算 \(\mathsf{Enc}_{\mathsf{pk}}(c) = (\mathsf{Enc}_{\mathsf{pk}}(a_1) \boxplus … \boxplus \mathsf{Enc}_{\mathsf{pk}}(a_n) ) \boxtimes (\mathsf{Enc}_{\mathsf{pk}}(b_1) \boxplus … \boxplus \mathsf{Enc}_{\mathsf{pk}}(b_n))\),然后调用子协议 \(\mathsf{Reshare}\) 通过分布式解密获得 \(c\) 的秘密份额。对于秘密值的MAC标签,也可以通过类似的方法计算。
协议描述。我们给出预处理阶段的协议描述,它需要调用两个理想功能:\(\mathcal{F}_{\mathsf{KeyGenDec}}\)(图 9.47)和 \(\mathcal{F}_{\mathsf{Rand}}\)(图 9.35)。
我们将预处理阶段协议的一些部分写成子协议,它们分别是:
\(\Pi_\mathsf{Reshare}\):它的输入是 \(e_{\boldsymbol{{m}}} = \mathsf{Enc}_{\mathsf{pk}}(\boldsymbol{{m}})\) 和 \(enc = \mathsf{NewCiphertext} / \mathsf{NoNewCiphertext}\). 协议使参与方获得 \(\boldsymbol{{m}}\) 的秘密分享,并且如果 \(enc = \mathsf{NewCiphertext}\),额外输出 \(e'_{\boldsymbol{{m}}}\),它将密文 \(e_{\boldsymbol{{m}}}\) 重随机化(re-randomize)。协议如图 9.49所示。
\(\Pi_\mathsf{PBracket}\):用于生成 \([\![ \cdot ]\!]\) 秘密分享,如图 9.50所示。
\(\Pi_\mathsf{PAngle}\):用于生成 \(\langle \cdot \rangle\) 秘密分享,如图 9.51所示。
最后,我们给出预处理阶段协议 \(\Pi_\mathsf{prep}\) 的描述,如图 9.52所示。
\(\caption\){\(\{ \mathcal{F}_{\mathsf{KeyGenDec}}, \mathcal{F}_{\mathsf{Rand}} \}\)-混合模型下的协议 \(\Pi_\mathsf{prep}\)}
我们有以下安全性定理。
该定理的证明请参阅文献 [DPSZ, 2012]。
本章思考题
让参与方用零知识证明协议来证明一个永真式(例如一个Pedersen承诺 \(C\) 是对某个消息 \(m\) 的承诺)是否有意义?为什么?
Shamir秘密分享和Reed-Solomon编码之间的关系是什么?
在朴素模型 (plain model,又叫做标准模型standard model)下是否存在恶意安全的两方OT协议,为什么?
学习笔记
记录协议细节、模拟器构造与图中记号对照。
