Friday October 24, 2014 at MIT

The Charles River Crypto Day is back! We now plan to make it a regular event held about once every two months. Please join us on Friday, October 24 at MIT for the first Crypto Day of 2014-2015.

Location: MIT Stata Center Building 32 Gates Tower, 8th floor Room G-882 (Hewlett).


9:00 – 9:30. Introduction/Coffee
9:30 – 10:30.
Ron Rivest, MIT
Spritz—A spongy RC4-like stream cipher and hash function
11:00 – 12:00. Allison Bishop Lewko, Columbia
Witness Encryption and Indistinguishability Obfuscation from the Multilinear Subgroup Elimination Assumption
12:00 – 2:00. Lunch (provided)
2:00 – 3:00. Alessandro Chiesa, ETH Zurich
Scalable Zero Knowledge via Cycles of Elliptic Curves
3:30 – 4:30. Alon Rosen, IDC Herzlia
An Algebraic Approach to Non-Malleability


Speaker: Ron Rivest (MIT)
Title/Abstract:  Spritz—A spongy RC4-like stream cipher and hash function

Abtract: We reconsider the design of the stream cipher RC4, and proposes an improved variant, which we call “Spritz”.

Our work leverages the considerable cryptanalytic work done on the original RC4 and its proposed variants. It also uses simulations extensively to search for biases and to guide the selection of intermediate expressions.

We estimate that Spritz can produce output with about 24 cycles/byte of computation. Furthermore, our statistical tests suggest that about 2^81 bytes of output are needed before one can reasonably distinguish Spritz output from random output; this is a marked improvement over RC4.

In addition, we formulate Spritz as a “sponge (or sponge-like) function,” (see Bertoni et al), which can Absorb new data at any time, and from which one can Squeeze pseudorandom output sequences of arbitrary length. Spritz can thus be easily adapted for use as a cryptographic hash function, an encryption algorithm, or a message-authentication code generator. (However, in hash-function mode, Spritz is rather slow.)

Joint work with Jacob Schuldt.

Speaker: Allison Bishop Lewko (Cloumbia U)
Title: Witness encryption and indistinguishability obfuscation from the multilinear subgroup elimination assumption

We present constructions of witness encryption and indistinguishability obfuscation along with security reductions to the multilinear subgroup elimination assumption. This assumption is a natural multilinear extension of the subgroup decision assumptions used in bilineargroups.

This talk is based on joint works with Gentry and Waters and with Gentry, Sahai and Waters.

Speaker: Alessandro Chiesa (ETH Zurich)
Title: Scalable Zero Knowledge via Cycles of Elliptic Curves

Abstract: Non-interactive zero-knowledge proofs for general NP statements are a powerful cryptographic primitive. Recent work has achieved theoretical constructions and working implementations of zero-knowledge proofs that are short and easy to verify.

Alas, all prior implementations suffer from severe scalability limitations: the proving key’s size and the prover’s space complexity grow with the size of the computation being proved.

The bootstrapping technique of Bitansky et al. (STOC 2013), following Valiant (TCC 2008), offers an approach to scalability, by recursively composing proofs, but it has never been realized in practice, due to enormous computational cost.

In this work, by leveraging new elliptic-curve cryptographic techniques, we achieve the first practical implementation of recursive proof composition, and thereby achieve the first implementation of *scalable zero knowledge*.

Joint work with Eli Ben-Sasson, Eran Tromer, and Madars Virza.

Speaker: Alon Rosen (IDC Herzliya)
Title: An Algebraic Approach to Non-Malleability

Abstract: I will present a new technique for constructing non-malleable protocols with only a single “slot”. Two direct byproducts of our ideas are a four round non-malleable commitment and a four round non-malleable zero-knowledge argument, the latter matching the round complexity of the best known zero-knowledge arguments (without the non-malleability requirement). The protocols are based on the existence of one-way functions and admit very efficient instantiations via standard homomorphic commitments and sigma protocols.

Our analysis relies on algebraic reasoning, and makes use of error correcting codes in order to ensure that committers’ tags differ in many coordinates. One way of viewing our construction is as a method for combining many atomic sub-protocols in a way that simultaneously amplifies soundness and non-malleability, thus requiring much weaker guarantees to begin with, and resulting in a protocol which is much trimmer in complexity compared to the existing ones.

Joint work with Vipul Goyal, Silas Richelson and Margarita Vald.

Comments are closed.

%d bloggers like this: