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.
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.
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.