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

Palmse, Estonia, March 5 - 10, 2017

Yuval Ishai

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

Homomorphic secret sharing


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 f1, ..., fm, such that f(x)=f1(x)+...+fm(x) for every input x, and every strict subset of the fi 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

Valid CSS! Valid XHTML 1.0 Strict 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/