Monthly Archives: January 2016

Please join us for second Charles River Crypto Day of this academic year on Friday, February 26 at MSR New England.

Location and Arrival Instructions:
Microsoft New England Research and Development Center
Clara Barton Room (First Floor),
One Memorial Drive, Cambridge MA 02142.

Thanks to NSF MACS Project for their generous support.


9:30 – 10:00. Introduction/Coffee
10:00 – 11:00. Ron Rothblum, MIT
Constant-round Interactive-proofs for Delegating Computations
11:30 – 12:30.
Omer Paneth, Boston University
Delegating RAM Computations
12:30 – 1:30. Lunch (provided)
1:30 – 2:30. Silas Richelson, MIT
Three round Non-Malleable Commitment from Non-Malleable Codes
3:00 – 4:00. Muthu Venkitasubramaniam, University of Rochester
On the Power of Secure Two-Party Computation


Speaker: Ron Rothblum
Title: Constant-round Interactive-proofs for Delegating Computations

Interactive proofs have had a dramatic impact on Complexity Theory and Cryptography. In particular, the celebrated IP=PSPACE Theorem [LFKN92,Shamir92] allows an all-powerful but untrusted prover to convince a polynomial-time verifier of the validity of extremely complicated statements (as long as they can be evaluated using polynomial space). The interactive proof system designed for this purpose requires a polynomial number of communication rounds. It is very natural and well motivated to examine the power of more efficient interactive proofs, and this is the focus of this work.

Our main result is that for every statement that can be evaluated in polynomial time and bounded-polynomial space there exists an interactive proof that satisfies the following strict efficiency requirements: (1) the honest prover runs in polynomial time, (2) the verifier is almost linear time (and under some conditions even sub linear), and (3) the interaction consists of only a constant number of communication rounds.

We introduce several new notions for interactive proofs that turn out to be very useful in our work and may be of independent interest. One of these notions is that of unambiguous interactive proofs where the prover has a unique successful strategy. Another notion is that of probabilistically checkable interactive proofs (PCIPs) where the verifier only reads a few bits of the transcript in checking the proof (this could be viewed as an interactive extension of PCPs).

Joint work with Omer Reingold and Guy Rothblum.

Speaker: Omer Paneth
Title: Delegating RAM Computations

In the setting of cloud computing a user wishes to delegate its data, as well as computations over this data, to a cloud provider. Each computation may read and modify the data, and these modifications should persist between computations. Minding the computational resources of the cloud, delegated computations are modeled as RAM programs. In particular, the delegated computations’ running time may be sub-linear, or even exponentially smaller than the memory size.

We construct a two-message protocol for delegating RAM computations to an untrusted cloud. In our protocol, the user saves a short digest of the delegated data. For every delegated computation, the cloud returns, in addition to the computation’s output, the digest of the modified data, and a proof that the output and digest were computed correctly. When delegating a T-time RAM computation M with security parameter k, the cloud runs in time T * Poly(k) and the user in time Poly(|M|, log(T), k).

Our protocol is secure assuming super-polynomial hardness of the Learning with Error (LWE) assumption. Security holds even when the delegated computations are chosen adaptively as a function of the data and output of previous computations.

We note that RAM delegation schemes are an improved variant of memory delegation schemes [Chung et al. CRYPTO 2011]. In memory delegation, computations are modeled as Turing machines, and therefore, the cloud’s work always grows with the size of the delegated data.

Joint work with Yael Tauman Kalai.

Speaker: Silas Richelson
Title: Three-Round Non-Malleable Commitments from Non-Malleable Codes

We present a new non-malleable commitment protocol. Our protocol has the following features:

1) The protocol has only three rounds of interaction. Pass (TCC 2013) showed an impossibility result for a two-round non-malleable commitment scheme w.r.t. a black-box reduction to any “standard” intractability reduction. Thus, this resolves the round complexity of non-malleable commitment at least w.r.t. black-box security reductions. Our construction is secure as per the standard notion of non-malleability w.r.t. commitment.

2) Our protocol is efficient. In our basic protocol, the entire computation of the committer is dominated by just three invocations of a non-interactive statically binding commitment scheme, while, the receiver computation (in the commitment stage) is limited to just sampling a random string. Unlike many previous works, we directly construct a protocol for large tags and hence avoid any non-malleability amplification steps.

3) Our protocol is based on a black-box use of any non-interactive statistically binding commitment scheme. Such schemes, in turn, can be based on any one-to-one one-way function (or any one-way function at the cost of an extra initialization round). Previously, the best known black-box construction of non-malleable commitments required a larger (constant) number of rounds.

4) Our construction is public-coin and makes use of only black-box simulation. Prior to our work, no public-coin constant round non-malleable commitment schemes were known based on black-box simulation.

Our techniques depart significantly from the techniques used previously to construct non-malleable commitment schemes. As a main technical tool, we rely on non-malleable codes in the split state model. Our proofs of security are purely combinatorial in nature.

In addition, we also present a simple construction of constant round non-malleable commitments from any one-way function. While this result is not new, the main feature is its simplicity compared to any previous construction of non-malleable commitments (regardless of the number of rounds). We believe the construction is simple enough to be covered in a graduate level course on cryptography. The construction uses non-malleable codes in the split state model in a black-box way.

This is joint work with Vipul Goyal and Omkant Pandey.

Speaker: Muthu Venkitasubramaniam
Title: On the Power of Secure Two-Party Computation

Ishai, Kushilevitz, Ostrovsky and Sahai (STOC`07, SIAM JoC 2009) introduced the powerful “MPC-in-the-head” technique that provided a general transformation of information-theoretic MPC protocols secure against passive adversaries to a ZK proof in a “black-box” way. In this work, we extend this technique and provide a generic transformation of any semi-honest secure two-party computation (2PC) protocol (with mild adaptive security guarantees) in the so called \emph{oblivious-transfer} hybrid model to an adaptive ZK proof for any NP-language, in a “black-box” way assuming only one-way functions. Our basic construction based on Goldreich-Micali-Wigderson’s 2PC protocol yields an adaptive ZK proof with communication complexity proportional to quadratic in the size of the circuit implementing the NP relation. Previously such proofs relied on an expensive Karp reduction of the NP language to Graph Hamiltonicity (Lindell and Zarosim (TCC`09, Journal of Cryptology 2011)). We also improve our basic construction to obtain the first linear-rate adaptive ZK proofs by relying on efficient maliciously secure 2PC protocols. Core to this construction is a new way of transforming 2PC protocols to efficient (adaptively secure) instance-dependent commitment schemes.

As our second contribution, we provide a general transformation to construct a randomized encoding of a function f from any 2PC protocol that securely computes a related functionality (in a black-box way). We show that if the 2PC protocol has mild adaptive security guarantees then the resulting randomized encoding (RE) can be decomposed to an offline/online encoding.

As an application of our techniques, we show how to improve the construction of Lapidot and Shamir (Crypto`90) to obtain black-box constructions of commit-and-prove protocols with the so called input-delayed property where the honest prover’s algorithm does not require the actual statement until the last round. Using this, we obtain first constructions of a 4-round concurrent non-malleable commitments scheme based on one-way permutations where the underlying one-way permutation is used in a black-box way. Previous constructions either required more number of rounds or made non-black-box usage of the underlying primitive. We also show how these proofs can improve round complexity of secure computation protocols in the tamper-proof model.

Joint work with Carmit Hazay.