Important: Registration is free but mandatory. Registration deadline: May 26, 2026, 08:00 AM.

May 29, 2026 (Friday) at Room 150 in 60 5th Ave, New York, NY 10031.

Program

09:00 – 10:00.	Introduction/Coffee
10:00 – 10:50.	Noam Mazor (NYU) Cryptographic Implications of Worst-Case Hardness of Time-Bounded Kolmogorov Complexity
11:00 – 11:50.	Eugene Bagdasarian (UMass Amherst) Towards the Universe of Trustworthy AI Agents
12:00 – 02:00.	Lunch
02:00 – 02:50.	Fatima Elsheimy (Yale University) Optimal Best-of-Both-Worlds Consensus
03:00 – 03:50.	Kameron Shahabi (University of Washington) Unforgeable and Recoverable Watermarks for Language Models via Robust Signatures

Registration Very important

Registration is free but mandatory.
Registration deadline: May 26, 2026, 08:00 (ET).
Only registered participants will be allowed to enter.

Venue

Address: Room 150 in 60 5th Ave, New York, NY 10031.

NYU Center for Data Science

[Directions]

Organizers

Fabrice Benhamouda (Amazon Web Services)
Daniel Escudero (TACEO)
Tal Rabin (Amazon Web Services)
Mariana Raykova (Google)
with the help and support of Nir Bitansky.

Support

NY CryptoDay is sponsored by Google and the Courant Institute School of Mathematics, Computing and Data Science.

Abstracts

• Cryptographic Implications of Worst-Case Hardness of Time-Bounded Kolmogorov Complexity / Noam Mazor (NYU)

  We consider the worst-case hardness of the gap version of the classic time-bounded Kolmogorov complexity problem—GapMKtP[s1,s2]—where the goal is to determine whether for a given string x, K^t(x) ≤ s1(n) or K^{p(t)}(x) > s2(n), where K^t(x) denotes the t-bounded Kolmogorov complexity of x. As shown by Hirahara (STOC’18), if GapMKtP[s1,s2] ∉ prBPP for every polynomial p, then (under appropriate derandomization assumption) GapMKtP is errorless average-case hard with respect to BPP heuristics. The notion of errorless average-case hardness, however, is seemingly insufficient for cryptographic applications where one needs to consider average-case hardness against attacks that simply may err with some probability (i.e., two-sided error hardness).

  In this work, we present several new consequences of the assumption that GapMKtP[s1,s2] ∉ P/poly for all polynomials p, for appropriate choices of s1,s2, and under appropriate (worst-case) derandomization assumptions. In particular, we show that this assumption implies:

  • The existence of an (inefficient-prover) zero-knowledge proof system for NP with a non-uniform simulator w.r.t. adversaries with a-priori bounded-length auxiliary-input.

  • The existence of a hard disjoint NP pair, defined as a promise problem (Y,N) where both Y,N ∈ NP; this provides a barrier towards showing that GapMKtP is NP-complete.

  The above results are proven via first showing that the above assumption implies the existence of a so-called conditional PRG—roughly speaking, a cryptographic PRG where indistinguishability only needs to hold for some (potentially not efficiently sampleable) distribution over the seed to the PRG. (In fact, this notion of a PRG also almost directly implies average-case hardness of GapMKtP, and as such, this provides a modular explanation to Hirahara’s results.)

  Finally, we show that for the results on conditional PRGs and Zero-knowledge Proofs, unconditional results can be obtained (that is, without making any derandomization assumptions), if considering an appropriate version of GapMKtP concerning randomized K^t.

• Towards the Universe of Trustworthy AI Agents / Eugene Bagdasarian (UMass Amherst)

  Frontier AI agents are increasingly delegated real work: browsing the web, calling APIs, and acting on user data. As autonomy grows, attacks could lead agents to leak private data, execute harmful actions, and even collude with other agents. I argue that we should rely on language models to decide what data and actions are appropriate in each context, but enforce these decisions using system primitives. Furthermore, decentralized multi-agent systems will allow us to increase robustness to attacks by providing independent perspectives on untrusted contexts. These contextual defenses offer a practical path to deploying trustworthy AI agents.

• Optimal Best-of-Both-Worlds Consensus / Fatima Elsheimy (Yale University)

  Consensus protocols face a fundamental trade-off: synchrony enables higher fault tolerance, whereas asynchrony provides responsiveness (latency proportional to actual network delays) and security under arbitrary delays. In particular, synchronous consensus achieves optimal resilience up to t<n/2 corruptions but relies on worst-case delay bounds that affect both latency and security, whereas asynchronous consensus tolerates only t<n/3 corruptions.

  Two approaches have sought orthogonal compromises between the two. Optimistically responsive protocols [Pass and Shi, EC’18] achieve resilience beyond the feasibility limits of asynchronous security, and provide responsiveness under optimistic conditions. Network-agnostic protocols [Blum–Katz–Loss, TCC’19] are secure in both synchronous and asynchronous networks but are non-responsive due to relying on conservative worst-case waiting and, to date, do not achieve constant time in asynchrony.

  We reconcile these approaches by constructing the first Byzantine agreement (BA) and validated Byzantine agreement (VBA) protocols that achieve network-agnostic security and optimistic responsiveness with optimal resilience tradeoffs. Concretely, for thresholds ts >tr >ta satisfying n>2ts + ta and n>ts + 2tr, our protocols satisfy:
  – Both protocols are synchronously secure for up to ts corruptions and asynchronously secure for up to ta corruptions.
  – Our VBA protocol is responsive when the number of corruptions is at most tr, while our BA protocol is responsive if additionally at least ts + 1 honest parties begin with the same input.
  – Both protocols run in expected constant time with quadratic communication complexity, regardless of network conditions.

  We prove matching impossibility results showing that the resilience trade-offs are optimal, and our protocols additionally achieve optimal expected time and communication complexity.

• Unforgeable and Recoverable Watermarks for Language Models via Robust Signatures / Kameron Shahabi (University of Washington)

  Language models now routinely generate text that is difficult to distinguish from human writing, raising the need for robust tools to verify content provenance. Watermarking has emerged as a promising countermeasure, with existing work largely focused on model quality preservation and robust detection. However, current schemes provide limited protection against false attribution. In this talk, we’ll introduce two novel security properties for watermarking aimed at strengthening attribution guarantees: unforgeability and recoverability. Unforgeability prevents adversaries from crafting false positives, texts that are far from any output from the watermarked model but are nonetheless flagged as watermarked. Recoverability provides an additional layer of protection: whenever a watermark is detected, the detector identifies the source text from which the flagged content was derived. Towards achieving these properties, we present a new primitive, robust signatures, inspired by classical digital signatures in cryptography. We will see how to build such signatures and demonstrate how they can be used to design robust watermarking schemes with secure attribution and fine-grained traceability.