Homomorphic Secret Sharing：Low-End HSS from OWF、HSS for Branching Programs from DDH、The HSS Construction

Homomorphic Secret Sharing Yuval Isha Technion European Research erc council Crypto Innovation School, November 2018

Homomorphic Secret Sharing Yuval Ishai Technion Crypto Innovation School, November 2018

1970 Primitives Assumptions PKE 1980 Signatures ZK OT Factoring Discrete Log 1990 Secure computation 2000 RILP 2010 CRYPTO

1970 1980 1990 2000 2010 PKE Secure Computation ZK Primitives Signatures Assumptions OT Factoring Discrete Log

1970 Primitives Assumptions PKE 1980 Signatures ZK OT Factoring Discrete Log 1990 Secure computation 2000 Minimize communication? Minimize interaction? 2010 Minimize local computation?

1970 1980 1990 2000 2010 PKE Secure Computation ZK Primitives Signatures Assumptions OT • Minimize communication? • Minimize interaction? • Minimize local computation? Factoring Discrete Log

1970 Primitives Assumptions PKE 1980 Signatures ZK OT Factoring Discrete Log 1990 Secure computation 2000 IBE ABE Bilinear Maps 2010 FHE Lattices FE

1970 1980 1990 2000 2010 Secure Computation ZK Primitives Signatures Assumptions OT Factoring Discrete Log FE IO IBE ABE Bilinear Maps FHE Lattices PKE

Fully Homomorphic encryption [RAD79, Gen09 (x) Function sk Dec Priva [P(X) Compactness Eval Dec<< P E Enc

Fully Homomorphic Encryption [RAD79,Gen09] Dec P(x) sk [x] Enc x pk Eval [P(x)] P Compactness: |Dec|<< |P| Function Privacy sk

State of the fhe The good Huge impact on the field -Solid 1 Given a generic group G Unconditionally secure PKE and even secure computation -Major. Not known to be helpful for FHE The not so goo Narrow set of assumptions and underlying structures all related to lattices Susceptible to lattice reduction attacks and other attacks Concrete efficiency still leaves much to be desired

State of the FHE • The good – Huge impact on the field – Solid foundations [BV11,GSW13,…] – Major progress on efficiency [BGV12,HS15,DM15,CGGI16,…] • The not so good – Narrow set of assumptions and underlying structures, all related to lattices • Susceptible to lattice reduction attacks and other attacks – Concrete efficiency still leaves much to be desired Given a generic group G: • Unconditionally secure PKE and even secure computation • Not known to be helpful for FHE

THERE HAS GOT TOBEA IN SOME SENSE FFERENT WAY

IN SOME SENSEDIFFERENT

Recall: ehe (x) sk Dec [P(x)] Eval E Enc

Recall: FHE Dec P(x) sk [x] Enc x pk Eval [P(x)] P

“1/2FHE sk Dec [P(x)]1 [P(×)]2 Eval Eval computationally computationally hi Ides x hides x Enc

“1/2 FHE” Dec P(x) sk [x]1 Enc x pk Eval [P(x)]1 P Eval [P(x)]2 P [x]2 computationally hides x computationally hides x

2-Party) Homomorphic Secret Sharing [P(x)]1 [P(×)]2 Eval Eval Share

(2-Party) Homomorphic Secret Sharing Dec P(x) [x]1 Share x Eval [P(x)]1 P Eval [P(x)]2 P [x]2 