22^nd Estonian Winter School in Computer Science (EWSCS)
XXII Eesti Arvutiteaduse Talvekool

Yuval Ishai

Technion, Israel & University of California at Los Angeles, USA

Homomorphic secret sharing

Abstract

Fully homomorphic encryption (FHE) is a powerful cryptographic tool that can be used to minimize the communication complexity of secure computation protocols. However, known FHE schemes rely on a relatively narrow set of assumptions and algebraic structures that are all related to lattices. Moreover, the efficiency of known FHE schemes still leaves much to be desired.

This tutorial will cover new techniques for succinct secure computation. The idea is to replace FHE by "homomorphic secret sharing" (HSS), which allows a compact evaluation of a function on a secret shared input, and construct HSS schemes for useful function classes in a way that gets around some of the limitations of known FHE schemes.

In the first part we will cover constructions of function secret sharing (FSS) schemes for simple function classes from one-way functions. FSS can be viewed as a dual version of HSS, where the roles of the function and input are reversed. More concretely, the goal of FSS is to split a function f into succinctly described f₁, ..., f_m, such that f(x)=f₁(x)+...+f_m(x) for every input x, and every strict subset of the f_i computationally hides f. We will present efficient constructions of FSS schemes for point functions and decision trees based on any pseudo-random generator, and survey applications of these constructions in the context of secure computation.

The second part of the tutorial will present a construction of more powerful types of HSS schemes under discrete-log-type assumptions. More concretely, under the decisional Diffie-Hellman (DDH) assumption, we construct a 2-out-of-2 secret sharing scheme that supports a compact evaluation of branching programs on the shares. We will survey different applications of this HSS scheme, including succinct secure computation for NC1, two-round general secure multiparty computation, and other DDH-based applications that previously required FHE.

Course materials

• Y. Ishai. Homomorphic secret sharing. Slides from the EWSCS 2017 course.
• Lectures 1-2 [pdf]
• Lectures 3-4 [pdf]
• Problems on the lecture material [pdf]


• E. Boyle, N. Gilboa, Y. Ishai. Function secret sharing. In E. Oswald, M. Fischlin, eds., Proc. of EUROCRYPT 2015, Part 2, v. 9057 Lect. Notes in Comput. Sci., pp. 337-367. Springer, 2015. [doi link]
• E. Boyle, N. Gilboa, Y. Ishai. Function secret sharing: improvements and extensions. In Proc. of 2016 ACM SIGSAC Conf. on Computer and Communications Security, ACM CCS 2016, pp. 1292-1303. ACM, 2016. [doi link]
• E. Boyle, N. Gilboa, Y. Ishai. Breaking the circuit size barrier for secure computation under DDH. In M. Robshaw, J. Katz, eds., Proc. of CRYPTO 2016, Part 1, v. 9814 of Lect. Notes in Comput. Sci., pp. 509-539. Springer, 2016. [doi link]
• E. Boyle, N. Gilboa, Y. Ishai. Group-based secure computation: optimizing rounds, communication, and computation. In Proc. of EUROCRYPT 2017, Lect. Notes in Comput. Sci.. Springer, to appear.

Last changed March 19, 2017 0:30 Europe/Helsinki (GMT +02:00) by local organizers, ewscs17(at)cs.ioc.ee
EWSCS'17 page: //cs.ioc.ee/ewscs/2017/