New York Area Theory Day

9:30 - 10:00 Coffee and bagels

10:00 - 10:55 Dr. Tal Rabin

              Advancing theory towards practice--the story of threshold cryptography

10:55 - 11:05 Short break

11:05 - 12:00 Dr. Sepehr Assadi

              Sublinear Algorithms for (Delta+1) Vertex Coloring

12:00 - 2:00 Lunch break

 2:00 - 2:55 Prof. Mark Zhandry

             Quantum Lightning Never Strikes the Same State Twice

 2:55 - 3:15 Coffee break

 3:15 - 4:10 Prof. Omri Weinstein

             Lower Bounds for Oblivious Near-Neighbor Search

 4:30 - 5:30 Follow-up social (location TBD)

For directions, please see here

To subscribe to our mailing list, follow instructions here

Organizers:

Alex Andoni
Yevgeniy Dodis
Krzysztof Onak

==================================================================
                             ABSTRACTS  
==================================================================

Dr. Tal Rabin (Algorand Foundation)

Advancing theory towards practice--the story of threshold cryptography

NIST (National Institute of Standards and Technology) has initiated an effort

to standardize Threshold Cryptography. In this talk we will explain the notion

of threshold cryptography, its uses and a proposal for the standard.

Based on work with Christian Cachin, Hugo Krawczyk, Jason Resch and Chrysoula Stathakopoulou.

==================================================================

Dr. Sepehr Assadi (Princeton University)

Sublinear Algorithms for (Delta+1) Vertex Coloring

In this talk, we will examine a classical graph coloring problem through

the lens of sublinear algorithms  these are algorithms that use computational

resources that are substantially smaller than the size of the input on which

they operate. It is well-known that any graph with maximum degree Delta admits

a proper vertex coloring with (Delta + 1) colors that can be found via

a simple sequential greedy algorithm in linear time and space. But can one

Find such a coloring via a sublinear algorithm? We will present results that

answer this question in the affirmative for several well-studied models of

sublinear computation, most notably, graph streaming and sublinear time

algorithms. We obtain these results by proving a palette sparsification

theorem which says that if every vertex independently samples O(log n) colors

from the available Delta+1 colors, then almost certainly a (Delta + 1)

coloring can be found using only the sampled colors. We then show that this

palette sparsification theorem naturally leads to essentially optimal

sublinear algorithms in the above-mentioned models of computation.

Based on joint work with Yu Chen and Sanjeev Khanna.

==================================================================

Prof. Mark Zhandry (Princeton University)

Quantum Lightning Never Strikes the Same State Twice

Public key quantum money can be seen as a version of the quantum no-cloning

theorem that holds even when the quantum states can be verified by the

adversary. In this work, we investigate quantum lightning, where no-cloning

holds even when the adversary herself generates the quantum state to be

cloned. We then study quantum money and quantum lightning, showing the

following results:

  - We demonstrate the usefulness of quantum lightning beyond quantum money

    by showing several potential applications, such as generating random

    strings with a proof of entropy, to completely decentralized

    cryptocurrency without a block-chain, where transactions is instant

    and local.

  - We give Either/Or results for quantum money/lightning, showing that either

    signatures/hash functions/commitment schemes meet very strong recently

    proposed notions of security, or they yield quantum money or lightning.

    Given the difficulty in constructing public key quantum money, this

    suggests that natural schemes do attain strong security guarantees.

  - We show that instantiating the quantum money scheme of Aaronson and

    Christiano [STOC'12] with indistinguishability obfuscation that is secure

    against quantum computers yields a secure quantum money scheme. This

    construction can be seen as an instance of our Either/Or result for

    signatures, giving the first separation between two security notions

    for signatures from the literature.  

  - Finally, we give a plausible construction for quantum lightning, which

    we prove secure under an assumption related to the multi-collision

    resistance of degree-2 hash functions. Our construction is inspired by

    our Either/Or result for hash functions, and yields the first plausible

    standard model instantiation of a non-collapsing collision resistant hash

    function. This improves on a result of Unruh [Eurocrypt'16] which is

    relative to a quantum oracle.

==================================================================

Prof. Omri Weinstein (Columbia University)

Lower Bounds for Oblivious Near-Neighbor Search

We prove an ~Omega(d*log n) lower bound on the dynamic cell-probe complexity

of statistically *oblivious*  approximate-near-neighbor search (ANN) over

the d-dimensional Hamming cube. For the natural setting of d =~ (log n),

our result implies a ~ log^2(n) lower bound, which is a quadratic improvement

over the highest (non-oblivious) cell-probe lower bound known for ANN. This

is the first super-logarithmic *unconditional* lower bound for ANN against

general (non black-box) data structures.

We also show that any oblivious static data structure for decomposable

Search problems (like ANN) can be obliviously "dynamized" with O(log n)

overhead in update and query time, strengthening a classic result of

Bentley and Saxe (Algorithmica, 1980).

Joint work with Kasper Green Larsen, Tal Malkin and Kevin Yeo.

==================================================================

Back to New York Area Theory Day