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

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 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
  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 fork-merge structures in the transaction graph.

  Joint work with Dorit Ron.