Monthly Archives: November 2017

Dec 8, 2017 (Friday) at City College (CUNY), NAC Ballroom, New York, NY.


9:30 – 10:00. Introduction/Coffee
10:00 – 10:50. Roei Schuster (Tel Aviv University / Cornell Tech)
Beauty and the Burst: Remote Identification of Encrypted Video Streams
11:00 – 11:50. Yael Kalai (Microsoft Research)
The virtues of two-message OT
12:00 – 2:00. Lunch (not provided)
2:00 – 2:50. Alexander Russell (University of Connecticut)
Ouroboros: A Provably-Secure Proof-of-Stake Blockchain
3:00 – 3:50. Henry Corrigan-Gibbs (Stanford)
The discrete-logarithm problem with preprocessing


Address: City College (CUNY), North Academic Center, NAC Ballroom, 1605 Amsterdam Ave, New York, NY.

You can come in from either side of the building (Amsterdam avenue or Convent avenue), the room is in the ground floor next to the Convent avenue entrance. If you come in from Amsterdam you are on the third floor and need to come he ground floor.

[Visitor Information] [Google Maps]


Fabrice Benhamouda (IBM Research)
Tal Rabin (IBM Research)
with the help and support of Rosario Gennaro (CUNY).


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


  • Beauty and the Burst: Remote Identification of Encrypted Video Streams / Roei Schuster (Tel Aviv University / Cornell Tech)The MPEG-DASH streaming video standard contains an information leak: even if the stream is encrypted, the segmentation prescribed by the standard causes content-dependent packet bursts. We show that many video streams are uniquely characterized by their burst patterns, and classifiers based on convolutional neural networks can accurately identify these patterns given very coarse network measurements. We demonstrate that this attack can be performed even by a Web attacker who does not directly observe the stream, e.g., a JavaScript ad confined in a Web browser on a nearby machine.

    Joint work with Vitaly Shmatikov and Eran Tromer.

  • The virtues of two-message OT / Yael Kalai (Microsoft Research)In this talk I will present techniques that use two-message oblivious transfer (OT) to construct two-message arguments with strong privacy guarantees.

    Specifically, assuming polynomial security of the OT scheme, we construct a two-message argument that is witness indistinguishable, and in the delayed-input setting it is distributional weak zero-knowledge, strong witness indistinguishable and witness hiding.
    Moreover, assuming a super-polynomial secure OT scheme, we construct a two-message argument with (similar) *statistical* secrecy guarantees.

    This is based on joint works with Abhishek Jain, Dakshita Khurana, Ron Rothblum and Amit Sahai.

  • Ouroboros: A Provably-Secure Proof-of-Stake Blockchain / Alexander Russell (University of Connecticut)This talk will introduce Ouroboros, a proof-of-stake blockchain that
    provides security guarantees analogous to those offered by Bitcoin.
    Specifically, we establish rigorous notions of liveness and persistence
    so long as honest parties hold a majority of the stake. In general,
    proof-of-stake blockchains must overcome a fundamental hurdle: robustly
    “electing” the participant responsible for producing each new block.
    Ouroboros addresses this challenge by running a lightweight multi-party
    computation, using the blockchain itself as a communication medium. In
    contrast to “online” blockchains–such as Bitcoin–the Ouroboros
    election mechanism determines the winners of this election to many
    blocks at a time. This provides potential adversaries with a novel means
    of attack and leads to a combinatorial security analysis that controls
    the various blockchain forkings that can be produced by an adversary
    with such strong knowledge of the future.
  • The discrete-logarithm problem with preprocessing / Henry Corrigan-Gibbs (Stanford)We study discrete-log algorithms that use preprocessing. In our model,
    an adversary may use a very large amount of precomputation to produce an
    “advice” string about a specific group (e.g., NIST P-256). In a
    subsequent online phase, the adversary’s task is to use the preprocessed
    advice to quickly compute discrete logarithms in the group. Motivated by
    surprising recent preprocessing attacks on the discrete-log problem, we
    study the power and limits of such algorithms.

    In particular, we focus on generic algorithms that operate in every
    cyclic group. We show a lower bound on the success probability of any
    generic discrete-log algorithm with preprocessing. Our lower bound,
    which is tight up to logarithmic factors, uses a synthesis of
    incompressibility techniques and classic methods for generic-group lower
    bounds. We apply our techniques to prove related lower bounds for the
    CDH, DDH, and multiple-discrete-log problems.

    Finally, we demonstrate two new generic preprocessing attacks: one for
    the multiple-discrete-log problem and one for certain decisional-type
    problems in groups. This latter result demonstrates that, for generic
    algorithms with preprocessing, distinguishing tuples of the form [g,
    g^x, g^(x^2)] from random is much easier than the discrete-log problem.

    This talk is based on joint work with Dmitry Kogan.


%d bloggers like this: