Monthly Archives: November 2016

Dec 16, 2016 (Friday) in Manhattan at Stony Brook Manhattan, Room 321B, 3rd Floor, 387 Park Avenue South, New York, NY.


9:30 – 10:00. Introduction/Coffee
10:00 – 10:50. Vinod Vaikuntanathan (MIT)
Low-Complexity Cryptographic Hash Functions
11:00 – 11:50. Chaya Ganesh (NYU)
Efficient Zero-Knowledge Proof of Algebraic and Non-Algebraic 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 Large-Scale Consensus through Blockchains


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]


Fabrice Benhamouda (IBM Research)
Tal Rabin (IBM Research)

Omkant Pandey (Stony Brook University)


Some travel support for NYC Crypto Day is provided by DIMACS/Simons Collaboration in Cryptography through NSF grant #CNS-1523467.


  • Low-Complexity 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:

    * Low-complexity CRH. Assuming the intractability of finding short codewords in natural families of linear error-correcting 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 linear-size circuits.* Win-win results. If low-degree CRH with good shrinkage do not exist, this has useful consequences for learning algorithms and data structures.

    * Degree-2 hash functions. Assuming the conjectured intractability of solving a random system of quadratic equations over Z2, a uniformly random degree-2 mapping is a universal one-way 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 degree-2 mapping is not a CRH. We leave the existence of degree-2 CRH open, and relate it to open questions on the existence of degree-2 randomized encodings of functions.

    Joint work with Benny Applebaum, Naama Haramaty, Yuval Ishai and Eyal Kushilevitz, to appear in ITCS 2017.

  • Efficient Zero-Knowledge Proof of Algebraic and Non-Algebraic Statements with Applications to Privacy Preserving Credentials / Chaya Ganesh (NYU)
    Practical anonymous credential systems are generally built around sigma-protocol 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 discrete-log, 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 non-algebraic statements and that of sigma protocols for algebraic ones. We then show how to use these as building-blocks to construct privacy-preserving 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 two-party 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 zero-knowledge so that, for example, an authenticated cropped image reveals nothing about the cropped-out regions.

    PhotoProof is based on Proof-Carrying Data (PCD), a cryptographic primitive for secure execution of distributed computations, built on top of zkSNARK proofs.

    Joint with with Assa Naveh.

  • Rethinking Large-Scale 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 “large-scale” 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 “proofs-of-work”).

    Based on joint work with Iddo Bentov and Elaine Shi.

%d bloggers like this: