Techniques for Efficient Secure
Computation Based on Yao’s Protocol
Yehuda Lindell
Bar-Ilan University, Israel

PKC 2013

Yehuda Lindell

Techniques for Efficient Secure Computation

28/2/2013

1 / 39Secure Computation – BackgroundA set of parties P1 , . . . , Pm with private inputs x1 , . . . , xm wish tocompute a joint function f of their inputs while preserving secure
properties such as:
I Privacy: nothing but the output f (x1 , . . . , xm ) is revealed
I Correctness: the correct output is obtained
I Independence of inputs: no party can choose its input as afunction of another party’s input

Yehuda Lindell

Techniques for Efficient Secure Computation

28/2/2013

2 / 39Secure Computation – Background

In an election:
I Privacy means that individual votes are not revealed
I Correctness means that the candidate with the majority vote

wins
I Independence of inputs means that you can’t vote as afunction of the outcome

Yehuda Lindell

Techniques for Efficient Secure Computation

28/2/20133 / 39Secure Computation – Background
Security must hold in the presence of adversarial behavior:
I Semi-honest: follows the protocol description but attempts tolearn more than allowed
I

Models inadvertent leakage but otherwise gives a weak
guarantee

Yehuda Lindell

Techniques for Efficient Secure Computation

28/2/20134 / 39Secure Computation – Background
Security must hold in the presence of adversarial behavior:
I Malicious: follows any arbitrary attack strategy
I

Provides a very strong guarantee, but is hard to achieve withrespect to efficiency

Security is formalized by comparing the output of a secure protocol to an ideal
world where an incorruptible trusted party computes the function for the parties
Yehuda Lindell

Techniques for Efficient Secure Computation

28/2/2013

5 / 39Secure Computation – Feasibility
Despite its stringent requirements, it was shown that essentiallyany function can be securely computed:
I In the presence of semi-honest adversaries [Yao86,GMW87]
I In the presence of malicious adversaries [GMW87]
I With perfect security where a 2/3 honest majority is

guaranteed [BGW88]
Since the 1980s, the feasibility of secure computation has beenstudied heavily:
I Assumptions
I Stronger adversaries (e.g., adaptive corruptions)
I Composition
I And much much more...

Yehuda Lindell

Techniques for Efficient Secure Computation

28/2/20136 / 39Secure Computation – Theory or Practice?
I Due to its broad applicability, secure computation has been afoundational theoretical topic of study since the mid 1980s
I

A rich and beautiful theory has been developed

I Recently, interest has grown with respect to the practicalityof secure computation
I

Governments, security organizations, industry,...

Yehuda Lindell

Techniques for Efficient Secure Computation

28/2/20137 / 39Secure Computation in Practice?
In the last 5 years there has been incredible progress on making
secure computation practical
I Today we can run semi-honest secure computation forproblems like secure AES in tens of milliseconds
I

We can run huge computations (on circuits of over a billion
gates) in minutes

I We have protocols for malicious adversaries that give amazing

amortized complexity
I Every year there are new significant breakthroughs

This is very surprising (and exciting): we now know that securecomputation can be practical for a reasonably wide range ofproblems
I Ten years ago, no one dreamed that this would be possible

Yehuda Lindell

Techniques for Efficient Secure Computation

28/2/20138 / 39Efficient Secure Computation – Semi-Honest Adversaries
From 2004 to 2013

I Yao’s protocol from 1986 has a constant number of rounds

and uses a few symmetric encryptions per gate
I

For many years, it was assumed that any protocol that is basedon a circuit for computing the function cannot be practical

I In 2004, the first implementation of a general securecomputation protocol was carried out
Fairplay – an implementation of Yao’s protocol for semi-honest
adversaries
I It was surprising to many that a circuit-based protocol could
even run
I The billionaires’ problem on 32-bit integers took between 1.25
seconds (LAN) and 4.01 seconds (WAN)
I Median on ten 16-bit numbers (circuit of size 4383 gates) took
between 7.09 and 16.63 seconds
I

Yehuda Lindell

Techniques for Efficient Secure Computation

28/2/2013

9 / 39Efficient Secure Computation – Semi-Honest Adversaries
From 2004 to 2013

I In 2011, an implementation of Yao for semi-honest adversaries

was carried out, using the state-of-the-art algorithmic
improvements, and systems optimizations
Secure AES computation (with 9,280 non-XOR gates) took
just 0.2 seconds overall (after an additional 0.6 seconds ofpreprocessing that can be used for many executions)
I In 2013, we can do even better
I

Yehuda Lindell

Techniques for Efficient Secure Computation

28/2/201310 / 39

Secure Computation – Malicious Adversaries
From 2004 to 2013

I In 2004, there were no efficient protocols whatsoever (theonly way to achieve this level of security was via generalzero-knowledge proofs for N P)
There were protocols that need exponentiations per gate; e.g.,[SchoenmakersTuyls2004]
I These protocols can be efficient for small circuits but do notscale wellI

I In 2013, we have a number of efficient protocols[NO09,IPS09,DO10,LOP11,BDOZ11,NNOS12,DPSZ12]
One important and influential approach is based on Yao’s
garbled circuits [Y86,LP07,LP11,sS11]
I This approach appears to still give the lowest latency in amodel with no preprocessing
I In 2012, an implementation of secure AES computation took
< 30 seconds on 4-cores, and about 8 seconds on 16-cores
I

Yehuda Lindell

Techniques for Efficient Secure Computation

28/2/201311 / 39

Secure Computation in PracticeSecure AES Computation

The problem of authentication and one-time passwords:
I Users have devices that compute a PRF of the current timeetc. to generate one-time passwords
I

The cryptographic keys for one-time password generation are
stored at a server

I A server breach means that all devices must be replaced (verycostly and problematic, and so is avoided)
I The danger can be mitigated using secure computation
I
I

Share the key between two servers
In order to verify a one-time password, securely compute AES(without revealing anything about the key), and then verify

I The same method can be used to verify “bank transaction

signing”

Yehuda Lindell

Techniques for Efficient Secure Computation

28/2/201312 / 39

Secure Computation in PracticeSecure AES Computation

Yehuda Lindell

Techniques for Efficient Secure Computation

28/2/201313 / 39

General versus Specific Protocols
I A general protocol can be used to compute any functionality(based on the circuit or some other general representation)
I For many years it was assumed that general protocols cannot
compete with specific protocols
I In some cases, this may be true, but in many cases general
protocols are the best we knowI

And they are good!

I Efficient general protocols have more applicability, and theysave us having to guess what people want to computeI

For years we talked about elections and auctions, but it appears
that one-time password computation is of much more interest

Yehuda Lindell

Techniques for Efficient Secure Computation

28/2/201314 / 39This Talk
Efficient Secure Computation Based on Yao’s Protocol

I We will briefly review Yao’s basic protocol
I We briefly mention the major techniques for improving

efficiency in the semi-honest settings
I We will focus on how to deal with malicious adversaries

Understanding the problem and difficulty
The cut-and-choose technique and subtleties
I An optimization to reduce bandwidth
I New developments
I
I

Yehuda Lindell

Techniques for Efficient Secure Computation

28/2/201315 / 39

Yao’s Garbled Circuits

A garbling of a circuit C is an “encryption” of the circuit with thefollowing properties
I Two secret keys are associated with each input wire; one for

the 0-bit and one for the 1-bit
I Given a single key for each input wire, it is possible tocompute the associated output and nothing else. That is:Given the keys associated with bits x1 , . . . , xn ∈ {0, 1}, it ispossible to compute f (x1 , . . . , xn )I Given the keys associated with x1 , . . . , xn ∈ {0, 1} it is notpossible to learn anything beyond f (x1 , . . . , xn )I

I How can garbled circuits be constructed?

Yehuda Lindell

Techniques for Efficient Secure Computation

28/2/201316 / 39

A Garbled Gate
Input wires i and j, and output wire `

x
0
0
1
1

y
0
1
0
1

x∧y
0
0
0
1

A plain AND gate

x
ki0
ki0
ki1
ki1

y
kj0
kj1
kj0
kj1

x∧y
k`0
k`0
k`0
k`1

The associated keys
(garbled values)

Ciphertexts

Ek0 Ek0 k`0i j
Ek0 Ek1 k`0i j
Ek1 Ek0 k`0i j
Ek1 Ek1 k`1ij

The garbled gate
(in random order)βα∧β
I Given k α and k for some α, β ∈ {0, 1}, can obtain kij`
I But, nothing is revealed by this since all keys are random!

Yehuda Lindell

Techniques for Efficient Secure Computation

28/2/201317 / 39

A Garbled Circuit
Input wires d, a, b, e and output wires f, g

I Garbled gates can be combined together naturally
I Given one key for every input wire, can compute the entire

circuit without learning anything but the output
Yehuda Lindell

Techniques for Efficient Secure Computation

28/2/201318 / 39

Garbled Circuits

Correct computation:
I How does the circuit evaluator know which decryption iscorrect?
I Can include redundancy, but then the evaluator has to try all

4 (on average 2.5)
I Choose random “selector bits” that point to the correct

ciphertext (these are random so reveal nothing about theassociation between the key and the bit)Yehuda Lindell

Techniques for Efficient Secure Computation

28/2/201319 / 39

Yao’s Protocol
The Construction

A protocol for securely computing f (x, y):
I Inputs: P1 has x, and P2 has y
I Party P1 constructs a garbled circuit computing the function

f and sends it to party P2
I Party P1 sends the keys associated with its input x to P2
I P1 and P2 run 1-out-of-2 oblivious transfer for every bit of

P2 ’s input
In the ith OT, P2 inputs yi (its ith input bit) and P1 inputs
the pair of keys ki0 , ki1 associated with this input wireyy
I P2 receives k i and learns nothing about k iii
I

I Given one key for every input wire, P2 computes the garbled

circuit, obtains the output f (x, y), and sends it to P1

Yehuda Lindell

Techniques for Efficient Secure Computation

28/2/201320 / 39

Yao’s Protocol
Security for Semi-Honest Adversaries

P1 corrupted:
I P1 learns nothing in the OTs and only sees f (x, y)I This view is easy to simulate given the input and output

P2 corrupted:
I P2 learns a single key only for every input wire
I
I

This is trivial for P1 ’s input wires
This follows from the security of OT for P2 ’s input wires

I From the above, P2 learns nothing but the output from thegarbled circuit
I This view is simulated by constructing a garbled circuit thatjust outputs the prescribed output

Yehuda Lindell

Techniques for Efficient Secure Computation

28/2/201321 / 39

Optimizations for Yao’s Circuits
A Brief Look
I Double-encryption optimizations [LPS08,BHR12]: garbled

gate naively costs 8 encryptions to generate and 2 to evaluate;
this can be reduced to a half (at the expense of assumptions)
I Free XOR gates [KS08]: it is possible to choose the garbled
values so that XOR gates can be computed by just XORing
the input wires
I Garbled row reduction [PSSW09]: reduce the number of
ciphertexts to transmit from 4 to 3 (save bandwidth; a real
bottleneck)
I Circuit optimizations: make circuits smaller, and with more
XOR gates and less AND gates (a new engineering problem)
I Oblivious transfer extensions [IKNP03]: compute 128 real
OTs once, and derive many OTs from hash calls only
I Pipelined execution [HEKM11]: Split the circuit into partsand have the parties compute in parallel
Yehuda Lindell

Techniques for Efficient Secure Computation

28/2/201322 / 39

Yao’s Protocols with Malicious Adversaries
The Problems

I The OT must be secure for malicious adversaries

This was a problem 5 years ago: the best protocols required
O(n) exponentiations
I In 2008, this was solved by [PVW] (stand-alone model version
in [HL10]): the cost is 11m + 15 regular DDH exponentiations
for m transfers

I

I The circuit may not be correctly constructed
I
I

This is not just a problem of correctness, but also of privacy
The circuit can compute a different function of the evaluator’s
input, revealing something that should remain secret

Yehuda Lindell

Techniques for Efficient Secure Computation

28/2/201323 / 39

Ensuring Correctness of the Circuit
The cut-and-choose paradigm:
I P1 constructs many copies of the circuit
I P2 challenges P1 on half of them
I P1 opens the requested half and P2 checks that are correct
I The parties evaluate the remaining circuits and take output

Yehuda Lindell

Techniques for Efficient Secure Computation

28/2/201324 / 39

Cut-and-Choose on Yao’s Protocol
Opening a Pandora’s Box

We solve a problem but generate many new ones:
I The parties compute many circuits: we need to force them to

use the same inputs in all
I Opening a circuit means providing all keys on input wires: it

may be possible to construct a circuit with two sets of keys –one opening it to the correct circuit and one to a different
circuit
I The circuits may be correct, but the garbled keys may not be:
P1 can give invalid 0-keys for the first bit of P2 ’s input
If the first bit of P2 ’s input is 0, then it cannot compute andso must abort
I If the first bit of P2 ’s input is 1, then it computes
I Thus, P1 can learn the first bit of P2 ’s input by observing if itaborts or not
I This is called a selective bit attack [KS06]

I

Yehuda Lindell

Techniques for Efficient Secure Computation

28/2/201325 / 39

Cut-and-Choose on Yao’s Protocol
Another Problem

What should P2 do if not all computed circuits give thesame output?
I Observe that a few circuits may be incorrect with good

probability!
I If P2 aborts, then P1 can carry out the following attack:P1 generates one garbled circuit that outputs garbage if thefirst bit of P2 ’s input is 0; otherwise it computes f
I With probability 1/2, this circuit is not checked
I If the first bit of P2 ’s input is 0, it aborts
I If the first bit of P2 ’s input is 1, it does not abort
I Thus, P can learn the first bit of P ’s input by observing if it
1
2
aborts or not
I

I Thus, P2 cannot abort, even though it knows that P1 is trying

to cheat!
Yehuda Lindell

Techniques for Efficient Secure Computation

28/2/201326 / 39

Strategy for Determining Output
Party P2 cannot abort, and so takes the majority output
I This is sound since the probability that a majority of theunopened circuits are incorrect is negligible (in the number ofcircuits)
I But, what is the function bounding the probability ofcheating?
I

This is important since it determines the number of circuits,
which has a huge ramification on efficiency

I An inaccurate computation:

Let s be the number of circuits
The adversary succeeds if 4s circuits are incorrect and none ofthem are chosen to be checked
I Assume each circuit is checked w.p. 1/2, this occurs withprobability 2−s/4
I For security of 2−40 need 160 circuits
I

I

Yehuda Lindell

Techniques for Efficient Secure Computation

28/2/201327 / 39

Bounding the Cheating Probability

I In [LP07] a non-tight bound of 2−s/17 overall was provenI

We didn’t fully appreciate the ramification of this at the time

I In [LP11] this was improved to 2−0.311s and so 128 circuits

suffice
I In [sS11] it was shown that by checking 60% of the circuits,
this can be further improved to 2−0.32s and so 125 circuits

sufficeI

In [sS11], they show that this is optimal and thus
cut-and-choose for Yao is stuck at 125 times the cost ofsemi-honest Yao

Yehuda Lindell

Techniques for Efficient Secure Computation

28/2/201328 / 39

Dealing with Malicious Adversaries
Solving the Other Problems
I P2 ’s input consistency in all circuits: this is easily solved

within regular oblivious transfer
I P1 ’s input consistency in all circuits: many different

solutions (commitment sets, pseudorandom synthesizer andDiffie-Hellman proof, auxiliary circuits, and more)
I A circuit with a valid and invalid opening: commit to all

the keys when sending the circuit (commitment may be
implicit as well)
I Selective bit attack: randomize the inputs [LP07], or

incorporate the input keys for P1 into the checks [LP11]
Solving these problems more efficiently is a very active areaof research
Yehuda Lindell

Techniques for Efficient Secure Computation

28/2/201329 / 39

The Problem of Bandwidth
An Optimization

I For a circuit of 50,000 gates, 125 copies of the circuits

requires sending about 400 MB (and in practice even more)I

In many cases, this will be the bottleneck (especially over theInternet)

I An optimization proposed by [GMS08]:

P1 chooses a random ri for the ith garbling and generates the
garbled circuit using randomness P RG(ri )I P1 sends P2 a collision-resistant hash of the garbled circuits
I To open the ith circuit, P1 sends the seed ri only (and P2
checks the hash)
I To evaluate the ith circuit, P1 sends the garbled circuit (andP2 checks the hash)I

I This saves half of the communication (or even 60% using[sS11])
Yehuda Lindell

Techniques for Efficient Secure Computation

28/2/201330 / 39

Malicious Security via Yao’s Garbled Circuits
Where do we go from here?

I It is still possible to optimize the methods used to enforce

input consistency and so on, but the bottleneck of 125 circuits
cannot be broken
This means that unless massive parallelism is used, the cost of
malicious security is going to be high
I It seems that we have to abandon Yao to go further
I

I But, the proof of optimality of [sS11] assumes that the

protocol works by opening and checking some percentage andtaking the majority output from the evaluated circuits
I Can a variant of cut-and-choose be used to reduce thenumber of circuits?

Yehuda Lindell

Techniques for Efficient Secure Computation

28/2/201331 / 39

Cut-and-Choose Yao with Fewer Circuits [L13]

I Recall the problem: if P2 aborts when receiving inconsistent

outputs, this can leak information to P1
I We want to design a strategy so that P1 can only cheat bymaking all of the checked circuits correct and all of theevaluated circuits incorrect
 −1s
I If we succeed, then the cheating probability is justs2I

To get 2−40 security, 44 circuits suffice

I To further improve this, we can have P2 choose each circuit
to check/evaluate independently at random w.p. 12
I

This gives an error of 2−40 with just 40 circuits!

Yehuda Lindell

Techniques for Efficient Secure Computation

28/2/201332 / 39

Dealing with Inconsistent Outputs
The aim: make cheating possible only if all evaluated circuits
are incorrect
I Observation: the problem occurs only if P2 receives different
outputs
If not all the circuits evaluate, but the ones that do yield thesame output then there is no problem
I This holds because unless all evaluated circuits are incorrect,
at least one is correct and so the output is correct
I

I The idea: if P2 receives different outputs, then it will learn

P1 ’s input x
In this case, P2 can locally compute f (x, y) and obtain correct
outputI We stress that P1 cannot know if P2 learned f (x, y) because
all circuits had the same output or because it learned xIYehuda Lindell

Techniques for Efficient Secure Computation

28/2/201333 / 39

Dealing with Inconsistent Outputs
Continued

Implementing the idea:
I The ith output wire must have the same garbled values in all

circuits (checked by P2 in check circuits)I P2 first evaluates all the evaluation circuits
I P1 and P2 run a new malicious-secure computation for a small

circuit, as follows:
P1 inputs the same x as in the main computation
P2 inputs either garbage or two garbled values on a single wire
I If P2 ’s input is two garbled values, then P2 learns x
II

I Following this, P1 opens the check circuits and P2 checks

Yehuda Lindell

Techniques for Efficient Secure Computation

28/2/201334 / 39

The New Secure Computation for a Small Circuit

I The secure computation used is one of the previous protocols,

like [LP11]
I The circuit can be made very small, using a specific design(see the paper)I

To be concrete: 2m + ` − 1 non-XOR gates, where m is theoutput length and ` is the input length

I The proof that P1 uses the same x as before is just a regular

input consistency check that is applied anyway to the main
secure computation
The checks don’t have any problem going across different
circuits
I We proved our protocol using the method of [LP11] but
believe that others will work
I

Yehuda Lindell

Techniques for Efficient Secure Computation

28/2/201335 / 39

Conclusions – Malicious Yao with Fewer Circuits

I We can now achieve malicious security with much fewer

circuits
For error 2−40 it suffices to send 40 circuits
I Together with existing optimizations and techniques, this gives
us very fast security for malicious adversaries
I

I The big question:
I
I

What else can be improved and optimized?
I conjecture that we are not finished with Yao yet!

Yehuda Lindell

Techniques for Efficient Secure Computation

28/2/201336 / 39

The MPC Lounge
For More Information

The MPC Lounge has just been opened:
I The aim of the lounge is to be a resource on efficient securecomputation
I The lounge has a Wiki, a blog, and pointers to resources
I It is rather empty right now, but we hope that within the next

few months it will fill out
I Go to mpclounge.org

Yehuda Lindell

Techniques for Efficient Secure Computation

28/2/201337 / 39

Summary
I Efficient secure computation is a reality: there is interest andwe have fast protocols
I

I strongly believe that we will start seeing secure computationin use in the near future

I Yao’s garbled circuits can yield very fast protocols, but there

is still more to do
I We have considered only one approach in this talk (garbled
circuits):
I

There are a number of very important other approaches[NO09,IPS09,DO10,LOP11,BDOZ11,NNOS12,DPSZ12]

I Follow this exciting field and join us: the pace is fast

and the competition is growing, but we are doing things
that we never believed possible just a few years ago!

Yehuda Lindell

Techniques for Efficient Secure Computation

28/2/201338 / 39

Thank You

Thank You!

Yehuda Lindell

Techniques for Efficient Secure Computation

28/2/201339 / 39