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 +
Other hss variants More than 2 shares: (m, t)-HSS Non-trivial information -theoretic hss when m>2t mplicit in best known information theoretic Pir and locally decodable codes [Yeko7, Efro9, blKo12 General compact output Compact HSs for low-degree polynomials [blo1,WY05, C F15, LM$18 Multiple inputs Public/secret key hss HSS taxonomy in [Boyle- Gilboa-l-Lin-Tessaro18
• More than 2 shares: (m,t)-HSS – Non-trivial information-theoretic HSS when m>2t – Implicit in best known information theoretic PIR and locally decodable codes [Yek07,Efr09,BIKO12] • General compact output – Compact HSS for low-degree polynomials [BI01,WY05,CF15,LMS18] • Multiple inputs • Public/secret key HSS • HSS taxonomy in [Boyle-Gilboa-I-Lin-Tessaro18] Other HSS Variants
HSS VS FHE HSS is generally weaker 2(or more) shares Vs single ciphertext Non-collusion assumption but has some advantages Ultimate output compactness Efficient and public decoding Can aggregate many outputs
HSS vs. FHE • HSS is generally weaker… – 2 (or more) shares vs. single ciphertext – Non-collusion assumption • … but has some advantages – Ultimate output compactness – Efficient and public decoding – Can aggregate many outputs
Applications Delegating Computations to the Cloud FHE HSS Bonus features: Multiple clients [P(×)]1 P(x)]2 Useful also for small p sk P(X)
Applications Delegating Computations to the Cloud sk [x] [P(x)] P(x) FHE HSS [x]1 [x]2 P(x) [P(x)]2 [P(x)]1 Bonus features: • Multiple clients • Useful also for small P
Applications Communication complexity of securely computing C? (a,b) C Cla, b) Classically: >C [Yao86, GMW87, BGW88, CCD88,. even for restricted classes, such as formulas Using FHE: M input +output
Applications (a,b) C(a,b) C • Classically: > |C| [Yao86,GMW87,BGW88,CCD88,…] … even for restricted classes, such as formulas • Using FHE: ~ |input|+|output| Communication complexity of securely computing C?