Bay Area Crypto Day

In the past couple of years, lattice-based cryptography began a transition to widespread deployment. A striking example is that of Google's experiment with NewHope, a lattice-based key agreement protocol. In this talk, we will extract the common idea behind the three most practical lattice-based schemes for key exchange based on the learning with error problem (Frodo, NewHope and Kyber, respectively based on LWE, Ring-LWE and Module-LWE), and compare their efficiency.

Traditional protocols for secure multi-party computation (MPC) among n parties that achieve optimal resiliency communicate at least a linear (in n) number of bits. In this work we investigate the feasibility of MPC with sublinear communication complexity. Concretely, we consider two clients, one of which may be corrupted, that wish to perform some joint computation using n servers but do not have any trusted setup. We show that enforcing sublinear message complexity drastically affects the feasibility bounds on the number of corrupted parties that can be tolerated.

We provide a complete investigation of security against semi-honest adversaries---static and adaptive, with or without erasures---and also initiate the study of actively malicious adversaries. In the case of semi-honest static adversaries, our bounds match (up to any constant fraction of corruptions) the corresponding bounds when there is no communication restriction---i.e., we can tolerate up to t < (1/2 -\epsilon)n corrupted parties. For the adaptive case, however, the situation is different. We prove that without erasures a constant fraction of corruptions is intolerable, and---most surprisingly---when erasures are allowed, we prove that t < (1 - \sqrt(0.5) - \epsilon)n corruptions can be tolerated, which we also show to be optimal up to an arbitrarily small constant factor. The latter optimality proof hinges on a new treatment of probabilistic adversary structures which may be of independent interest. In the case of active corruptions in this setting, we prove that static security with abort is feasible when t < (1/2 - \epsilon)n, namely, the bound that is tight for semi-honest security.

This is joint work with Juan Garay, Yuval Ishai, and Rafail Ostrovsky.

Machine learning is widely used in practice to produce predictive models for applications such as image processing, speech and text recognition. These models are more accurate when trained on large amount of data collected from different sources. However, the massive data collection raises privacy concerns.

In this talk, I present new and efficient protocols for privacy preserving machine learning for linear regression, logistic regression and neural network training using the stochastic gradient descent method. I also report on experimental results that confirm our protocols are several orders of magnitude faster than the state of the art implementations and scale to millions of data samples with thousands of features.

Joint work with Yupeng Zhang.

To many theory-oriented cryptographers, symmetric encryption is our most passé problem. Yet from the point of view of providing a useful theory and desirable schemes, the area is very much alive. For this talk I’d like to explore the long dialectic that has taken us from semantic security to robust authenticated-encryption.

I’ll trace the history of AE, explaining why it emerged and how it evolved. AE is rare topic insofar as there has at least been a dialog around identifying what the right problem is. For most topics in cryptography, we seem to travel a road with little but our imagination as guide.

A puncturable pseudorandom function (PRF) has a master key k that enables one to evaluate the PRF at all points of the domain, and has a punctured key k_x that enables one to evaluate the PRF at all points but one. The punctured key k_x reveals no information about the value of the PRF at the punctured point x. In a private puncturable PRF, the punctured key k_x additionally hides the punctured point x. Previous privately puncturable PRF constructions relied on multilinear maps or indistinguishability obfuscation.

We construct the first privately puncturable PRF from standard lattice assumptions, namely from the hardness of learning with errors (LWE) and 1 dimensional short integer solutions (1D-SIS), which have connections to worst-case hardness of general lattice problems. Along the way, we introduce a number of new techniques that can have wider applications in other lattice-based constructions.

This is joint work with Dan Boneh and Hart Montgomery.

We introduce a novel technique for secure computation over large inputs. Specifically, we provide a new oblivious transfer (OT) protocol with a laconic receiver. Laconic OT allows a receiver to commit to a large input D (of length M) via a short message. Subsequently, a single short message by a sender allows the receiver to learn m_{D[L]}, where the messages m_0, m_1 and the location L \in [M] are dynamically chosen by the sender. All prior constructions of OT required the receiver's outgoing message to grow with D.

Our key contribution is an instantiation of this primitive based on the Decisional Diffie-Hellman (DDH) assumption. The technical core of this construction is a novel use of somewhere statistically binding (SSB) hashing in conjunction with hash proof systems. Next, we show applications of laconic OT to non-interactive secure computation on large inputs and multi-hop homomorphic encryption for RAM programs.

Based on joint work with Chongwon Cho, Nico Döttling, Sanjam Garg, Divya Gupta, and Antigoni Polychroniadou.

Succinct non-interactive arguments (SNARGs) enable verifying NP computations with substantially lower complexity than that required for classical NP verification. In this work, we first construct a lattice-based SNARG candidate with quasi-optimal succinctness (where the argument size is quasilinear in the security parameter). Further extension of our methods yields the first SNARG (from any assumption) that is quasi-optimal in terms of both prover overhead (polylogarithmic in the security parameter) as well as succinctness. Moreover, because our constructions are lattice-based, they plausibly resist quantum attacks. Central to our construction is a new notion of linear-only vector encryption which is a generalization of the notion of linear-only encryption introduced by Bitansky et al. (TCC 2013). We conjecture that variants of Regev encryption satisfy our new linear-only definition. Then, together with new information-theoretic approaches for building statistically-sound linear PCPs over small finite fields, we obtain the first quasi-optimal SNARGs.

We then show a surprising connection between our new lattice-based SNARGs and the concrete efficiency of program obfuscation. All existing obfuscation candidates currently rely on multilinear maps. Among the constructions that make black-box use of the multilinear map, obfuscating a circuit of even moderate depth (say, 100) requires a multilinear map with multilinearity degree in excess of 2^100. In this work, we show that an ideal obfuscation of both the decryption function in a fully homomorphic encryption scheme and a variant of the verification algorithm of our new lattice-based SNARG yields a general-purpose obfuscator for all circuits. Finally, we give some concrete estimates needed to obfuscate this “obfuscation-complete” primitive. We estimate that at 80-bits of security, a (black-box) multilinear map with ≈2^12 levels of multilinearity suffices. This is over 2^80 times more efficient than existing candidates, and thus, represents an important milestone towards implementable program obfuscation for all circuits.