Report

Private Function Evaluation Payman Mohassel University of Calgary Talks given at Bristol and Aarhus Universities Joint work with Saeed Sadeghian 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 • Semi-honest adversaries ⋯ 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 , = ( + ) = ( × ) is an additively homomrphic encryption 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 • Assume inputs are ready 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 adjust values. • 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 • Security against stronger adversaries 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!