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_i^{1-b}$.
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_a^0=(k_a^0,p_a^0),w_a^1=(k_a^1,p_a^1),w_b^0=(k_b^0,p_b^0),w_b^1=(k_b^1,p_b^1)$, and the output labels are $w_c^0=(k_c^0,p_c^0),w_c^1=(k_c^1,p_c^1)$.
      
   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_a^{v_a}||k_b^{v_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 $⟨p_a^{v_a},p_b^{v_b}⟩$.
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_i^0),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_i^1=p_i^0\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 取反, 因为 $(\mathrm{\neg }{s}_i^1)\oplus (\mathrm{\neg }{s}_i^2)=\mathrm{\neg }(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_1^k\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}[\mathrm{\forall }k\ge 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”，即 $$\frac{1}{2}\sum _y|\text{Pr}[D_1(x)=y]-\text{Pr}[D_2(x)=y]|$$ 它等价于 $$\underset{\mathcal{A}}{max}|\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^{\prime }\notin \mathcal{L}$，$S(x)$ 和 $S^{\prime }(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|\bar{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{\}}^{\ast }$ 的 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}]\ge 1-{\delta }_c$$
2. (Soundness) For every $x\notin \mathcal{L}$ and every tuple of prover strategies $({\mathcal{P}}_1^{\prime },...,{\mathcal{P}}_k^{\prime })$, $$\text{Pr}[\text{out}(\mathcal{V},x,r,{\mathcal{P}}_1^{\prime },...,{\mathcal{P}}_k^{\prime })=\text{accept}]\le {\delta }_s$$

如果 ${\delta }_c,{\delta }_s\le \frac{1}{3}$，称其为合法的。复杂度集 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]\ge 1-{\delta }_c$$
• (Soundness) For every $x\in \{0,1{\}}^n$ and every deterministic prover strategy ${\mathcal{P}}^{\prime }$, if ${\mathcal{P}}^{\prime }$ sends a value $y\ne f(x)$ at the start of the protocol, then $${\text{Pr}}_r[\text{out}(\mathcal{V},x,r,{\mathcal{P}}^{\prime })=1]\le {\delta }_s$$

An interactive proof system is valid if ${\delta }_c,{\delta }_s\le 1/3$.

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

对于任何 IP 满足 ${\delta }_c\le \frac{1}{3}$，都可以以一个多项式复杂度的增长为代价转换为 perfect completeness（${\delta }_c=0$）。

${\delta }_s\le \frac{1}{3}$ 的 $\frac{1}{3}$ 只是按照习惯选取的，可以通过重复试验 $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},\mathrm{\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 $\mathrm{\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},\mathrm{\Pi }}(n)=1]\le \text{negl}(n)$$

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

Hash-and-Sign

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