The smallest tournament graph in which every pair of nodes has at least one common ancestor. Erdős and Sós consider the general problem of constructing tournament graphs where every n nodes have a common ancestor, giving an exponential lower bound for such graphs. This lower bound plays a crucial role in our impossibility results for constructing order-revealing encryption. See .
Can public key encryption be built from one-way functions? Is it just a matter of time before the community solves this problem, or are this problem and others like it actually impossible? This question is addressed by black box impossibilities, which show, relative to certain techniques, that such a result is indeed impossible. Black box impossibilities help guide protocol design by showing which techniques won't work. The proofs of such impossibilities can draw on interesting mathematical tools from linear algebra, graph theory, are more.

Limits on the Power of Prime-Order Groups: Separating Q-Type from Static Assumptions
By George Lu and Mark Zhandry
In CRYPTO 2024

A Computational Separation Between Quantum No-cloning and No-telegraphing
By Barak Nehoran and Mark Zhandry
In ITCS 2024, QIP 2023

The Relationship Between Idealized Models Under Computationally Bounded Adversaries
By Cong Zhang and Mark Zhandry
In ASIACRYPT 2023

A Lower Bound on the Length of Signatures Based on Group Actions and Generic Isogenies
By Dan Boneh, Jiaxin Guan and Mark Zhandry
In EUROCRYPT 2023

To Label, or Not To Label (in Generic Groups)
By Mark Zhandry
In CRYPTO 2022

Impossibility of Order-Revealing Encryption in Idealized Models
By Mark Zhandry and Cong Zhang
In TCC 2018