Paper 2021/016
BlackBox Uselessness: Composing Separations in Cryptography
Geoffroy Couteau, Pooya Farshim, and Mohammad Mahmoody
Abstract
Blackbox separations have been successfully used to identify the limits of a powerful set of tools in cryptography, namely those of blackbox 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 blackbox uselessness, we develop a framework that allows us to make such conclusions. At an informal level, we call primitive $\mathcal{Q}$ blackbox useless (BBU) for primitive $\mathcal{P}$ if $\mathcal{Q}$ cannot help constructing $\mathcal{P}$ in a blackbox 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 blackbox construction of $\mathcal{P}$ from $(\mathcal{Q},\mathcal{Z})$, then there must already also exist a blackbox construction of $\mathcal{P}$ from $\mathcal{Z}$ alone. We also formalize various other notions of blackbox uselessness, and consider in particular the setting of efficient blackbox constructions when the number of queries to $\mathcal{Q}$ is below a threshold. Impagliazzo and Rudich (STOC'89) initiated the study of blackbox separations by separating key agreement from oneway functions. We prove a number of initial results in this direction, which indicate that oneway functions are perhaps also blackbox useless for key agreement. In particular, we show that OWFs are blackbox 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 Merkletype protocols). We conjecture that OWFs are indeed blackbox useless for general key agreement protocols. We also show that certain techniques for proving blackbox separations can be lifted to the uselessness regime. In particular, we show that known lower bounds for assumptions behind blackbox 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 socalled "compiling out" technique, which we prove to imply blackbox uselessness. Eventually, we study the complementary landscape of blackbox uselessness, namely blackbox helpfulness. Formally, we call primitive $\mathcal{Q}$ blackbox helpful (BBH) for $\mathcal{P}$, if there exists an auxiliary primitive $\mathcal{Z}$ such that there exists a blackbox construction of $\mathcal{P}$ from $(\mathcal{Q},\mathcal{Z})$, but there exists no blackbox construction of $\mathcal{P}$ from $\mathcal{Z}$ alone. We put forth the conjecture that oneway functions are blackbox helpful for building collisionresistant 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.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 Preprint. MINOR revision.
 Keywords
 blackbox separationscomposability
 Contact author(s)

couteau @ irif fr
pooya farshim @ gmail com
mahmoody @ gmail com  History
 20210106: received
 Short URL
 https://ia.cr/2021/016
 License

CC BY
BibTeX
@misc{cryptoeprint:2021/016, author = {Geoffroy Couteau and Pooya Farshim and Mohammad Mahmoody}, title = {BlackBox Uselessness: Composing Separations in Cryptography}, howpublished = {Cryptology ePrint Archive, Paper 2021/016}, year = {2021}, note = {\url{https://eprint.iacr.org/2021/016}}, url = {https://eprint.iacr.org/2021/016} }