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

Introduction to Modern Cryptography Reading Notes

6 Hash Functions and Applications

哈希函数的定义

A hash function (with output length \(\ell(n)\)) is a pair of probabilistic polynomial-time algorithms \((\text{Gen}, H)\) satisfying the following:

• \(\text{Gen}\) is a probabilistic algorithm that takes as input a security parameter \(1^n\) and outputs a key \(s\). We assume that \(n\) is implicit in \(s\).
• \(H\) is a deterministic algorithm that takes as input a key \(s\) and a string \(x \in \{0, 1\}^∗\) and outputs a string \(H^s(x) \in \{0, 1\}^{\ell(n)}\) (where \(n\) is the value of the security parameter implicit in \(s\)).

If \(H^s\) is defined only for inputs \(x\) of length \(\ell'(n) > \ell(n)\), then we say that \((\text{Gen}, H)\) is a fixed-length hash function for inputs of length \(\ell'(n)\). In this case, we also call \(H\) a compression function.

在这里，攻击者往往会知道 \(s\) 的值，因此 \(s\) 放在 \(H\) 的上标。

The collision-finding experiment \(\text{Hash-coll}_{\mathcal{A},\mathcal{H}(n)}\) \((\mathcal{H}=(\text{Gen},H))\):

1. A key \(s\) is generated by running \(\text{Gen}(1^n)\).
2. The adversary \(\mathcal{A}\) is given \(s\), and outputs \(x, x'\) . (If \(H\) is a fixed-length hash function for inputs of length \(\ell'(n)\), then we require \(x, x' \in \{0, 1\}^{\ell'(n)}\).)
3. The output of the experiment is defined to be \(1\) if and only if \(x = x'\) and \(H^s(x) = H^s(x')\). In such a case we say that \(\mathcal{A}\) has found a collision.

如果 \(\text{Pr}[\text{Hash-coll}_{\mathcal{A},\mathcal{H}(n)}=1]\leq\text{negl}(n)\)，则称 \(\mathcal{H}\) 是collision resistant的。

下面给出两个其他关于哈希安全的概念。

• Second-preimage resistance 给出 \(s\) 和一个均匀分布的 \(x\)，一个PPT的 \(\mathcal{A}\) 几乎无法找到 \(x'\) 使得 \(x\neq x',H(x)=H(x')\)
• Preimage resistance 给出 \(s\) 和 \(y=H^s(x)\) 对于一个均匀分布的 \(x\)，一个PPT的 \(\mathcal{A}\) 几乎无法找到 \(x'\) 使得 \(H(x)=H(x')\) (\(x'\) 可以等于 \(x\))