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
