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 ZeroKnowledge.

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 NonMalleable Codes. 
4:00 – 4:50.  Adi Shamir, Weizmann Institute Quantitative Analysis of the Full Bitcoin Transaction Graph 
Getting Here
Address: Broadway 719
[ 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 highlevel program executions. Proofs in our system are noninteractive, short (less than 300 bytes), and can be verified publicly in milliseconds. Moreover, our proofs are zeroknowledge proofs of knowledge.
Our work raises additional intriguing mathematical questions, whose solutions could push outsourced computation even further.
Joint work with Eli BenSasson, 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 errorcorrection 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$ “mostrecently 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 decodabledetectable codes (LULDDCs) and obtain dramatic improvements in the parameters (over the informationtheoretic 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 NonMalleable Codes
Mahdi Cheraghchi (MIT)Nonmalleable codes, introduced by Dziembowski, Pietrzak and Wichs (ICS 2010) and motivated by applications in tamperresilient 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 nonmalleable 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 nonmalleable codes: For any tampering family of a prescribed size, we derive an explicit lower bound on the maximum possible rate of a nonmalleable code against the given family. Furthermore, we show that this bound is essentially optimal.2. I describe an efficient MonteCarlo construction of nonmalleable codes against any family of tampering functions of exponential size (e.g., polynomialsized 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 bittampering adversaries, that is adversaries that independently act on each encoded bit. For this family, we are able to obtain an explicit construction of nonmalleable 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
Adi Shamir (Weizmann Institute)The Bitcoin scheme is a rare example of a large scale global payment system in which all the transactions are publicly accessible (but in an anonymous way). We downloaded the full history of this scheme, and analyzed its associated transaction graph in order to answer a variety of interesting questions about the typical behavior of users, how they acquire and how they spend their bitcoins, the balance of bitcoins they keep in their accounts, and how they move bitcoins between their various accounts in order to better protect their privacy. In addition, we isolated all the large transactions in the system, and discovered that almost all of them are closely related to a single large transaction that took place in November 2010, even though the associated users apparently tried to hide this fact with many strange looking long chains and forkmerge structures in the transaction graph.
Joint work with Dorit Ron.