Monthly Archives: February 2018

When: Friday, Feb 16 at MIT.

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

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

Thanks: NSF MACS Project for their generous support.


9:30 – 10:00. Coffee/Welcome
10:00 – 11:00.
Siyao Guo, Northeastern University
Random Oracles and Non-Uniformity
11:15 – 12:15. Muthuramakrishnan Venkitasubramaniam, University of Rochester
Ligero: Lightweight Sublinear Zero-Knowledge Arguments
12:15 – 1:30. Lunch
1:30 – 2:30. Yael Kalai, MSR and MIT
Non-Interactive Delegation for Low-Space Non-Deterministic Computation
2:45 – 3:45. Daniel Genkin, UPenn
Spectre and Meltdown: Speculative Execution Considered Harmful


Speaker: Siyao Guo, Northeastern University
Title: Random Oracles and Non-Uniformity

Abstract: We revisit security proofs for various cryptographic primitives in the {\em auxiliary-input random oracle model} (AI-ROM), in which an attacker can compute arbitrary $S$ bits of leakage about the random oracle $O$ before attacking the system and then use additional $T$ oracle queries to $O$ during the attack. This model was explicitly studied by Unruh (CRYPTO 2007) but dates back to the seminal paper of Hellman in 1980 about time-space tradeoffs for inverting random functions, and has natural applications in settings where traditional random oracle proofs are not useful: (a) security against non-uniform attackers; (b) security against preprocessing.

We obtain a number of new results about the AI-ROM:

(1) Unruh introduced the {\em pre-sampling technique}, which generically reduces security proofs in the AI-ROM to those in a much simpler {\em $P$-bit-fixing random oracle model} (BF-ROM), where the attacker can arbitrarily fix the values of $O$ on some $P$ coordinates, but then the remaining coordinates are chosen at random. Unruh’s security loss for this transformation is $\sqrt{ST/P}$. We improve this loss to the {\em optimal} value $O(ST/P)$, which implies nearly tight security bounds for a variety of indistinguishability applications in the AI-ROM.

(2) While the basic pre-sampling technique cannot give tight bounds for unpredictability applications, we introduce a novel “mutiplicative version” of pre-sampling, which allows to dramatically reduce the size of $P$ of the pre-sampled set (namely, $P=O(ST)$), and yields nearly tight security bounds for a variety of unpredictability applications in the AI-ROM. Qualitatively, it validates Unruh’s “polynomial pre-sampling conjecture”—disproved in general by Dodis \etal (Eurocrypt 2017)—for the special case of unpredictability applications.

(3) Finally, we build two general compilers showing how to generically extend the security of applications proven in the traditional ROM to the AI-ROM. One compiler simply prepends a public salt to the random oracle and shows that {\em salting generically provably defeats preprocessing}.

Overall, or results makes it much easier to get concrete security bounds in the AI-ROM. These bounds in turn give concrete conjectures about the security of these applications (in the standard model) against {\em non-uniform} attackers.

Joint work with Sandro Coretti, Yevgeniy Dodis and John Steinberger.

Speaker: Muthuramakrishnan Venkitasubramaniam, University of Rochester
Title:  Ligero: Lightweight Sublinear Zero-Knowledge Arguments

Abstract: Succinct non-interactive zero-knowledge (ZK) argument of knowledge or zk-SNARKs, a variant of ZK proof systems, have recently gained a lot of attention as a tool that enables anonymity and integrity in blockchain technologies and forms the backbone of the Zcash cryptocurrency. However, the current (efficient) solutions either rely on trusted setup or make heavy use of public-key primitives and/or complex combinatorial objects (eg, probabilistically checkable proofs).

We design and implement a simple zero-knowledge argument protocol for arbitrary statements (i.e., NP) whose communication complexity is proportional to the square-root of the verification circuit size. The protocol can be based on any collision-resistant hash function. Alternatively, it can be made non-interactive in the random oracle model, yielding concretely efficient zk-SNARKs that do not require a trusted setup or public-key cryptography.

Our protocol is attractive not only for very large verification circuits but also for moderately large circuits (Boolean or Arithmetic) that arise in applications. For instance, for verifying a SHA-256 preimage in zero-knowledge with 2^{-40} soundness error, the proof length is 34KB, the prover running time is 140 ms, and the verifier running time is 62 ms. This proof is roughly 5 times shorter than a similar proof of ZKB++ (Chase et al., CCS 2017), an optimized variant of ZKBoo (Giacomelli et al., USENIX 2016).

I will describe some applications where our zero-knowledge argument will improve the state-of-the-art and present some on-going work.

Based on joint works with Scott Ames, Carmit Hazay, and Yuval Ishai

Speaker: Yael Kalai, MSR and MIT
Title:  Non-Interactive Delegation for Low-Space Non-Deterministic Computation

Abstract: We construct a delegation scheme for verifying *non-deterministic* computations, with complexity proportional only to the non-deterministic space of the computation.  Specifically, letting n denote the input length, we construct a delegation scheme for any language verifiable in non-deterministic time and space (T(n), S(n)), with communication complexity poly(S(n)), verifier runtime n*polylog(T(n))+poly(S(n)), and prover runtime poly(T(n)).

Our scheme consists of only two messages and has adaptive soundness, assuming the existence of a sub-exponentially secure private information retrieval (PIR) scheme, which can be instantiated under the sub-exponential LWE assumption.

Specifically, the verifier publishes a (short) public key ahead of time, and this key can be used by any prover to *non-interactively* prove the correctness of any *adaptively chosen* non-deterministic computation.  Our scheme is privately verifiable, where the verifier needs the corresponding secret key in order to verify proofs.
This is joint work with Saikrishna Badrinarayanan, Dakshita Khurana, Amit Sahai, and Daniel Wichs.

Speaker: Daniel Genkin, UPenn
Title:  Spectre and Meltdown: Speculative Execution Considered Harmful

Abstract: This talk presents Spectre and Meltdown, two new microarchitectural attacks that exploit speculative execution of instructions to leak sensitive information from computer systems. The talk discusses the mechanisms employed by the attacks, initial countermeasures and the implications on secure software design. 

This is a joint work with Anders Fogh, Daniel Gruss, Werner Haas, Mike Hamburg, Jann Horn, Paul Kocher, Moritz Lipp, Stefan Mangard, Thomas Prescher, and Michael Schwarz and Yuval Yarom