CryptoDay in Manhattan @ Stony Brook – Manhattan campus, Friday Dec 16, 2016
Dec 16, 2016 (Friday) in Manhattan at Stony Brook Manhattan, Room 321B, 3rd Floor, 387 Park Avenue South, New York, NY.
Program
9:30 – 10:00.  Introduction/Coffee 
10:00 – 10:50.  Vinod Vaikuntanathan (MIT) LowComplexity Cryptographic Hash Functions 
11:00 – 11:50.  Chaya Ganesh (NYU) Efficient ZeroKnowledge Proof of Algebraic and NonAlgebraic Statements with Applications to Privacy Preserving Credentials 
12:00 – 2:00.  Lunch (not provided) 
2:00 – 2:50.  Eran Tromer (Tel Aviv University and Columbia University) PhotoProof: Cryptographic Image Authentication for Any Set of Permissible Transformations 
3:00 – 3:50.  Rafael Pass (Cornell Tech) Rethinking LargeScale Consensus through Blockchains 
Venue
Address: Stony Brook Manhattan, Room 321B, 3rd Floor, 387 Park Avenue South, New York, NY. Enter on East 27th Street (beneath university banner, doors marked 387 Park Avenue South).
[Visitor Information] [Google Maps]
Organizers
Fabrice Benhamouda (IBM Research)
Tal Rabin (IBM Research)
Omkant Pandey (Stony Brook University)
Support
Some travel support for NYC Crypto Day is provided by DIMACS/Simons Collaboration in Cryptography through NSF grant #CNS1523467.
Abstracts

LowComplexity Cryptographic Hash Functions / Vinod Vaikuntanathan (MIT)
Cryptographic hash functions are efficiently computable functions that shrink a long input into a shorter output while achieving some of the useful security properties of a random function. The most common type of such hash functions is collision resistant hash functions (CRH), which prevent an efficient attacker from finding a pair of inputs on which the function has the same output.Despite the ubiquitous role of hash functions in cryptography, several of the most basic questions regarding their computational and algebraic complexity remained open. In this work we settle most of these questions under new, but arguably quite conservative, cryptographic assumptions, whose study may be of independent interest.
Concretely, we obtain the following results:
* Lowcomplexity CRH. Assuming the intractability of finding short codewords in natural families of linear errorcorrecting codes, there are CRH that shrink the input by a constant factor and have a constant algebraic degree over Z2 (as low as 3), or even constant output locality and input locality. Alternatively, CRH with an arbitrary polynomial shrinkage can be computed by linearsize circuits.* Winwin results. If lowdegree CRH with good shrinkage do not exist, this has useful consequences for learning algorithms and data structures.
* Degree2 hash functions. Assuming the conjectured intractability of solving a random system of quadratic equations over Z2, a uniformly random degree2 mapping is a universal oneway hash function (UOWHF). UOWHF relaxes CRH by forcing the attacker to find a collision with a random input picked by a challenger. On the other hand, a uniformly random degree2 mapping is not a CRH. We leave the existence of degree2 CRH open, and relate it to open questions on the existence of degree2 randomized encodings of functions.
Joint work with Benny Applebaum, Naama Haramaty, Yuval Ishai and Eyal Kushilevitz, to appear in ITCS 2017.
 Efficient ZeroKnowledge Proof of Algebraic and NonAlgebraic Statements with Applications to Privacy Preserving Credentials / Chaya Ganesh (NYU)
Practical anonymous credential systems are generally built around sigmaprotocol ZK proofs. This requires that credentials be based on specially formed signatures. In this work, we ask whether we can instead use a standard (say, RSA, or (EC)DSA) signature that includes formatting and hashing messages, as a credential, and still provide privacy. Existing techniques do not provide efficient solutions for proving knowledge of such a signature: On the one hand, ZK proofs based on garbled circuits (Jawurek et al. 2013) give efficient proofs for checking formatting of messages and evaluating hash functions. On the other hand they are expensive for checking algebraic relations such as RSA or discretelog, which can be done efficiently with sigma protocols. We design new constructions obtaining the best of both worlds: combining the efficiency of the garbled circuit approach for nonalgebraic statements and that of sigma protocols for algebraic ones. We then show how to use these as buildingblocks to construct privacypreserving credential systems based on standard RSA and (EC)DSA signatures.Other applications of our techniques include anonymous credentials with more complex policies, the ability to efficiently switch between commitments (and signatures) in different groups, and secure twoparty computation on committed/signed inputs.Joint work with Melissa Chase and Payman Mohassel.

PhotoProof: Cryptographic Image Authentication for Any Set of Permissible Transformations / Eran Tromer (Tel Aviv University and Columbia University)
Authenticating images that claim to depict real events is desirable in many applications. While some commercial cameras already attach digital signatures to photographs, plain signatures are invalidated by desirable transformations such as cropping, rotation, compression.
This presents PhotoProof, a novel approach to image authentication based on cryptographic proofs. It can be configured, according to application requirements, to allow any permissible set of (efficiently computable) transformations. Starting with a signed image, our scheme attaches, to each legitimately derived image, a succinct proof of computational integrity attesting that the transformation was permissible. Anyone can verify these proofs, and generate updated proofs when applying further permissible transformations. Moreover, the proofs are zeroknowledge so that, for example, an authenticated cropped image reveals nothing about the croppedout regions.
PhotoProof is based on ProofCarrying Data (PCD), a cryptographic primitive for secure execution of distributed computations, built on top of zkSNARK proofs.
Joint with with Assa Naveh.
 Rethinking LargeScale Consensus through Blockchains / Rafael Pass (Cornell Tech)
The literature on distributed computing (as well as the cryptographic literature) typically considers two types of players—honest ones and corrupted ones. Resilience properties are then analyzed assuming a lower bound on the fraction of honest players. Honest players, however, are not only assumed to follow the prescribed the protocol, but also assumed to be online throughout the whole execution of the protocol.The advent of “largescale” consensus protocols (such as e.g., the blockchain protocol) where we may have millions of players, makes this assumption unrealistic. In this work, we initiate a study of distributed protocols in a “sleepy” model of computation, where players can be either online (awake) or offline (asleep), and their online status may change at any point during the protocol. The main question we address is:Can we design consensus protocols that remain resilient under “sporadic participation”, where at any given point, only a subset the players are actually online?As far as we know, all standard consensus protocols break down under such sporadic participation, even if we assume that 99% of the online players are honest. Our main result answers the above question in the affirmative, assuming only that a majority of the online players are honest. Perhaps surprisingly, our protocol significantly departs from the standard approaches to distributed consensus, and we instead rely on key ideas behind Nakamoto’s blockchain protocol (while dispensing with “proofsofwork”).Based on joint work with Iddo Bentov and Elaine Shi.