Welcome to the resource topic for 2021/016
Title:
Black-Box Uselessness: Composing Separations in Cryptography
Authors: Geoffroy Couteau, Pooya Farshim, 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 \mathcal{Q} black-box useless (BBU) for primitive \mathcal{P} if \mathcal{Q} cannot help constructing \mathcal{P} in a black-box way, even in the presence of another primitive \mathcal{Z}. This is formalized by saying that \mathcal{Q} is BBU for \mathcal{P} if for any auxiliary primitive \mathcal{Z}, whenever there exists a black-box construction of \mathcal{P} from (\mathcal{Q},\mathcal{Z}), then there must already also exist a black-box construction of \mathcal{P} from \mathcal{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 \mathcal{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 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 \mathcal{Q} black-box helpful (BBH) for \mathcal{P}, if there exists an auxiliary primitive \mathcal{Z} such that there exists a black-box construction of \mathcal{P} from (\mathcal{Q},\mathcal{Z}), but there exists no black-box construction of \mathcal{P} from \mathcal{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.
ePrint: https://eprint.iacr.org/2021/016
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .