Archive

Monthly Archives: September 2016

Come to the first Charles River Crypto Day of this academic year and get your fix of coffee, blockchains, rational proofs, memory hard functions and (need we say) indistinguishability obfuscation.

When: Friday, October 14 at MIT.

Where: 32 Vassar St (Stata Center)
G-882 (Hewlett), Cambridge MA 02139.

Organizers: Yael Kalai, Ron Rothblum, Vinod Vaikuntanathan and Daniel Wichs.

Thanks: NSF MACS Project for their generous support.

Program:

9:30 – 10:00. Introduction/Coffee
10:00 – 11:00.
Nir Bitansky, MIT
From Cryptomania to Obfustopia through Secret-Key Functional Encryption
11:00 – 12:00.
Rachel Lin, UC Santa Barbara
Indistinguishability Obfuscation from DDH-like Assumptions on Constant-Degree Graded Encodings
12:00 – 1:30. Lunch (provided)
1:30 – 2:30. Jing Chen, Stony Brook
Rational Proofs with Multiple Provers
2:30 – 3:30. Elaine Shi, Cornell
Blockchains and Beyond: Rethinking Distributed Consensus in New Settings
3:30 – 4:00. Coffee Break
4:00 – 5:00. Jeremiah Blocki, Purdue
Towards a Theory of Data-Independent Memory Hard Functions

Abstracts:

Speaker: Nir Bitansky
Title: From Cryptomania to Obfustopia through Secret-Key Functional Encryption

Functional encryption lies at the frontiers of current research in cryptography; some variants have been shown sufficiently powerful to yield indistinguishability obfuscation (IO) while other variants have been constructed from standard assumptions such as LWE. Indeed, most variants have been classified as belonging to either the former or the latter category. However, one mystery that has remained is the case of \emph{secret-key functional encryption} with an unbounded number of keys and ciphertexts. On the one hand, this primitive is not known to imply anything outside of minicrypt, the land of secret-key crypto, but on the other hand, we do no know how to construct it without the heavy hammers in obfustopia.

In this work, we show that (subexponentially secure) secret-key functional encryption is powerful enough to construct indistinguishability obfuscation if we additionally assume the existence of (subexponentially secure) plain public-key encryption. In other words, secret-key functional encryption provides a bridge from cryptomania to obfustopia.

On the technical side, our result relies on two main components. As our first contribution, we show how to use secret key functional encryption to get “exponentially-efficient indistinguishability obfuscation” (XIO), a notion recently introduced by Lin et al. (PKC ’16) as a relaxation of IO. Lin et al. show how to use XIO and the LWE assumption to build IO. As our second contribution, we improve on this result by replacing its reliance on the LWE assumption with any plain public-key encryption scheme.

Lastly, we ask whether secret-key functional encryption can be used to construct public-key encryption itself and therefore take us all the way from minicrypt to obfustopia. A result of Asharov and Segev (FOCS ’15) shows that this is not the case under black-box constructions, even for exponentially secure functional encryption. We show, through a non-black box construction, that subexponentially secure-key functional encryption indeed leads to public-key encryption. The resulting public-key encryption scheme, however, is at most quasi-polynomially secure, which is insufficient to take us to obfustopia.

Joint work with Ryo Nishimaki, Alain Passelègue, and Daniel Wichs

Speaker: Rachel Lin
Title: Indistinguishability Obfuscation from DDH-like Assumptions on Constant-Degree Graded Encodings

All constructions of general purpose indistinguishability obfuscation (IO) rely on either meta-assumptions that encapsulate an exponential family of assumptions (e.g., Pass, Seth and Telang, CRYPTO 2014) or polynomial families of assumptions, on graded encoding schemes with a high polynomial degree/multilinearity (e.g., Gentry, Lewko, Sahai and Waters, FOCS 2014).

In this talk, we present two recent works on simplifying graded encodings needed for constructing IO [Lin EUROCRYPT 2016 and Lin-Vaikuntanathan FOCS 2016]. These two works show that IO can be constructed from only constant-degree graded encodings, with a security reduction to a DDH-like assumption — called the joint-SXDH assumption — on the graded encodings, and the sub-exponential security of a polynomial-stretch PRG in NC0. Our assumption on graded encodings is simple, has constant size, and does not require handling composite-order rings. This narrows the gap between the mathematical objects that exist (bilinear maps, from elliptic curve groups) and ones that suffice to construct general purpose IO.

Speaker: Jing Chen
Title: Rational Proofs with Multiple Provers

Classic interactive proofs model a world where a verifier delegates computation to an untrustworthy prover, verifying the prover’s claims before accepting them. We provide the first model that extends rational interactive proofs to allow multiple provers. A verifier pay the provers according to his own randomness and the information received from them. The provers are rational rather than untrustworthy —they may lie, but only to increase the payment. Properly designed protocols incentivize the provers to provide correct information and hence let the verifier to learn the correct answer.

We give tight upper and lower bounds on the computation power of this model. On the way, we show that multiple rational provers are strictly more powerful than one, under standard complexity-theoretic assumptions. We further show that the full power of rational proofs with multiple provers can be achieved using only two provers and five rounds of interaction. Finally, we consider more demanding models where the verifier wants the payment to decrease significantly when the provers are lying, and fully characterize the power of the model when the payment gap must be noticeable.

Speaker: Elaine Shi
Title: Blockchains and Beyond: Rethinking Distributed Consensus in New Settings

Abstract coming soon.

Speaker: Jeremiah Blocki
Title: Towards a Theory of Data-Independent Memory Hard Functions

There is a growing interest in functions which are moderately hard to compute on a normal single-processor machine, but which cannot be computed at a significantly lower cost of dedicated hardware. Such functions are necessary for password-hashing to prevent brute-force attacks implemented on application specific integrated circuits (ASICs). Towards this goal memory-hard functions (MHFs) have been proposed, motivated by the observation that memory costs on customized hardware is not much cheaper than on general architectures. A MHF should have the properties that: (1) Computing the MHF on any input, using a sequential algorithm requires a moderate amount of computational resources (memory and time), and (2) The MHF cannot be repeatedly computed in parallel with significantly less computational resources even if an adversary can amortize his costs across multiple instances (e.g., password guesses). More specifically, we want to ensure that any algorithm evaluating multiple instances of the MHF has high amortized ST-cost — Space X Time divided by #instances evaluated. The second property ensures that the amortized cost of computing an MHF cannot be significantly reduced by developing application specific integrated circuits (ASICs).

Of particular interest in the context of password hashing are data-independent MHFs (iMHFs) as they enjoy a natural resistance to certain side channel attacks which might otherwise leak information about the user’s password. An iMHF can be specified by fixing a directed acyclic graph (DAG) G_n on n nodes of constant indegree and a single sink node n. G_n represents the data-dependency graph between intermediate calls to an underlying hash function during the computation of the iMHF and node n represents final output.

This talk will overview recent results demonstrating that a combinatorial property called depth-robustness fully characterizes iMHFs with high amortized ST-cost. On the positive side we construct a family of DAGs G_n with ST-cost at least $\Omega(n^2/log(n))$. We also show that any iMHF has amortized ST-cost at most $O(n^2 log(log(n))/log(n))$ so our construction is nearly optimal in an asymptotic sense. On the negative side we show that Argon2i, the winner of the password hashing competition, is defined using a directed acyclic graph G_n that is not depth-robust and can be computed by an algorithm with low amortized ST-cost $O(n^{1.71})$. The resulting attacks are practical for realistic settings of the Argon2i parameters.

Based on joint works with Joel Alwen and Krzysztof Pietrzak.