### slides - Yan Huang

```Fast Cut-and-Choose Based Protocols for
Malicious and Covert Adversaries
Yehuda Lindell
Bar-Ilan University
Efficient Secure Two-Party Computation
Using Symmetric Cut-and-Choose
Yan Huang, Jonathan Katz, David Evans
University of Maryland, University of Virginia
Secure Two-Party Computation
• Two parties with private inputs x and y
• Compute a joint function of their inputs while
preserving
– Privacy
– Correctness
– Independence of
inputs
2
• Semi-honest: follow protocol description but
– Highly efficient, but weak guarantee
• Malicious: run any arbitrary attack strategy
– Much more expensive
• Covert: behave maliciously and may succeed,
but will be caught with a guaranteed
probability
3
Yao’s Protocol (Semi-Honest)
Bob
Alice
Input: x
Input: y
Garbled
(encrypted)
circuit
Compute f(x,y)
(learn nothing else)
Security for Malicious
• Alice may not construct the circuit correctly
• Solution – cut-and-choose
5
6
7
Final output
Majority
8
The Cost
• How many circuits are needed to make sure
that the majority are correct?
– With s circuits, probability of cheating is 2-0.311s
[LP11] or 2-0.32s [sS11]
– For error 2-40, need approximately 125 circuits
– For error 2-80, need approximately 250 circuits
• This is a very heavy price!
9
These Two Works
• Aim: reduce the number of garbled circuits
needed
1. Lindell: s circuits + some small additional
overhead for 2-s error
2. Huang-Katz-Evans: s circuits per party in parallel
for 2-s error
• Cut-and-choose opens up many other problems
(input consistency etc.); we focus on the main issue
of number of circuits
10
Lindell’s Solution – The Main Idea
• Why majority?
– A malicious Alice can make most circuits correct
and a few not
– The incorrect circuits can compute the function if
Bob’s input meets some condition; otherwise
compute garbage
– Bob aborts if it gets different outputs:
• If Bob aborts, Alice knows that Bob’s input does not
meet the condition
• If Bob does not abort, Alice knows that Bob’s input
meets the condition
11
Lindell’s Solution – The Main Idea
• Make cheating possible only if all checked circuits
are correct and all evaluated circuits are incorrect
– This yields error 2-s for s circuits
• How?
– Alice and Bob run a small secure computation in
– If Bob received two different outputs in two different
circuits, it learns Alice’s input
– In this case, Bob computes f(x,y) itself
– Alice doesn’t know which case happened
12
Lindell’s Solution – The Main Idea
• The secure computation
– Yao’s circuit for malicious (e.g., LP11)
– Number of non-XOR gates is only the number of
bits in Alice’s input (very small circuit)
• Input consistency and other issues are dealt
with as in other works
– These other parameters are not optimized in the
paper
– This will be discusses in the next talk; their
solutions can be applied here
13
Lindell’s Solution – More Details
• The garbled values on the output wires are secret
(this has been used for secure delegation)
• If Bob learns two garbled values on a single output
wire (in different circuits), then Alice must have
been cheating
– This is a proof that Alice cheated
• The secure computation checks if Bob has two such
values and outputs Alice’s input x to Bob if yes
• This circuit can be made very small, and Alice can
be forced to use the same input
14
Huang-Katz-Evans Solution
• Observation
– One of the two parties is honest, all circuits
generated by him is correct
• Approach
– Let each party generate half of the circuits
– Suffices to ensure at least one good evaluation
circuit is generated by the adversary
15
16
A party uses
consistent inputs
in both roles
Securely combine both
parties’ results to obtain
the final output
17
Input Consistency – The Goal
Generator
s
s
sends wi
w10
w20
w30
w40
w11
w12
w13
w14
Evaluator / OT Receiver
ì q = gk
ï 0
[Naor and Pinkas, SODA2001] k ¬
, sends qs
q, í
k
ïî q1 = C / g
The discrete log of C is unknown.
18
Input Consistency – The Idea
Generator
s
w10 = g a1
w20 = g a2
w30 = g a3
w40 = g a4
w11 = C / g r1
w12 = C / g r2
w13 = C / g r3
w14 = C / g r4
Evaluator / OT Receiver
ì q = gk
ï 0
k ¬ q, í
, sends qs
k
ïî q1 = C / g
19
Final output
Goal: Derive the final
output from both parties’
circuit evaluation results
z
20
Output Revelation
Verifiable Secret Sharing
w10
w20
w30
w40
w50
w60
w70
w80
w11
w12
w13
w14
w15
w16
w17
w18
Generator picks a pair of secrets (s0, s1)randomly
(w10 ,w20 ,w30 ,w40 ,w50 ,w60 ,w70 ,w80 ) = VSS.Share(s0 ,8,5)
(w11,w12 ,w13 ,w14 ,w15 ,w16 ,w17 ,w18 ) = VSS.Share(s1,8,5)

2
with threshold: + 1 = 5.
21
Output Revelation
circuit check
w10
w20
w30
w40
w50
w60
w70
w80
w11
w12
w13
w14
w15
w16
w17
w18
Verify(s0 ,w ),Verify(s0 ,w ),Verify(s0 ,w ),Verify(s0 ,w )
0
1
0
3
0
4
0
7
Verify(s1,w ), Verify(s1,w ),Verify(s1,w ),Verify(s1,w )
1
1
1
3
1
4
1
7
sharing threshold: 5.
22
Output Revelation
circuit evaluation
w10
w20
w30
w40
w50
w60
w70
w80
w11
w12
w13
w14
w15
w16
w17
w18
s0 = VSS.Recover(w ,w ,w ,w ,w ,w ,w ,w )
0
1
0
2
0
3
0
4
0
5
0
6
0
7
0
8
s1 = VSS.Recover(w ,w ,w ,w ,w ,w ,w ,w )
1
1
1
2
1
3
1
4
1
5
1
6
1
7
1
8
sharing threshold: 5.
23
Output Revelation
secure equality test
Output 0
(s0, s’0)
(s0, s’0)
Output 1
(s0,s1)
(s1, s’1)
(s1, s’1)
(s’0,s’1)
One and only one of the 2 tests can succeed.
24
Conclusions
Actively secure two party computation can be done
with reduced number of circuits via either punishing
the cheater or symmetric cut-and-choose.
```