Black-Box Uselessness: Composing Separations in Cryptography

International audienceBlack-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 P on another Q. Such separations, however, do not say anything about the power of the combination of primitives Q 1 , Q 2 for constructing P, even if P cannot be based on Q 1 or 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 Q black-box useless (BBU) for primitive P if Q cannot help constructing P in a black-box way, even in the presence of another primitive Z. This is formalized by saying that Q is BBU for P if for any auxiliary primitive Z, whenever there exists a black-box construction of P from (Q, Z), then there must already also exist a black-box construction of P from Z 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 Q 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 blackbox 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 blackbox helpfulness. Formally, we call primitive Q black-box helpful (BBH) for P, if there exists an auxiliary primitive Z such that there exists a black-box construction of P from (Q, Z), but there exists no black-box construction of P from Z 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