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.

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

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

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