Presentation

Report
GARBLED CIRCUITS
&
SECURE TWO-PARTY COMPUTATION
Payman Mohassel
Yahoo Labs
History of Garbled Circuits
1982: First oral presentation  [Andrew Yao]
1987: First written account  [GMW] (public-key)
1990: First use of term ``Garbled circuits”  [BMR] (symmetric-key)
1994: First abstraction as a primitive  [FKN] (minimal model for sec. comp.)
1999: First PRF-based construction  [NPS] (PP-auctions)
2004: First implementation  [MNPS] (Fairplay)
2004: First proof of 2PC based on garbled circuits  [LP] (double-encryption)
A Garbling Scheme
seed
 ,  = (, )







Eval(

)


(, )


Basic Properties
 Privacy: Knowing  ,  , and  does no leak any info

(, )






 Output Authenticity: Cannot compute another valid output



‘
Many Applications








Secure multi-party computation
Zero-knowledge proofs
Verifiable computation
Homomorphic encryption
One-time programs
Circular-secure encryption
Functional encryption
...
Emerged as a powerful building block!
Secure Multiparty Computation (MPC)
P2, x2
P1, x1
P3, x3
P5, x5
P4, x4
Correctness:
honest parties learn
the correct output
Privacy:
Nothing but the
final output is leaked
Parties learn only f(x1,…,xn) Fairness, Output Delivery, …
Applications of MPC








Data mining
Electronic Voting
Auctions
Exchanges/financial analysis
Location privacy
Genomic computation
Electronic commerce
Healthcare
 When there is IP, NDA, user consent involved
 When you need to distribute trust
Secure Two-Party Computation (2PC)
 ,  = (, )
 ← (, )
 ← (, )





Evaluator
Garbler
Oblivious Transfer

(, )
Yao’s Garbled Circuit Protocol
 First secure computation protocol
 Efficient and simple
 Implementations
›
Fairplay, 2004
TASTY, 2010
FastGarble, 2011
SCAPI, 2013
JustGarble, 2013
›
…
›
›
›
›
•
Circuits with millions of gates in less than a second
Research Directions
Garbling
Constructions
Functionality
&
Security Properties
Secure 2PC
Basic Garbling/Evaluation
Evaluate
Garble
01 , 11
AND
02 , 12
3 3
0 , 1
AND
0,0 =  01,02 (03 )
0,1 =  01,12 (03 )
1,0 =  11,02
1,1 =  11,12
(03 )
(13 )
3
 1 , 2 , = &

Constructions (Efficiency)










1990: Point-and-Permute  [BMR]
1999: 3-row reduction  [NPS]
2008: Free-XOR  [KS]
2009: 2-row reduction  [PSSW]
2013: Fixed-key block-cipher  [BHKR]
2014: FleXor  [KMR]
2014: Privacy-free garbling  [KNO]
2015: HalfGates  [ZRE]
(2-row non-XORs, and 0-row XORs)
How low can we get? Lower bounds?
Fresh ideas for garbling needed?
Constructions (Security)
Weak Assumptions
 PRF  double-encryption
 LPN  Free-XOR
 Correlation-robustness  row reduction techniques
 Correlation-robustness  FleXor
Strong Assumptions
 Circular-security  Free-XOR
 Circular-security  Half-Gates
 Ideal-permutation  Fixed-key block-cipher
 RO  Adaptive security
 Can we achieve these using weak assumptions?
Standard Security Properties
 Input privacy
›
Needed in most applications (not in ZK application)
 Function privacy
›
Private function evaluation
 Output authentication
›
Malicious 2PC, dual-execution, verifiable comp., server-aided comp., ZK
 Adaptive privacy
›
Verifiable comp, offline/online batch execution, …
New Security Properties?
 Only a subset of properties (e.g. privacy-free garbling)
 Leaky privacy (e.g. leak a few bits, protect/leak certain functions)
 Tunable security! (tunable privacy, authenticity, …)
 Leveled privacy (inputs with different sensitivity levels)
Functionality?
 Standard ones
›
Garble, encode inputs, evaluate, authenticate outputs
 Circuit property enforcing (with Rosulek and Kolesnikov)
›
Checking circuit properties
›
Topology, depth, input size, gate types
›
Useful in limiting malicious behavior
 Input property enforcing
›
Unique input identifier (for input consistency)
›
Enforcing input formats
›
Enforce relation between inputs in multiple executions (beyond equality)
 Output property enforcing
›
Enforcing output format
Malicious 2PC
Are all inputs the same?
Evaluate
Open

1

2

⋮
1
3

Is the output correct?
1
2
2
1 − 2−Ω  
 ≥ 40
3
4
5
Majority
4
4
6
6
5
6

 = (, )
Secure 2PC
 Malicious security
›
›
›
›
Cut-and-choose (state of the art: Lindell 2013)
Abstracting out cut-and-choose (joint work with Seny Kamara)
A new paradigm?
Lower bounds for cut-and-choose?
 RAM programs
›
›
›
›
Optimizing ORAM for 2PC ([WCS]: Circuit-ORAMs)
Implementation framework (SCVM)
Extending cut-and-choose to RAM programs ([AHMR])
Lots of interesting questions
 2PC with relaxed security
›
›
Covert security, leaky 2PC, one-sided security
Restricting leakage functions
Questi ons?

similar documents