Monthly Archives: November 2014

Please join us for the next installment of Crypto Day on Friday, December 5 at Boston University.

Location: 111 Cummington Mall Room 180. [directions]

Parking: There’s a pay lot across the street and 4-hour meters on Bay State Road.


9:30 – 10:00. Introduction/Coffee
10:00 – 11:00.
Yuval Ishai, Technion
Circuits Resilient to Additive Attacks, with Applications to Secure Computation
11:30 – 12:30. Omer Paneth, Boston University
Publicly-Verifiable Non-Interactive Arguments for Delegating Computations
12:30 – 2:00. Lunch (provided)
2:00 – 3:00. Elaine Shi, University of Maryland
Programs to Circuits: Towards a Programming Language for Cryptography
3:30 – 4:30. Sergey Gorbunov, MIT
Leveled Fully Homomorphic Signatures from Standard Lattices

Thanks: NSF Frontier Grant: Modular Approach to Cloud Security (MACS), Hariri Institute for Computing and Center for RISCS.

Special thanks to Leo Reyzin, Debbie Lehto, and Lauren Dupee for help with organization


Speaker: Yuval Ishai
Title: Circuits Resilient to Additive Attacks, with Applications to Secure Computation

We study the question of protecting arithmetic circuits against additive attacks that can add an arbitrary fixed value to each wire in the circuit. We show how to transform an arithmetic circuit C into a functionally equivalent, randomized circuit C’ of comparable size, such that the effect of any additive attack on the wires of C’ can be simulated (up to a small statistical distance) by an additive attack on just the inputs and outputs of C.

Our study of this question is motivated by the goal of simplifying and improving protocols for secure multiparty computation (MPC). It is typically the case that securing MPC protocols against active adversaries is much more difficult than securing them against passive adversaries. We observe that in simple MPC protocols that were designed to protect circuit evaluation only against passive adversaries, the effect of any active adversary corresponds precisely to an additive attack on the circuit’s wires. Thus, to securely evaluate a circuit C in the presence of active adversaries, it suffices to apply the passive-case protocol to a corresponding circuit C’ which is secure against additive attacks. We use this methodology to simplify feasibility results and obtain efficiency improvements in several standard MPC models.

Joint work with Daniel Genkin, Manoj Prabhakaran, Amit Sahai, and Eran Tromer.

Speaker: Omer Paneth
Title: Publicly-Verifiable Non-Interactive Arguments for Delegating Computations

We construct publicly verifiable non-interactive arguments that can be used to delegate polynomial time computations. These computationally sound proof systems are completely non-interactive in the common reference string model. The verifier’s running time is nearly-linear in the input length, and poly-logarithmic in the complexity of the delegated computation. Our protocol is based on graded encoding schemes, introduced by Garg, Gentry and Halevi (Eurocrypt 2012). Security is proved under a falsifiable and arguably simple cryptographic assumption about graded encodings. All prior publicly verifiable non-interactive argument systems were based on non-falsifiable knowledge assumptions. Our new result builds on the beautiful recent work of Kalai, Raz and Rothblum (STOC 2014), who constructed privately verifiable 2-message arguments. While building on their techniques, our protocols avoid no-signaling PCPs, and we obtain a simplified and modular analysis.

As a second contribution, we also construct a publicly verifiable non-interactive argument for (logspace-uniform) computations of bounded depth. The verifier’s complexity grows with the depth of the circuit. This second protocol is adaptively sound, and its security is based on a falsifiable assumption about the hardness of a search problem on graded encodings (a milder cryptographic assumption). This result builds on the interactive proof of Goldwasser, Kalai and Rothblum (STOC 2008), using graded encodings to construct a non-interactive version of their protocol.

Joint work with Guy Rothblum.

Speaker: Elaine Shi
Title: Programs to Circuits: Towards a Programming Language for Cryptography

Modern cryptography (e.g., secure multi-party computation, fully-homomorphic encryption, program obfuscation) commonly models computation as “circuits”. To make modern cryptography work for real-world programs, it is necessary to compile “programs” into compact “circuits”. The key difficulty is that programs make dynamic memory accesses, whereas circuits have static wiring. To address this challenge, we need efficient Oblivious RAM and oblivious algorithms.

In this talk, I will first describe Circuit ORAM, a new ORAM scheme that yields very small circuit size. Circuit ORAM shows the tightness of certain stronger interpretations of the well-known Goldreich-Ostrovsky lower bound.

Next, I will describe ObliVM, a programming framework that compiles real-life programs into compact circuits, while offering formal security guarantees.

Speaker: Sergey Gorbunov
Title: Leveled Fully Homomorphic Signatures from Standard Lattices

In a homomorphic signature scheme, a user Alice signs some large dataset x using her secret signing key and uploads the signed data to an untrusted remote server. The server can then run some computation y=f(x) over the signed data and homomorphically derive a short signature \sigma_{f,y} certifying that y is the correct output of the computation f. Anybody can verify the tuple (f, y, \sigma_{f,y}) using Alice’s public verification key and become convinced of this fact without having to retrieve the entire underlying data.

In this work, we construct the first (leveled) fully homomorphic signature schemes that can evaluate arbitrary circuits over signed data. Only the maximal depth d of the circuits needs to be fixed a-priori at setup, and the size of the evaluated signature grows polynomially in d, but is otherwise independent of the circuit size or the data size. Our solution is based on the (sub-exponential) hardness of the small integer solution (SIS) problem in standard lattices. In the standard model, we get a scheme with large public parameters whose size exceeds the total size of a dataset. In the random-oracle model, we get a scheme with short public parameters. In both cases, the schemes can be used to sign many different datasets. The complexity of verifying a signature for a computation f is at least as large as that of computing f, but can be amortized when verifying the same computation over many different datasets. Furthermore, the signatures can be made context-hiding so as not to reveal anything about the data beyond the outcome of the computation.

These results offer a significant improvement in capabilities and assumptions over the best prior homomorphic signature schemes, which were limited to evaluating polynomials of constant degree.

As a building block of independent interest, we introduce and construct a new object called homomorphic trapdoor functions (HTDF) which conceptually unites homomorphic encryption and signatures.

Joint work with Vinod Vaikuntanathan (MIT) and Daniel Wichs (Northeastern).