-
Notifications
You must be signed in to change notification settings - Fork 1
/
smpc.tex
174 lines (144 loc) · 12.4 KB
/
smpc.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
\section{Secure Multi-party Computation (SMPC)}\label{s:smpc}
Secure multi-party computation (SMPC)\footnote{Both SMPC and MPC abbreviations are used for secure multi-party computation; in this thesis we use them interchangeably.} or Secure Function Evaluation (SFE) (in the two-party setting) is a field of cryptography aiming to create methods that enable distinct parties, to jointly compute a function over their private inputs.
Only the outcome of that function is made public and the parties don’t learn anything more than their own input except whatever can be learned from the output of the function.
Secure multi-party computation was introduced in 1982 by Andrew Yao.
Its first form was that of secure two-party computation (2PC) with the so-called Millionaire's Problem \cite{yao1982protocols}.
The problem states that there are two millionaires wishing to know who is richer.
However, they should not find out any additional information about each other’s wealth.
In the general case we have N parties $P_1, P_2, \dots, P_N$ with private inputs $x_1, x_2, \dots, x_N$ respectively.
The goal is to compute a function $f(x_1, x_2, \dots, x_N)$ and learn nothing more than what they would have if a separate trusted party had collected their inputs, computed function $f$ for them, and the return the result to all parties.
There are two important requirements on any protocol for secure computation, namely \textit{privacy} and \textit{correctness} \cite{lindell2009secure}.
The privacy requirement suggests that nothing but what is absolutely essential should be learned.
More specifically, all parties should learn nothing more but the computation output.
The correctness requirement states that every party should receive the correct computation output, that is an adversary should not be able to cause the result of the computation to be different than the outcome of the function the parties agreed to compute.
Plenty of tasks can be modeled using SMPC.
The tasks that can be modeled using SMPC include simple ones such as coin tossing, as well as far more complex such as electronic voting, electronic auctions, anonymous transactions, anonymous chatting and private information retrieval systems.
Take electronic voting as an example.
The privacy requirement ensures that no party can learn the individual votes of other parties, while still learning the election outcome.
The correctness requirement ensures that no party can affect the outcome with means other than casting their one individual vote.
Similarly, in the electronic auction example, the privacy requirement ensures that no party learns the bids of other parties while still learning the winning bid. The correctness requirement ensures that no party can bias the auction outcome and that in fact the winning party has places the highest bid.
\subsection{Millionaire's Problem}\label{ss:millionaire}
The first problem that was modeled using SMPC is the Millionaire's Problem introduced by Yao, and it is a basic building block for such secure computations.
Here the two parties $P_1$, $P_2$ are the two millionaires.
Their private inputs are each one’s wealth $x_1$ and $x_2$ respectively.
The function which they wish to jointly compute can be formulated as
\begin{equation}
f(x_1, x_2)=\begin{cases}
x_1, & \text{if $x_1 > x_2$}.\\
x_2, & \text{otherwise}.
\end{cases}
\end{equation}
A lot of solutions have been proposed to the Millionaire's problem starting with the one from Yao himself \cite{yao1982protocols} as well as multiple others including \cite{ioannidis2003efficient, lin2005efficient}.
\subsection{Oblivious Transfer}\label{ss:oblivious-transfer}
Another example for the two-party case and a basic building block of SMPC systems is Oblivious Transfer (OT) firstly introduced in 1981 by Michael O. Rabin \cite{rabin2005exchange}.
Its simple flavor is 1-2 oblivious transfer or ``1 out of 2 oblivious transfer".
In the 1-2 oblivious transfer case we have two parties, the sender $S$ and the receiver $R$.
The sender has two messages, $m_0$ and $m_1$, and the receiver has a bit $b$.
The receiver wishes to learn $m_b$, without learning anything about $m_{1-b}$ and without the sender learning $b$.
A solution for the above problem has been implemented using the protocol of Even, Goldreich, and Lempel in \cite{even1985randomized}.
Below we describe the otherwise generic protocol using RSA as en encryption scheme.
\begin{itemize}
\item $S$ (who holds messages $m_0$ and $m_1$) generates an RSA key pair. Recall from section \ref{ss:rsa} that the public key is $(n,e)$ and the private key is $d$.
\item $S$ randomly selects two values $x_0, x_1$.
\item $S$ sends $x_0, x_1, N, e$ to $R$.
\item $R$ picks $b \in \{0,1\}$
\item $R$ randomly selects a value $k$ and computes $v = x_b + k^e \pmod{n}$.
\item $R$ sends $v$ to $S$.
\item $S$ computes $k_0 = (v-x_0)^d \pmod{n}$ and $k_1 = (v-x_1)^d \pmod{n}$. One of $k_0, k_1$ will be equal to $k$ randomly selected be $R$.
\item $S$ sends to $m_0' = m_0 + k_0$ and $m_1' = m_1 + k_1$ to $R$.
\item $R$ can compute exactly one of the messages, as $m_b = m_b' - k$.
\end{itemize}
\subsection{Garbled Circuits}\label{ss:garbled-circuits}
There are also generic constructions for building SMPC systems.
Generic protocols implement secure computation for any probabilistic polynomial time function.
One of the most commonly known such generic protocol is Garbled (or Encrypted) Circuits (GC).
The most simple version of SMPC using Garbled Circuits can be found in the two-party case.
The first protocol for such computations was introduced by Yao in \cite{yao1986generate}.
Assume that we have two parties, Alice and Bob, with private inputs $x$ and $y$, respectively.
They wish to compute function $f$ over their private inputs, and nothing more than $f(x,y)$ should be learned.
The GC protocol works by expressing $f$ as an combinatorial circuit.
The circuit contains logical gates that implement any function $g : \{0,1\} \times \{0,1\} \rightarrow \{0,1\}$.
These include for instance simple \texttt{AND, OR, XOR} and \texttt{NOT} gates.
This circuit takes as inputs the bitwise representation of $x$ and $y$ and has output the bitwise representation of the value $f(x,y)$.
The protocol is based on evaluating an encrypted version of this circuit.
A simple description of Yao's protocol can be seen below. A complete description as well as security proof of this protocol can be found in \cite{lindell2009proof}.
Let's assume without loss of generality that Alice is the so called \textit{garbled circuit generator}, or \textit{garbler}, and Bob the \textit{evaluator}. The circuit is known to both parties.
\subsubsection{Circuit Encoding}\label{sss:circuit-encoding}
\begin{itemize}
\item Alice ``hardwires'' her input into the circuit. Thus the circuit now computes $f(x, \cdot)$.
\item Alice assigns to each wire $i$ of the circuit two random string values $(W_i^0, W_i^1)$ which are called \textit{labels} that correspond to the Boolean values $0 /$ \texttt{false} and $1 /$ \texttt{true} respectively. These labels should be of adequate length (usually 128 bits) as they will be used as symmetric keys in an encryption scheme.
\item For each gate $g$ in the circuit Alice prepares the truth table of $g$. In that truth table the values $0,1$ are replaced with the corresponding labels that were generated in the previous step. The output column is then encrypted \footnote{The notation $E_{K}(M)$ means an encryption of the value $M$ with key $K$.} using as keys the labels from the two input columns.
For example the transformation of the truth table of an \texttt{AND} gate with input wires $A,B$ and output wire $C$ can be seen below.
\begin{minipage}{0.2\textwidth}
\begin{center}
\begin{tabular}{ c c | c }
$A$ & $B$ & $C$ \\
\hline
$0$ & $0$ & $0$ \\
$0$ & $1$ & $0$ \\
$1$ & $0$ & $0$ \\
$1$ & $1$ & $1$ \\
\end{tabular}
\end{center}
\end{minipage}
$\xrightarrow[]{\text{becomes}}$
\begin{minipage}{0.2\textwidth}
\begin{center}
\begin{tabular}{ c c | c }
$A$ & $B$ & $C$ \\
\hline
$W_A^0$ & $W_B^0$ & $W_C^0$ \\
$W_A^0$ & $W_B^1$ & $W_C^0$ \\
$W_A^1$ & $W_B^0$ & $W_C^0$ \\
$W_A^1$ & $W_B^1$ & $W_C^1$ \\
\end{tabular}
\end{center}
\end{minipage}
$\xrightarrow[]{\text{becomes}}$
\begin{minipage}{0.2\textwidth}
\begin{center}
\begin{tabular}{ c c | c }
$A$ & $B$ & $C$ \\
\hline
$W_A^0$ & $W_B^0$ & $E_{W_A^0}(E_{W_B^0}(W_C^0))$ \\
$W_A^0$ & $W_B^1$ & $E_{W_A^0}(E_{W_B^1}(W_C^0))$ \\
$W_A^1$ & $W_B^0$ & $E_{W_A^1}(E_{W_B^0}(W_C^0))$ \\
$W_A^1$ & $W_B^1$ & $E_{W_A^1}(E_{W_B^1}(W_C^1))$ \\
\end{tabular}
\end{center}
\end{minipage}
\item As a final step Alice generates a random permutation of the truth table's rows, and the result is a \textit{garbled} table.
\end{itemize}
\subsubsection{Data Transfer}\label{sss:data-transfer}
\begin{itemize}
\item Alice sends the garbled truth table for every gate $g$ of the circuit to Bob.
\item Alice also sends the randomly generated labels corresponding to her input.
For example if Alice's input $a$ is represented by the bits $a_4a_3a_2a_1a_0 = 01101$ then she will send the labels $W_{a_4}^0$, $W_{a_3}^1$, $W_{a_2}^1$, $W_{a_1}^0$, $W_{a_0}^1$ to Bob.
\item Bob also needs the labels corresponding to his input bits. For example if Bob's input $b$ is represented by the bits $b_4b_3b_2b_1b_0 = 10100$ then he will need the labels $W_{b_4}^1$, $W_{b_3}^0$, $W_{b_2}^1$, $W_{b_1}^0$, $W_{b_0}^0$
To obtain these labels, Alice and Bob run an 1 out of 2 oblivious transfer protocol, for each bit (each input wire) of Bob's input $b$.
Using this 1-2 OT protocol Bob learns only the labels corresponding to his input bits, and Alice learns nothing about Bob's input.
If bob wants to obtain the label for input bit $b_4 = 1$, he will ask Alice between $W_{b_4}^0$ and $W_{b_4}^1$.
Bob will learn only $W_{b_4}^1$ and not $W_{b_4}^0$, while Alice will not learn the value of $b_4$.
\end{itemize}
\subsubsection{Circuit Evaluation}\label{sss:circuit-evaluation}
\begin{itemize}
\item Bob now has the garbled truth tables for each gate of the circuit as well as all input labels. Having one garbled value\myslash label per input wire and the truth table, Bob will try to decrypt every value in the output column of the table, but will succeed only once.
The decryption will succeed only in the row for which Bob has the input labels so he can use them as keys in the decryption.
The decryption result will be the output label of that gate (the garbled version of the gate's output value).
This label will be used as an input for the next gate in the combinatorial circuit.
\item Bob repeats the process for each gate $g$ of the circuit, until he reaches to the output gate(s) and acquires the output label(s).
\end{itemize}
\subsubsection{Output Revealing}\label{ss:output-revealing}
\begin{itemize}
\item Alice knows The Boolean value corresponding to the output label(s), so Bob and Alice communicate in order for them to learn the computation result.
\item Either Alice will share her information about the original values of the output label(s) with Bob, or Bob will share the output to Alice and she could respond accordingly so that one or both of them learn the output.
\end{itemize}
\subsubsection{Overhead}\label{ss:overhead}
This protocol inevitably inserts a notable overhead. An overview of the most substantial factors as described in \cite{lindell2009secure} can be found below.
\begin{itemize}
\item Alice and Bob involve in a 1 out of 2 oblivious transfer protocol for each input wire related with Bob's input. These oblivious transfers can dominate the computation overhead -- at least for relatively small circuits -- since they require modular exponentiations.
\item Alice sends to Bob a garbled truth table for every gate $g$ of the circuit. Thereby, this operation's cost is proportional to the circuit size.
\item Bob decrypts a constant number of encrypted values for each gate $g$ of the circuit. This is also linear with respect to the size of the circuit.
\end{itemize}
Multiple attempts have been made to improve the performance of Yao's protocol. Many optimizations have been introduced like the ones found in \cite{beaver1990round, naor1999privacy, kolesnikov2008improved, bellare2013efficient, zahur2015two}.
Another generic protocol for Secure multi\hyp party computation can be constructed using \textit{Secret Sharing}, a technique which we will describe in section \ref{s:secret-sharing}.