— nycryptoday Crypto is the deadliest Espresso
Home About
Search
Related events
Archive
Oblivious RAM
CryptoDay at NYU
Nov 15, 2013 (Friday) at NYU (Broadway 719, Room 1221)
October 14, 2013 Anonymity, Error Correction, Non-Malleability, Oblivious RAM, Succinct Arguments
Program 10:30 – 11:00.
Introduction/Coffee
11:00 – 11:50.
Alessandro Chiesa, MIT SNARKs for C: Verifying Program Executions Succinctly and in ZeroKnowledge.
Leave a comment
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.
Charles River Crypto Day DC Area Crypto Day Bay Area Crypto Day London Crypto Day Paris Crypto Day GTACS Tokyo Crypto Day
Previous CryptoDays February 2018 November 2017 August 2017 May 2017 March 2017 January 2017 November 2016 September 2016 April 2016 February 2016 December 2015 September 2015 January 2015 October 2014 June 2014 May 2014 March 2014 January 2014 October 2013 September 2013 July 2013 March 2013 January 2013 December 2012 September 2012 July 2012 June 2012 April 2012 March 2012 January 2012 November 2011 July 2011 June 2011 May 2011 January 2011 October 2010 September 2010 April 2010 March 2010
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.
Report this ad
Report this ad
Share this: Twitter
Facebook
Like Be the first to like this.
Older posts
Blog at WordPress.com.
Google
Report this ad
