### PPT - University of Calgary

```Private Function Evaluation
Payman Mohassel
University of Calgary
Talks given at Bristol and Aarhus Universities
Joint work with Saeed
Secure Function Evaluation
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 f(x1,…,xn)
2
Private vs. Secure Function
Evaluation

⋯ 2 1 ,
,
⋯ 2 ,  1 ,
( , … ,  )
( , … ,  )
⋯
⋯
Our Setup
• Function
o Boolean circuits
o Arithmetic circuits
• Settings we consider
o Two-party
o Multiparty
• Dishonest majority

⋯ 2 1 ,
( , … ,  )
⋯
Motivation
• Why Hide the Function?
o Private functions
• Proprietary, intellectual property
o Sensitive functions
• Revealing vulnerabilities
o Output of SFE leaks information
• Hiding the function potentially helps
• Prevents dictionary attacks on input
• Interactive program obfuscation
o If interaction is possible PFE yields efficient program
obfuscation
Is PFE Hard?
• Not really!
• All SFE feasibility results extend to PFE
o Using Universal Circuits
• The only interesting questions are efficiency
questions
Universal Circuits
C
Universal Circuit
C(x)
x
Universal Circuits
• Boolean
o For a circuit C with g gates
o [Valiant’ 76]: 19 log  + … (good for large circuits)
• Building it seems complicated
o [KS’ 08]: 1.5 log 2  + 2.5 log  + ⋯ (good for small circuits )
• Arithmetic
o For a circuit C with g gates and depth d
o [Raz’ 08]:   4 gates, i.e.  5 in the worst case
PFE Constructions
• Two-party setting
o Universal Circuit + Yao’s protocol
• (log) or (log 2 ) symmetric ops + () OTs
o [KM’ 11]: Homomorphic Enc + Yao’s protocol
•   public-key ops +   symmetric ops
• Multi-party setting
o Universal Circuit + GMW protocol
•   2 log OTs
• Arithmetic circuits
o Universal Circuit + HE-based MPC [CDN’ 01]
o (5 ) public-key ops
Efficiency Questions
• Asymptotic Efficiency
o Can we design PFE with linear complexity in all standard
settings?
• Practical Efficiency
o
o
o
o
Constant factors are important
Symmetric ops superior to public-key ops
…
Can we improve practical efficiency of universal circuit
approach?
Our Framework
Hiding the Circuit
• What is leaked
o Number of gates
o Input size
o Output size
• What is private
o Functionality of gates
o Topology of the circuit
One can hide circuit size using an FHE-based construction
Private Gate Evaluation
• Inputs are shared
o  = 1 ⊕ 2
o  = 1 ⊕ 2
• Gate function
o  = , ,
o  = +,×
o Known only to 1
2 , 2 1 , 1 ,
(, )
1
• Output is shared
o  = 1 ⊕ 2
Actual sharing mechanism depends on the protocol
2
Circuit Topology
• Topology captured using
a mapping

1
3
4
3
4
5
6
1
2
2
3
3
4
4
1
2
2
1
5
5
6
7
6
8
5
9
6
10
7
8
9
10
CTH
Functionality
• Inputs are shared
Map

o  = 1 ⊕ 2
• Mapping
o  known by 1 only
• Outputs are shared
o  = 1′ ⊕ 2′
• Query types
o Map: done internally
o Reveal: reveal result of map
o On-demand mapping
= 1 ⊕ 2
′1 ⊕  ′ 2 =
= 1 ⊕ 2
′1 ⊕  ′ 2 =
′′1 ⊕  ′′ 2 =
Reveal
PGE + CTH
CTH
1

3

4

5

6
Map

PGE

PGE

PGE

PGE

PGE
Reveal
5
6
Topological order
2

1
2
1
2
3
4
3
4
5
6
5
6
7
8
9
10
Instantiating PGE
PGE for GMW
1
1
2
3
2 , 2 1 , 1 ,
2 , 2
1-out-of-4 OT
2
(, )
4
1
g

2
g x
y
z
0
0
1 =  1 ⊕ 0, 1 ⊕ 0 ⊕ 1
0
0
g(0,0)
0
1
2 =  1 ⊕ 0, 1 ⊕ 1 ⊕ 1
0
1
g(0,1)
1
0
3 =  1 ⊕ 1, 1 ⊕ 0 ⊕ 1
1
0
g(1,0)
1
1
4 =  1 ⊕ 1, 1 ⊕ 1 ⊕ 1
1
1
g(1,1)
PGE for AC
•
•
•
•
,  ∈
= 1 + 2 ,  = 1 + 2
= 1 + 2 ,  = ( + )   = ( × )
2 ,  2 ,  (2 2 )
1 , 1 ,
1
(If +)
(If ×)
←
1 ← 1 + 1 −
1 ←
2 , 2 , ,
2
=  (2 + 2 + )
=  (1 1 + 2 1 + 1 2 + 2 2 − 1 )
2 ←  ()
PGE for Garbled Circuit
• We kind of cheat!
o We assume all gates are NAND gates
• Sharing associated with Yao
o To share a value
o 2 holds (0 , 1 )
o 1 holds
• 2 sends a garbled table to 1
• 1 decrypts one row of the table
Instantiating CTH
Oblivious Mapping
Oblivious mapping
1
π:  → []
2
3 ⊕ 3
3
1 ⊕ 5
4
5 ⊕ 6
5 ⊕ 7
1
1
2
.
.
.

1
2
.
.
.

−1
−1
−1
1
2

.
.
.
2
⊕ 1
⊕ 2
⊕

5
6
1 ⊕ 1
2 ⊕ 2
4 ⊕ 4
6 ⊕ 8
6 ⊕ 9
4 ⊕ 10
Oblivious Mapping
• Using any MPC
o inefficient
o Not clear it has the on-demand property
o [HEK’12] implements Waksman using Yao’s protocol
• Using singly HE
o Linear complexity
o Requires public-key operations
• Using oblivious transfer
o Not linear
o But better concrete efficiency (OT extension)
HE-based
,

1
2
.
.
.

(1 )
(2 )
.
.
.
( )
1
(−1 1 ⊕ 1 )
(−1 2 ⊕ 2 )
.
.
.
(−1  ⊕  )
Easy to make on-demand
2
1
2
.
.
.

Permutation Networks
Switches
selection bit
Permutation Network
0
…

…
1

…

…
[Waksman’ 68]: any permutation :  → [] can be implemented using a
permutation network of size   −  + 1
The permutation is determined using   −  + 1 selection bits
Switching Networks
• Our mapping is not a permutation
• Need one more switch type
0

0

1

1

Mapping from SN
1
2
.
.
.

.
.
.

Waksman
network
m −  + 1
1

2

3
4
.
.
.

1
1
1
1
1
1
0
1
2
Waksman
network
.
.
.
+

+
−  + 1
Oblivious Switch 1
,
2

1
3
2
4
(1 ⊕ 3 , 2 ⊕ 4 )
(1 ⊕ 4 , 2 ⊕ 3 )
1

1-out-of-2 OT
⊕ 1 ,  ⊕ 2
=0→
=1→
( ⊕ 1 ) ⊕ 1 ⊕ 3 =  ⊕
( ⊕ 2 ) ⊕ 2 ⊕ 4 =  ⊕
( ⊕ 2 ) ⊕ 2 ⊕ 3 =  ⊕
( ⊕ 1 ) ⊕ 1 ⊕ 4 =  ⊕
Oblivious Switch 2
,
2

1
3
2
4
(1 ⊕ 3 , 2 ⊕ 4 )
(1 ⊕ 3 , 1 ⊕ 4 )
1
1-out-of-2 OT

⊕ 1 ,  ⊕ 2
=0→
=1→
( ⊕ 1 ) ⊕ 1 ⊕ 3 =  ⊕
( ⊕ 2 ) ⊕ 2 ⊕ 4 =  ⊕
( ⊕ 1 ) ⊕ 1 ⊕ 3 =  ⊕
( ⊕ 1 ) ⊕ 1 ⊕ 4 =  ⊕
Oblivious SN Evaluation
MAP
⊕ 1
0
1

3 ⊕ 3
2
4
1
3
4
5
⊕ 6
6
1
⊕ 7
6
⊕ 7
7
5
8
⊕ 7 ⊕ 7
Reveal
Oblivious SN Evaluation
• One OT per switch
o O(mlog m) OTs total
• On-demand
o All OTs done offline
o Only Xoring online
• Practical when using OT extension
• Constant round
Oblivious Mapping 
CTH Functionality
• GMW or Arithmetic Circuits
o Inputs to mapping are ADDITIVE- or XOR-shared
o (MAP) Each party  runs an oblivious mapping with 1
•  uses his vector of shares as input
• 1 uses his mapping and blinding vector
o (Reveal) Each party obtains his blinded “mapped” vector
of shares
o 1 maps his own vector of shares and XOR/SUBTRACTs  s to
• Yao’s Protocol
o Slightly more involved due to “weird sharing” mechanism
Summary of Results
• First Multiparty PFE with linear complexity
o GMW + HE-Based oblivious mapping
• First Arithmetic PFE with linear complexity
o [CDN 01] + HE-based oblivious mapping
• More efficient two-party PFE with linear
complexity
o Yao + HE-based oblivious mapping
o Subsumes and improves construction of [KM’11]
• More practical PFE
o Yao/GMW + OT-based oblivious mapping + OT extension
Future Work
Other Security Notions
o Covert, malicious
o Can we still achieve linear complexity?
• PFE in the information theoretic setting
o Our OT-based solution seems generalizable to IT setting
o But linear PFE is open
• Can we hide circuit size without using FHE?
o or use FHE in a limited way, or use somewhat FHE?
Round Complexity of PFE
• Can we do PFE non-interactively?
o Our Yao-based protocol requires at least 3 messages
o SFE can be done in two messages
• Can we achieve constant round multiparty
PFE with linear complexity?
o We only know it for two-party case
• Can we achieve constant round arithmetic
PFE?
o Without switching to a Boolean circuit
PFE for Practice
• PFE with good concrete + asymptotic
efficiency
o E.g. designing OT-based oblivious mapping with linear
complexity
• Can PFE help improve efficiency of SFE?
o Idea:
• One party embeds his input in the circuit
• Shrinks the circuit significantly
• Circuit structure leaks information
• We use PFE to hide the structure
• PFE for RAM programs
Thank you!
```