Where: Tel Aviv Yaffo College, Weston Bld, room 007
Program
9:00--9:30Coffee + Gathering
9:30--10:30Zvika Brakerski (Weizmann), Obfuscating Circuits via Composite-Order Graded Encoding
10:30--10:45Coffee Break
10:45--11:45 Alon Rosen (IDC), The SPRING Family of Pseudorandom Functions
11:45--12:00Coffee Break
12:00--13:00 Pavel Hubacek (Weizmann), On the Communication Complexity of Secure Function Evaluation with Long Output
13:00--14:00 Lunch (served by us)
14:00--15:00Eylon Yogev (Weizmann), Secret-Sharing for NP
15:00--15:15Coffee Break
15:15--16:15 Ran Canetti (TAU and BU), ndistinguishability Obfuscation of Probabilistic and Iterated Programs
16:15 sending you home
Abstracts
Zvika Brakerski (The Weizmann Institute of Science)
Obfuscating Circuits via Composite-Order Graded Encoding
We present a candidate obfuscator based on composite-order Graded Encoding Schemes, which are a generalization of multilinear maps. Our obfuscator operates on circuits directly without converting them into formulas or branching programs as was done in previous solutions. As a result, the time and size complexity of the obfuscated program is directly proportional to the circuit complexity of the program being obfuscated. This improves upon previous constructions whose complexity was related to the formula or branching program size. Known instantiations of Graded Encoding Schemes allow us to obfuscate circuit classes of polynomial degree, which include for example families of circuits of logarithmic depth.
We prove that our obfuscator is secure against a class of generic algebraic attacks, formulated by a generic graded encoding model. We further consider a more robust model which provides more power to the adversary and extend our results to this setting as well.
Based on joint work with Benny Applebaum
Ran Canetti (Tel Aviv University and Boston University)
Indistinguishability Obfuscation of Probabilistic and Iterated Programs
Indistinguishability Obfuscation (IO) for general circuits has proven to be an extremely powerful and versatile primitive. Still, working with "bare-bones IO" is challenging and painstaking. We present two extensions of this notion:
•We show how to succinctly obfuscate ``iterated circuits'', namely circuits that work in iterations and where the output of each iteration is the input for the next one.
•We show how to obfuscate probabilistic circuits in a way that keeps the internal randomness hidden from, and unpredictable to, the evaluator.
As applications we show, assuming IO for circuits and one way functions (sometimes sub-exponentially strong and sometimes injective):
•IO for RAM programs. These are obfuscators where both the input and output programs are short RAM programs, and where the time and space complexities of the input program are individually preserved.
•(Still, the obfuscated program requires initialized memory of size proportional to the maximum space requirements of the input program.)
•Fully homomorphic encryption without circular security assumptions.
Based on joint work with Justin Holmgren, Abhishek Jain, Rachel Lin, Stefano Tessaro and Vinod Vaikuntanathan.
Pavel Hubacek (The Weizmann Institute of Science)
On the Communication Complexity of Secure Function Evaluation with Long Output
We study the communication complexity of secure function evaluation (SFE). Consider a setting where Alice has a short input a, Bob has an input b and we want Bob to learn some function y = f(a, b) with large output size. For example, Alice has a small secret decryption key, Bob has a large encrypted database and we want Bob to learn the decrypted data without learning anything else about Alice's key. In a trivial insecure protocol, Alice can just send her short input to Bob. However, all known SFE protocols have communication complexity that scales with size of the output y, which can potentially be much larger. Is such ``output-size dependence'' inherent in SFE?
Surprisingly, we show that output-size dependence can be avoided in the \honest-but-curious setting. In particular, using indistinguishability obfuscation (iO) and fully homomorphic encryption (FHE), we construct the first honest-but-curious SFE protocol whose communication complexity only scales with that of the best insecure protocol for evaluating the desired function, independent of the output size. Our construction relies on a novel way of using iO via a new tool that we call a ``somewhere statistically binding (SSB) hash'', and which may be of independent interest.
On the negative side, we show that output-size dependence is inherent in the fully malicious setting, or even already in an honest-but-deterministic setting, where the corrupted party follows the protocol as specified but fixes its random tape to some deterministic value. Moreover, we show that even in an offline/online protocol, the communication of the online phase must have output-size dependence. This negative result uses an incompressibility argument and it generalizes several recent lower bounds for functional encryption and (reusable) garbled circuits, which follow as simple corollaries of our general theorem.
Based on joint work with Daniel Wichs.
Alon Rosen (The Interdisciplinary Center, Herzlia)
The SPRING Family of Pseudorandom Functions
Recently, Banerjee, Peikert and Rosen (BPR) proposed new theoretical pseudorandom function candidates based on ``rounded products'' in certain polynomial rings, which have rigorously provable security based on worst-case lattice problems. The functions also enjoy algebraic properties that make them highly parallelizable and attractive for modern applications, such as evaluation under homomorphic encryption schemes. However, the parameters required by BPR's security proofs are too large for practical use, and many other practical aspects of the design were left unexplored in that work.
In this talk I will describe two concrete and practically efficient instantiations of the BPR design, which we call SPRING, for ``subset-product with rounding over a ring.'' One instantiation uses a generator matrix of a binary BCH error-correcting code to ``determinstically extract'' nearly random bits from a (biased) rounded subset-product. The second instantiation eliminates bias by working over suitable moduli and decomposing the computation into ``Chinese remainder'' components.
I will also report on initial software implementations whose throughputs are within small factors (as small as 4.5) of those of AES, and on a hardware implementation that examines the resistance of SPRING against side-channel attacks.
Based on joint works with Abhishek Banerjee, Hai Brenner, Gaetan Leurent and Chis Peikert, and Hai Brenner, Lubos Gaspar, Gaetan Leurent and Francois-Xavier Standaert.
Eylon Yogev (The Weizmann Institute of Science)
Secret-Sharing for NP
A computational secret-sharing scheme is a method that enables a dealer, that has a secret, to distribute this secret among a set of parties such that a "qualified" subset of parties can efficiently reconstruct the secret while any "unqualified" subset of parties cannot efficiently learn anything about the secret. The collection of "qualified" subsets is defined by a Boolean function.
It has been a major open problem to understand which (monotone) functions can be realized by a computational secret-sharing schemes. Yao suggested a method for secret-sharing for any function that has a polynomial-size monotone circuit (a class which is strictly smaller than the class of monotone functions in P). Around 1990 Rudich raised the possibility of obtaining secret-sharing for all monotone functions in NP: In order to reconstruct the secret a set of parties must be "qualified" and provide a witness attesting to this fact.
Recently, Garg et al. (STOC 2013) put forward the concept of witness encryption, where the goal is to encrypt a message relative to a statement "x in L" for a language L in NP such that anyone holding a witness to the statement can decrypt the message, however, if x is not in