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

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 差不多）

Introduction to Modern Cryptography Reading Notes

12 Public-Key Encryption

定义

A public-key encryption scheme is a triple of probabilistic polynomial-time algorithms \((\text{Gen}, \text{Enc}, \text{Dec})\) such that:

1. The key-generation algorithm \(\text{Gen}\) takes as input the security parameter \(1^n\) and outputs a pair of keys \((pk, sk)\). We refer to the first of these as the public key and the second as the private key. We assume for convenience that \(pk\) and \(sk\) each has length at least \(n\), and that \(n\) can be determined from \(pk\), \(sk\). The public key \(pk\) defines a message space \(\mathcal{M}_{pk}\).
2. The encryption algorithm \(\text{Enc}\) takes as input a public key \(pk\) and message \(m\in \mathcal{M}_{pk}\), and outputs a ciphertext \(c\); we denote this by \(c \leftarrow \text{Enc}_{pk}(m)\). (Looking ahead, \(\text{Enc}\) will need to be probabilistic in order to achieve meaningful security.)
3. The deterministic decryption algorithm \(\text{Dec}\) takes as input a private key \(sk\) and a ciphertext \(c\), and outputs a message \(m\) or a special symbol \(\perp\) denoting failure. We write this as \(m:=\text{Dec}_{sk}(c)\).

It is required that, except with negligible probability over the randomness of \(\text{Gen}\) and \(\text{Enc}\), we have \(\text{Dec}_{sk}(\text{Enc}_{pk}(m))=m\) for any message \(m\in \mathcal{M}_{pk}\).

下面定义与之对应的安全测试

The eavesdropping indistinguishability experiment \(\text{PubK}^{\text{eav}}_{\mathcal{A},\Pi(n)}\):

1. \(\text{Gen}(1^n)\) is run to obtain keys \((pk, sk)\).
2. Adversary \(\mathcal{A}\) is given \(pk\), and outputs a pair of equal-length messages \(m_0, m_1\in \mathcal{M}_{pk}\).
3. A uniform bit \(b\in \{0, 1\}\) is chosen, and then a ciphertext \(c \leftarrow \text{Enc}_{pk}(m_b)\) is computed and given to \(\mathcal{A}\). We call \(c\) the challenge ciphertext.
4. \(\mathcal{A}\) outputs a bit \(b'\). The output of the experiment is \(1\) if \(b' = b\), and \(0\) otherwise. If \(b' = b\) we say that \(\mathcal{A}\) succeeds.

还有安全定义

A public-key encryption scheme \(\Pi=(\text{Gen}, \text{Enc}, \text{Dec})\) has indistinguishable encryptions in the presence of an eavesdropper if for all probabilistic polynomial-time adversaries \(\mathcal{A}\) there is a negligible function \(\text{negl}\) such that \[\text{Pr}[\text{PubK}^{\text{eav}}_{\mathcal{A},\Pi(n)}=1]\leq \frac12+\text{negl}(n)\]

它是等价于于 CPA-secure 的。

接下来考虑到我们需要使用一个公钥进行多次加密

Introduction to Modern Cryptography Reading Notes

11 Key Management and the Public-Key Revolution

密钥分发和密钥管理

密钥加密主要会遇到三个问题

• key distribution
• storing and managing large numbers of secret keys
• inapplicability of private-key cryptography to open systems

密钥分发中心 KDC

密钥分发中心通常是一个可信的第三方。一种做法是，当新加入一个成员时，分发他与其他所有成员之间的密钥。

online 可能是更好的做法，当 \(A\) 需要和 \(B\) 通信时，向 KDC 发送请求，KDC 像 \(A\) 和 \(B\) 发送一个 session key（分别使用 \(k_A\) 和 \(k_B\) 加密），然后 \(A\) 和 \(B\) 通过 session key 交流。

Needham–Schroeder protocol \(A\) 发出请求后，KDC 把 \(\text{Enc}_{k_A}(k_{session})\) 和 \(\text{Enc}_{k_B}(k_{session})\) 发送给 \(A\)，\(A\) 将后者发送给 \(B\)。一般将 \(\text{Enc}_{k_B}(k_{session})\) 称为 ticket。

密钥交换和 Diffie-Hellman Protocol

Introduction to Modern Cryptography Reading Notes

10 *Algorithms for Factoring and Computing Discrete Logarithms

(skip)

Introduction to Modern Cryptography Reading Notes

9 Number Theory and Cryptographic Hardness Assumptions

关于群论的部分全部跳过。

离散对数问题和 CDH/DDH

用 \(\mathcal G\) 表示一个通用的、多项式时间的群生成算法，输入 \(1^n\)，输出一个阶为 \(q\)（其中 \(||q||=n\)） 的循环群 \(\mathbb G\) 的描述（description）和它的一个生成元 \(g\)。它将 \(\mathbb G\) 的每个元素都表示为一个比特串，并且要求存在多项式时间算法，能够验证一个任意比特串是否对应着 \(\mathbb G\) 中的一个元素，能执行群运算（我的理解是，输入两个对应着 \(g_1,g_2\in\mathbb G\) 的比特串，能计算 \(g_1\circ g_2\) 对应的比特串）。虽然所有阶为 \(q\) 的循环群都是同构的，但是不同的描述可能会导致不同的计算复杂度。

对于 \(g\in\mathbb G\)，存在一个唯一的 \(x\in\mathbb{Z}_q\) 使得 \(g^x=h\)，称 \(x\) 是 \(h\) 关于 \(g\) 的离散对数（discrete logarithm）。注意如果 \(g^{x'}=h\)，那么 \(\log_gh=[x'\mod q]\)。

我们和之前一样用测试的方式定义离散对数问题（discrete-logarithm problem）

The discrete-logarithm experiment \(\text{DLog}_{\mathcal{A},\mathcal G(n)}\):

1. Run \(\mathcal G(1^n)\) to obtain \((\mathbb G, q, g)\), where \(\mathbb G\) is a cyclic group of order \(q\) (with \(|q|=n\)), and \(g\) is a generator of \(\mathbb G\).
2. Choose a uniform \(h\in\mathbb G\).
3. \(\mathcal{A}\) is given \(\mathbb G, q, g, h\), and outputs \(x\in\mathbb{Z}_q\).
4. The output of the experiment is defined to be \(1\) if \(g^x=h\), and \(0\) otherwise.

根据上下文，书中的 \(\mathcal G\) 是一个随机算法。如果 \(\mathcal G\) 是确定性的，或者 \(\mathcal G\) 的随机性被 \(\mathcal{A}\) 所知，会发生什么事，我还没有想清楚。

如果对于任意的 PPT 算法 \(\mathcal{A}\)，都有 \(\text{Pr}[\text{DLog}_{\mathcal{A},\mathcal G(n)}=1]\leq\text{negl}(n)\)，则称离散对数问题是难的（relative to \(\mathcal G\)）。而离散对数假设就是存在一个 \(\mathcal G\) 使得离散对数问题是难的。

Introduction to Modern Cryptography Reading Notes

8 *Theoretical Constructions of Symmetric-Key Primitives

这章标了*，先跳过（

Introduction to Modern Cryptography Reading Notes

7 Practical Constructions of Symmetric-Key Primitives

流密码

Linear-Feedback Shift Registers(LFSR)

\(y_i=s_i^{(0)},i=0,...,n-1\)

\(y_i=\oplus_{j=0}^{n-1}c_jy_{i-n+j},i>n-1\)

\(n\) 称为 LFSR 的度数。

知道 \(2n\) 个输出后，可以得到 \(n\) 个方程（如果是max length的，这 \(n\) 个方程是独立的），然后可以解出所有系数 \(c\) 的值。

可以通过引入一些非线性函数（比如 AND 和 OR）来避免这种攻击，称为 FSR，比如将状态转移方程替换为一个非线性函数，或者将输出值替换为当前状态的一个非线性函数，或者使用多个 LFSR，将它们的输出的一个非线性函数作为输出。

Trivium