# CryptoDay at NYU

Nov 15, 2013 (Friday) at NYU (Broadway 719, Room 1221)

Program

 10:30 – 11:00. Introduction/Coffee 11:00 – 11:50. Alessandro Chiesa, MIT SNARKs for C: Verifying Program Executions Succinctly and in Zero-Knowledge. 12:00 – 12:50. Bhavana Kanukurthi, UCLA Locally Updatable and Locally Decodable Codes 1:00 – 3:00. Lunch (not provided) 3:00 – 3:50. Mahdi Cheraghchi, MIT Capacity and Constructions of Non-Malleable Codes. 4:00 – 4:50. Adi Shamir, Weizmann Institute Quantitative Analysis of the Full Bitcoin Transaction Graph

Getting Here

google maps | official directions | restaurants on yelp | coffee ]

Organizers

Tal Rabin (IBM) and Sanjam Garg (IBM)
with the help and support of Yevgeniy Dodis (NYU).

Abstracts

• SNARKs for C: Verifying Program Executions Succinctly and in Zero Knowledge
Alessandro Chiesa (MIT)

Theoretical results in cryptography provide various techniques for outsourcing computation with strong integrity and confidentiality guarantees. Yet, these techniques continue to suffer from high overheads in the general case.

In this work, we significantly reduce the aforementioned costs via a combination of new theoretical and engineering techniques. Concretely, we present a new system for proving the correctness of high-level program executions. Proofs in our system are non-interactive, short (less than 300 bytes), and can be verified publicly in milliseconds. Moreover, our proofs are zero-knowledge proofs of knowledge.

Our work raises additional intriguing mathematical questions, whose solutions could push outsourced computation even further.

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

• Locally Updatable and Locally Decodable Codes
Bhavana Kanukurthi (UCLA)

We introduce the notion of locally updatable and locally decodable codes (LULDCs). In addition to having low decode locality, such codes allow us to update a codeword (of a message) to a codeword of a different message, by rewriting just a few symbols. While, intuitively, updatability and error-correction seem to be contrasting goals, we show that for a suitable, yet meaningful, metric (which we call the Prefix Hamming metric), one can construct such codes. Informally, the Prefix Hamming metric allows the adversary to arbitrarily corrupt bits of the codeword subject to one constraint — he does not corrupt more than a $\delta$ fraction of the $t$ “most-recently changed” bits of the codeword (for all $1 \leq t \leq n$, where $n$ is the length of the codeword).

Our results are as follows. First, we construct binary LULDCs for messages in ${0,1}^k$ with constant rate, update locality of $O(log^2 k)$, and read locality of $O(k^\epsilon)$ for any constant $\epsilon<1$. Next, we consider the case where the encoder and decoder share a secret state and the adversary is computationally bounded. Here too, we obtain local updatability and decodability for the Prefix Hamming metric. Furthermore, we also ensure that the local decoding algorithm never outputs an incorrect message — even when the adversary can corrupt an arbitrary number of bits of the codeword. We call such codes locally updatable locally decodable-detectable codes (LULDDCs) and obtain dramatic improvements in the parameters (over the information-theoretic setting). Our codes have constant rate, an update locality of $O(log k)$ and a read locality of $O(\lambda log^2 k)$, where $\lambda$ is the security parameter.

Finally, we show how our techniques apply to the setting of dynamic proofs of retrievability (DPoR) and present a construction of this primitive with better parameters than existing constructions. In particular, we construct a DPoR scheme with linear storage, $O(log k)$ write complexity, and $O(\lambda log k)$ read and audit complexity.

This is joint work with Nishanth Chandran and Rafail Ostrovsky.

•  Capacity and Constructions of Non-Malleable Codes
Mahdi Cheraghchi (MIT)

Non-malleable codes, introduced by Dziembowski, Pietrzak and Wichs (ICS 2010) and motivated by applications in tamper-resilient cryptography, encode messages in a manner so that tampering the codeword causes the decoder to either output the correct message or an uncorrelated message. While this relaxation of error detection is an impossible goal to achieve against unrestricted tampering functions, rather surprisingly non-malleable coding becomes possible against every fixed family of tampering functions that is not too large.In this talk, I will address the following questions:

1. “Capacity” of non-malleable codes: For any tampering family of a prescribed size, we derive an explicit lower bound on the maximum possible rate of a non-malleable code against the given family. Furthermore, we show that this bound is essentially optimal.
2. I describe an efficient Monte-Carlo construction of non-malleable codes against any family of tampering functions of exponential size (e.g., polynomial-sized Boolean circuits). Codes obtained by this construction achieve rates arbitrarily close to 1 and do not rely on any unproven assumptions.
3. We study the specific family of bit-tampering adversaries, that is adversaries that independently act on each encoded bit. For this family, we are able to obtain an explicit construction of non-malleable codes achieving rate arbitrarily close to 1.

Based on joint work with Venkatesan Guruswami and articles arXiv:1309.0458 and arXiv:1309.1151.

• Quantitative Analysis of the Full Bitcoin Transaction Graph