Paper 2021/016

Black-Box Uselessness: Composing Separations in Cryptography

Geoffroy Couteau, Pooya Farshim, and Mohammad Mahmoody

Abstract

Black-box separations have been successfully used to identify the limits of a powerful set of tools in cryptography, namely those of black-box reductions. They allow proving that a large set of techniques are not capable of basing one primitive $\mathcal{P}$ on another $\mathcal{Q}$. Such separations, however, do not say anything about the power of the combination of primitives ${\mathcal{Q}}_1,{\mathcal{Q}}_2$ for constructing $\mathcal{P}$, even if $\mathcal{P}$ cannot be based on ${\mathcal{Q}}_1$ or ${\mathcal{Q}}_2$ alone. By introducing and formalizing the notion of black-box uselessness, we develop a framework that allows us to make such conclusions. At an informal level, we call primitive $$ black-box useless (BBU) for primitive $$ if $$ cannot help constructing $$ in a black-box way, even in the presence of another primitive $$. This is formalized by saying that $$ is BBU for $$ if for any auxiliary primitive $$, whenever there exists a black-box construction of $$ from $$, then there must already also exist a black-box construction of $$ from $$ alone. We also formalize various other notions of black-box uselessness, and consider in particular the setting of efficient black-box constructions when the number of queries to $$ is below a threshold. Impagliazzo and Rudich (STOC'89) initiated the study of black-box separations by separating key agreement from one-way functions. We prove a number of initial results in this direction, which indicate that one-way functions are perhaps also black-box useless for key agreement. In particular, we show that OWFs are black-box useless in any construction of key agreement in either of the following settings: (1) the key agreement has perfect correctness and one of the parties calls the OWF a constant number of times; (2) the key agreement consists of a single round of interaction (as in Merkle-type protocols). We conjecture that OWFs are indeed black-box useless for general key agreement protocols. We also show that certain techniques for proving black-box separations can be lifted to the uselessness regime. In particular, we show that known lower bounds for assumptions behind black-box constructions of indistinguishability obfuscation (IO) can be extended to derive black-box uselessness of a variety of primitives for obtaining (approximately correct) IO. These results follow the so-called "compiling out" technique, which we prove to imply black-box uselessness. Eventually, we study the complementary landscape of black-box uselessness, namely black-box helpfulness. Formally, we call primitive $$ black-box helpful (BBH) for $$, if there exists an auxiliary primitive $$ such that there exists a black-box construction of $$ from $$, but there exists no black-box construction of $$ from $$ alone. We put forth the conjecture that one-way functions are black-box helpful for building collision-resistant hash functions. We define two natural relaxations of this conjecture, and prove that both of these conjectures are implied by a natural conjecture regarding random permutations equipped with a collision finder oracle, as defined by Simon (Eurocrypt'98). This conjecture may also be of interest in other contexts, such as hardness amplification.