4 Implementation Techniques

Less Expensive Garbling

A Pragmatic Introduction to Secure Multi-Party Computation Reading Notes

1 Introduction

Outsourced Computation

一方拥有数据，想知道对这些数据进行某种运算的结果；另一方接收数据并进行运算，返回结果。这期间第二方不应该知道任何关于输入、输出结果、中间量的任何信息。

同态加密（homomorphic encryption）允许对加密数据进行操作。分为部分同态加密（partially homomorphic encryption）和完全同态加密（FHE, fully homomorphic encryption）

Multi-Party Computation

持有数据的一些人想共同计算一个函数，但是他们不互相信任，也没有可信任的第三方。

3 Fundamental MPC Protocols

Yao’s Garbled Circuit Protocol (Yao’s GC)

混淆门的产生过程.

Parameters: Boolean circuit \(\mathcal C\) implementing function \(\mathcal F\), security parameter \(\kappa\).

GC generation:

1. Wire Label Generation. For each wire \(w_i\) of \(\mathcal C\), randomly choose wire labels,
   \[w_i^b = (k_i^b\in_R\{0, 1\}^{\kappa}, p_i^b\in_R\{0,1\})\] , such that \(p_i^b = 1−p^{1−b}_i\).
2. Garbled Circuit Construction. For each gate \(G_i\) of \(\mathcal C\) in topological order:
   1. Assume \(G_i\) is a \(2\)-input Boolean gate implementing function \(g_i\): \(w_c = g_i(w_a, w_b)\), where input labels are \(w^0_a = (k^0_a, p^0_a), w^1_a =(k^1_a, p^1_a), w^0_b= (k^0_b, p^0_b), w^1_b= (k^1_b, p^1_b)\), and the output labels are \(w^0_c = (k^0_c, p^0_c), w^1_c = (k^1_c, p^1_c)\).
      
   2. Create \(G_i\)’s garbled table. For each of \(2^2\) possible combinations of \(G_i\)’s input values \(v_a, v_b\in\{0, 1\}\), set
      \[e_{v_a,v_b} = H(k^{v_a}_a|| k^{v_b}_b|| i)\oplus w_c^{g_i(v_a,v_b)}\] Sort entries \(e\) in the table by the input pointers, placing entry \(e_{v_a,v_b}\) in position \(\langle p^{v_a}_a , p^{v_b}_b\rangle\).
3. Output Decoding Table. For each circuit-output wire \(w_i\) (the output of gate \(G_j\)) with labels \(w_i^0 = (k_i^0, p^0_i), w_i^1 = (k_i^1, p_1^i)\), create garbled output table for both possible wire values \(v\in\{0, 1\}\). Set
   \[e_v=H(k_i^v||\text{"out"}||j)\oplus v\]
   (Because we are xoring with a single bit, we just use the lowest bit of the output of \(H\) for generating the above \(e_v\).) Sort entries \(e\) in the table by the input pointers, placing entry ev in position \(p_i^v\). (There is no conflict, since \(p^1_i= p^0_i\oplus 1\).)

接下来是 \(P_1\) 和 \(P_2\) 的具体交互过程.

Parameters: Parties \(P_1\) and \(P_2\) with inputs \(x\in\{0, 1\}^n\) and \(y\in\{0, 1\}^n\) respectively. Boolean circuit \(\mathcal C\) implementing function \(\mathcal F\).

Protocol:

1. \(P_1\) plays the role of GC generator and runs the algorithm of Figure 3.1. \(P_1\) then sends the obtained GC \(\hat C\) (including the output decoding table) to \(P_2\).
2. \(P_1\) sends to \(P_2\) active wire labels for the wires on which \(P_1\) provides input.
3. For each wire \(w_i\) on which \(P_2\) provides input, \(P_1\) and \(P_2\) execute an Oblivious Transfer (OT) where \(P_1\) plays the role of the Sender, and \(P_2\) plays the role of the Receiver:
   1. \(P_1\)’s two input secrets are the two labels for the wire, and \(P_2\)’s choice-bit input is its input on that wire.
   2. Upon completion of the OT, \(P_2\) receives active wire label on the wire.
4. \(P_2\) evaluates received \(\hat C\) gate-by-gate, starting with the active labels on the input wires.
   1. For gate \(G_i\) with garbled table \(T = (e_{0,0},...e_{1,1})\) and active input labels \(w_a = (k_a, p_a), w_b = (k_b, p_b)\), \(P_2\) computes active output label \(w_c = (k_c, p_c)\): \[w_c = H(k_a || k_b || i)\oplus e_{p_a,p_b}\]
5. Obtaining output using output decoding tables. Once all gates of \(\hat C\) are evaluated, using “out” for the second key to decode the final output gates, \(P_2\) obtains the final output labels which are equal to the plaintext output of the computation. \(P_2\) sends the obtained output to \(P_1\), and they both output it.

GMW Protocol

Yao’s GC 只能支持只有两方的情况, 如果需要支持不少于三方, 则需要新的技术支持. 但是 GMW 协议 (Goldreich-Micali-Wigderson (GMW) Protocol) 天然支持这一点.

先讲只有两方的情况. 不失一般性地, 我们只考虑NOT, XOR 和 AND 三个门. 对于每根导线(即 wire, 表示某个门电路的输入或输出, 用 \(w_i\) 来表示), \(P_1\) 和 \(P_2\) 都将各自持有它的一个“部分”(share) \(s_i^1\) 和 \(s_i^2\), 这根导线的实际值为 \(s_i^1\oplus s_i^2\). \(P_1\) 和 \(P_2\) 最终只需要把最终输出导线的值展示给对方, 他们就都可以通过异或操作得到计算结果.

具体来说, \(P_1\) 对于自己的输入 \(x_1,...,x_n\), 生成一列随机数 \(r_1,...,r_n\), 然后将 \(r_1,...,r_n\) 发送给 \(P_2\) 作为 \(P_2\) 的 share, 而将自己的 share 设为 \(x_1\oplus r_1,...,x_n\oplus r_n\). 如此, 只需要将双方的 share 进行异或操作, 就可以得到真正的输入值 \(r_1\oplus (x_1\oplus r_1)=x_1\). \(P_2\) 也进行同样的操作.
然后双方各自计算逻辑电路 \(\mathcal C\). 当遇到 NOT 门时, 直接将自己所持有的 share 取反, 因为 \((\lnot s_i^1)\oplus(\lnot s_i^2)=\lnot(s_i^1\oplus s_i^2)\), 也就是说操作完成后双方 share 异或的结果确实等于输入实际值 NOT 的结果.
遇到 XOR 门时, 也是直接将自己持有的两个输入的 share 取异或, 因为 \((s_i^1\oplus s_j^1)\oplus(s_i^2\oplus s_j^2)=(s_i^1\oplus s_i^2)\oplus(s_j^1\oplus s_j^2)\).
遇到 AND 门时, 就需要双方进行交流了. \(P_1\) 生成一个随机数 \(r\in_R\{0,1\}\) 作为自己的 share, 然后枚举两根输入导线 \(P_2\) 那边的 share 的可能值, 计算出四种情况下输出导线的实际值, 利用 1-out-of-4 OT 将实际值与 \(r\) 的异或值发送给 \(P_2\).

A Pragmatic Introduction to Secure Multi-Party Computation Reading Notes

2 Defining Multi-Party Computation

Secret Sharing

Let \(D\) be the domain of secrets and \(D_1\) be the domain of shares. Let \(\text{Shr}:D\to D_1^n\) be a (possibly randomized) sharing algorithm, and \(\text{Rec} : D^k_1\to D\) be a reconstruction algorithm. A \((t, n)\)-secret sharing scheme is a pair of algorithms \((\text{Shr}, \text{Rec})\) that satisfies these two properties:

• Correctness. Let \((s_1, s_2,...,s_n) = \text{Shr}(s)\). Then, \(\text{Pr}[\forall k \geq t, \text{Rec}(s_{i_1},..., s_{i_k}) = s] = 1\).
• Perfect Privacy. Any set of shares of size less than \(t\) does not reveal anything about the secret in the information theoretic sense. More formally, for any two secrets \(a, b\in D\) and any possible vector of shares \(v=v_1, v_2, ..., v_k\) , such that \(k < t\),\(\text{Pr}[v = \text{Shr}(a)|_k ] = \text{Pr}[v = \text{Shr}(b)|_k ]\), where \(|_k\) denotes appropriate projection on a subspace of \(k\) elements.

Real-Ideal Paradigm

在 Ideal World 中，每一方都和一个可信方 \(\mathcal T\) 进行交流，他们将自己的输入 \(x_i\) 发送给 \(\mathcal T\)，\(\mathcal T\) 计算出 \(\mathcal F(x_1,...,x_n)\) 并将结果返回给每一个人。

在 Real World 中，每一方都有一个 \(\pi_i\)，根据 \(x_i\)、一个随机带、之前接收到的信息等来决定下一步给哪一方发送什么消息，或者终止并得到最终的输出。

如果攻击者在 Ideal World 和 Real World 中能做的事一样，称该协议 \(\pi\) 是安全的。

Semi-Honest Security

A semi-honest adversary is one who corrupts parties but follows the protocol as specified.

明天组会讲Circuit PSI，事先预习一下前置知识

参考资料：

【知乎专栏】隐私集合求交(Private Set Intersection)问题综述

PSI

隐私求交(Private Set Intersection, PSI)可能是被研究最多的具体的多方安全计算（Secure Multiparty Computation, MPC）协议。PSI本质上是一种特殊的多方安全计算协议：计算双方各自有一个集合，要求双方协作共同计算出两者集合的交集，计算过程中（除了交集部分）不泄露任何和各自集合相关的信息。

标准的PSI分为几大类：基于密钥交换（Diffie-Hellman key exchange based）、基于透明传输 (oblivious transfer based, OT-based)、基于透明键-值(oblivious key-value stores based, OKVS-based)、基于透明向量线性估值(Vector Oblivious Linear Evaluation, VOLE-based)、基于多项式操作(polynomial manipulation)、基于分支程序(Branching Program, BP)。

除此之外还有隐私求交集基数(Private Intersection Cardinality)、阈值隐私求交(Threshold Private Set Intersection)、电路隐私求交(Circuit-PSI)、模糊隐私求交(Fuzzy-PSI)等变体。

电路隐私求交(Circuit-PSI)

Circuit-PSI 的开篇之作：Private set intersection: Are garbled circuits better than custom protocols?

Yao’s Garbled Circuits

Proofs, Arguments, and Zero-Knowledge Reading Notes

11 Zero-Knowledge Proofs and Arguments

什么是“零知识”

(Informal definition of zero-knowledge). A proof or argument system with prescribed prover \(\mathcal{P}\) and prescribed verifier \(\mathcal{V}\) for a language \(\mathcal{L}\) is said to be zero-knowledge if for any probabilistic polynomial time verifier strategy \(\hat{\mathcal{V}}\), there exists a probabilistic polynomial time algorithm \(S\) (which can depend on \(\hat{\mathcal{V}}\)), called the simulator, such that for all \(x\in\mathcal{L}\), the distribution of the output \(S(x)\) of the simulator is “indistinguishable” from \(\text{View}_{\hat{\mathcal{V}}}(\mathcal{P}(x),\hat{\mathcal{V}}(x))\). Here, \(\text{View}_{\hat{\mathcal{V}}}(\mathcal{P}(x),\hat{\mathcal{V}}(x))\) denotes the distribution over transcripts generated by the interaction of prover strategy \(\mathcal{P}\) and verifier strategy \(\hat{\mathcal{V}}\) within the proof or argument system.

主要针对 prover，也就是说就算换一个 verifier 来，无论怎么做都无法从 prover 那里套出其他的信息。

• perfect zero knowledge: \(S(x)\) 和 \(\text{View}\) 产生的分布完全一样。
• statistical zero knowledge: 两者产生的分布只有可忽略的 “statistical distance”，即 \[\frac12\sum_{y}|\text{Pr}[D_1(x)=y]-\text{Pr}[D_2(x)=y]|\] 它等价于 \[\max_{\mathcal{A}}|\underset{y\leftarrow D_1}{\text{Pr}}[\mathcal{A}(y)=1]-\underset{y\leftarrow D_2}{\text{Pr}}[\mathcal{A}(y)=1]|\]
• computational zero-knowledge: 对于多项式时间算法 \(\mathcal A\) 无法区分两个分布。

statiscial zero knowledge 比较弱，尽管人们相信它能解决一些 BPP(Bounded-error Probalistic Polynomial-time) 以外的问题，但是并不认为它能解决 NPC 问题。（突然有个疑问，如果问题 \(A\) 能归约到问题 \(B\)，那么存在 \(B\) 的零知识证明能推出存在 \(A\) 的零知识证明吗？好像从来没有仔细思考过这个问题，也没在哪里看到过，也许书上有但我漏了？）

需要注意，一个诚实的 \(\mathcal{V}\) 的 view 和 simulator \(S(x)\) 无法区分，并不代表着这个问题是 NP 问题，这要求对于 \(x\in\mathcal{L},x'\notin\mathcal{L}\)，\(S(x)\) 和 \(S'(x)\) 无法区分。\(\mathcal{P}\) 可能知道关于陈述的证据 \(w\)，\(S\) 可以在不知道 \(w\) 的情况下生成一个 accepting transcipt。

\(S\) 可以为 \(x\notin\mathcal{L}\) 生成一个 accepting transcript，但是这并不违背 soundness，即使一个恶意的 prover 知道 \(x\notin\mathcal{L}\) 的 accepting transcript 分布，它也无法说服 verifier，因为证明的过程是交互的。（我有个想法，满足 zero-knowledge 是否意味着，通过 prover 的回复能高效地推导出 verifier 的 challenge，反过来却不行？）

statistical zero-knowledge proof with a polynomial time verifier 能处理的语言在复杂度集 \(\mathbf{AM}\cap\mathbf{coAM}\) 中。其中 \(\mathbf{AM}\) 指的是 Solvable in polynomial time by an Arthur–Merlin protocol，\(\mathbf{coAM}\) 指的是 \(\{L\,|\,\overline{L}\in\mathbf{AM}\}\)，前面提到过，一般认为 \(\mathbf{AM}\) 是等价于 \(\mathbf{NP}\) 的。

Proofs, Arguments, and Zero-Knowledge Reading Notes

8 MIPs and Succinct Arguments

Multi-prover interactive proofs (MIPs) 允许验证者 \(\mathcal V\) 与多个不被信任的证明者交互，并假设证明者之间无法交流从 \(\mathcal V\) 收到的 challenge。

MIP 定义

一个关于 \(\mathcal{L}\subseteq\{0,1\}^*\) 的 k-prover interactive proof protocol 涉及 \(k+1\) 方，\(1\) 个 PPT 验证者和 \(k\) 个证明者。交互过程产生一个 transcript \(t = (\mathcal{V}(r),\mathcal{P}_1,...,\mathcal{P}_k)(x)\)，其中 \(r\) 表示 \(\mathcal{V}\) 的内部随机性。验证者最后的输出为 \(\text{out}(\mathcal{V}, x,r,\mathcal{P}_1,...,\mathcal{P}_k)\)。

1. (Completeness) There exists a tuple of prover strategies \((\mathcal{P}_1,...,\mathcal{P}_k)\) such that for every \(x\in\mathcal{L}\): \[\text{Pr}[\text{out}(\mathcal{V}, x,r,\mathcal{P}_1,...,\mathcal{P}_k)=\text{accept}]\geq 1−\delta_c\]
2. (Soundness) For every \(x\notin\mathcal{L}\) and every tuple of prover strategies \((\mathcal{P}'_1,...,\mathcal{P}'_k)\), \[\text{Pr}[\text{out}(\mathcal{V},x,r,\mathcal{P}'_1,...,\mathcal{P}'_k) = \text{accept}]\leq\delta_s\]

如果 \(\delta_c,\delta_s\leq\frac13\)，称其为合法的。复杂度集 MIP 指的是拥有合法 k-prover IP 的语言 \(\mathcal{L}\) 的集合（对于某个 \(k=\text{poly}(n)\)）。

MIP 和 IP 的主要区别在于，MIP 是 non-adaptive 的，也就是说，在 IP 中证明者可以根据之前的 challenge 作出临时应对，但在 MIP 中就不行。从这一观点出发，我们可以证明 MIP 等价于 PPT oracle Turing Machine 能接受的 language。

设 \(\mathcal{L}\) 为一个 language，\(M\) 为一个 PPT oracle Turing Mahine，\(M^{\mathcal O}\) 表示 \(M\) 可以访问 oracle \(\mathcal O\)。如果对于任意 \(x\in\mathcal{L}\)，都存在一个 \(\mathcal O\) 使得 \(M^{\mathcal O}\) 以概率 \(1\) 接受 \(x\)；对于任意 \(x\notin\mathcal L\) 都存在一个 \(\mathcal O\) 使得 \(M^{\mathcal O}\) 至少以概率 \(2/3\) 拒绝 \(x\)，那么就存在关于 \(\mathcal L\) 的 2-prover MIP。

至于构造方法，简单地说，\(\mathcal{V}\) 可以把 \(\mathcal{P}_1\) 当做 \(\mathcal O\)，并模拟 \(M\)，如果 \(M\) 接受了 \(x\)，就从之前对 \(\mathcal{P}_1\) 的所有 challenge 中随机选取一个发送给 \(\mathcal{P}_2\)，如果和 \(\mathcal{P}_1\) 一致，那么就接受 \(x\)，重复这样的过程若干次。

Proofs, Arguments, and Zero-Knowledge Reading Notes

5 Fiat-Shamir 变换

Fiat-Shamir transformation 可以将任意 public-coin protocol \(\mathcal I\) 转换为一个 non-interactive, publicly verifiable protocol \(\mathcal Q\)。

The Random Oracle Model

随机函数 \(R:D\to\{0,1\}^{\kappa}\)，对于任意 \(x\in D\)，\(R\) 从 \(\{0,1\}^{\kappa}\) 中均匀随机选取它的值 \(R(x)\)。

ROM 假设证明者和验证者可以访问一个黑盒随机函数 \(R\)，对于一次访问 \(x\)，\(R(x)\) 将会独立地从 \(\{0,1\}^{\kappa}\) 随机均匀地选取一个数并返回，然后记录这个值，下次如果重复查询 \(R(x)\) 时返回相同的值。

实际中使用真正的 ROM 是不现实的，一般会使用一些具体的哈希函数（如 SHA-3 等）来代替。

The Fiat-Shamir Transformation

Security of the Transformation

Proofs, Arguments, and Zero-Knowledge Reading Notes

3 定义和技术准备工作

Interactive Proofs

给定一个函数 \(f:\{0,1\}^n\to\mathcal R\)，一个 k-message interactive proof system (IP) for \(f\) 包含了一个随机（probalilistic）验证算法 \(\mathcal{V}\) （running in time poly(\(n\))） 和一个确定（deterministic）证明算法 \(\mathcal{P}\)。给 \(\mathcal{P}\) 和 \(\mathcal{V}\) 一个共同的 \(x\in\{0,1\}^n\)。开始时，\(\mathcal{P}\) 给出一个 \(y\)，声明 \(f(x)=y\)，然后 \(\mathcal{P}\) 和 \(\mathcal{V}\) 交换一系列消息 \(m_1,m_2,...,m_k\)，双方交替发送消息（如果 IP 指定 \(\mathcal{V}\) 发送 \(m_1\)，那么 \(\mathcal{P}\) 发送 \(m_2\)，\(\mathcal{V}\) 发送 \(m_3\)，以此类推）。\(\mathcal{V}\) 和 \(\mathcal{P}\) 都根据之前交换的一系列消息来计算下一条消息。

整个消息序列 \(t=(m_1,m_2,...,m_k)\)，和 \(\mathcal{P}\) 声明的 \(y\) 一起，被称为 transcript。在协议的末尾，\(\mathcal{V}\) 需要输出 \(1\) 或者 \(0\)，表示他是否接受 \(f(x)=y\)。

用 \(\text{out}(\mathcal{V},x,r,\mathcal{P})\) 来表示 \(\mathcal{V}\) 的输出，其中 \(r\) 表示 \(\mathcal{V}\) 的内部随机性。所以 \(\text{out}\) 是一个确定函数。

An interactive proof system \((\mathcal{V},\mathcal{P})\) is said to have completeness error \(\delta_c\) and soundness error \(\delta_s\) if the following two properties hold.

• (Completeness) For every \(x\in\{0,1\}^n\), \[\text{Pr}_r[\text{out}(\mathcal{V},x,r,\mathcal{P})=1]\geq1-\delta_c\]
• (Soundness) For every \(x\in\{0,1\}^n\) and every deterministic prover strategy \(\mathcal{P}'\), if \(\mathcal{P}'\) sends a value \(y \neq f(x)\) at the start of the protocol, then \[\text{Pr}_r[\text{out}(\mathcal{V},x,r,\mathcal{P}')=1]\leq \delta_s\]

An interactive proof system is valid if \(\delta_c,\delta_s \leq 1/3\).

除了 \(\mathcal{P}\) 和 \(\mathcal{V}\) 的时间消耗，他们之间的空间消耗同样值得关注，如果他们交换了 \(k\) 条消息，那么称 \(\lceil\frac{k}{2}\rceil\) 为 round complexity。

对于任何 IP 满足 \(\delta_c\leq\frac13\)，都可以以一个多项式复杂度的增长为代价转换为 perfect completeness（\(\delta_c=0\)）。

\(\delta_s\leq\frac13\) 的 \(\frac13\) 只是按照习惯选取的，可以通过重复试验 \(O(k)\) 次将其降为 \(\delta_s^k\)。

Introduction to Modern Cryptography Reading Notes

13 Digital Signature Schemes

定义

A (digital) signature scheme consists of three probabilistic polynomial-time algorithms \((\text{Gen}, \text{Sign}, \text{Vrfy})\) such that:

1. The key-generation algorithm \(\text{Gen}\) takes as input a security parameter \(1^n\) and outputs a pair of keys \((pk, sk)\). These are called the public key and the private key, respectively. We assume that \(pk\) and \(sk\) each has length at least \(n\), and that \(n\) can be determined from \(pk\) or \(sk\).
2. The signing algorithm \(\text{Sign}\) takes as input a private key \(sk\) and a message \(m\) from some message space (that may depend on \(pk\)). It outputs a signature \(\sigma\), and we write this as \(\sigma\leftarrow \text{Sign}_{sk}(m)\).
3. The deterministic verification algorithm \(\text{Vrfy}\) takes as input a public key \(pk\), a message \(m\), and a signature \(\sigma\). It outputs a bit \(b\), with \(b = 1\) meaning valid and \(b = 0\) meaning invalid. We write this as \(b := \text{Vrfy}_{pk}(m, \sigma)\).

It is required that except with negligible probability over \((pk, sk)\) output by \(\text{Gen}(1^n)\), it holds that \(\text{Vrfy}_{pk}(m, \text{Sign}_{sk}(m)) = 1\) for every (legal) message \(m\).

If there is a function \(\ell\) such that for every \((pk, sk)\) output by \(\text{Gen}(1^n)\) the message space is \(\{0, 1\}^{\ell(n)}\), then we say that \((\text{Gen}, \text{Sign}, \text{Vrfy})\) is a signature scheme for messages of length \(\ell(n)\).

The signature experiment \(\text{Sig-forge}_{\mathcal{A},\Pi(n)}\):

1. \(\text{Gen}(1^n)\) is run to obtain keys \((pk, sk)\).
2. Adversary \(\mathcal{A}\) is given \(pk\) and access to an oracle \(\text{Sign}_{sk}(\cdot)\). The adversary then outputs \((m, \sigma)\). Let \(\mathcal Q\) denote the set of all queries that \(\mathcal{A}\) asked its oracle.
3. \(\mathcal{A}\) succeeds if and only if (1) \(\text{Vrfy}_{pk}(m, \sigma) = 1\) and (2) \(m \notin \mathcal Q\). In this case the output of the experiment is defined to be \(1\).

A signature scheme \(\Pi=(\text{Gen},\text{Sign},\text{Vrfy})\) is existentially unforgeable under an adaptive chosen-message attack, or just secure, if for all probabilistic polynomial-time adversaries \(\mathcal{A}\), there is a negligible function \(\text{negl}\) such that: \[\text{Pr}[\text{Sig-forge}_{\mathcal{A},\Pi}(n) = 1]\leq\text{negl}(n)\]

与 MAC 同理，可以定义强安全。

Hash-and-Sign

对于任意长度的消息，可以先对它用哈希映射到一个固定长度的串，然后对其进行数字签证。（和 Hash-and-MAC 差不多）