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 𝒫 on another 𝒬. Such separations, however, do not say anything about the power of the combination of primitives 𝒬₁,𝒬₂ for constructing 𝒫, even if 𝒫 cannot be based on 𝒬₁ or 𝒬₂ 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 𝒬 blackbox useless (BBU) for 𝒫 if 𝒬 cannot help constructing 𝒫 in a blackbox 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 blackbox construction of 𝒫 from (𝒬,𝒵), then there must already also exist a blackbox construction of 𝒫 from 𝒵 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 𝒬 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.
We also show that certain techniques for proving blackbox separations can be lifted to the uselessness regime. In particular, we show that the lower bounds of Canetti, Kalai, and Paneth (TCC'15) as well as Garg, Mahmoody, and Mohammed (Crypto'17 & TCC'17) for assumptions behind 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. 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 amplification of hardness.
BibTeX  Entry
@InProceedings{couteau_et_al:LIPIcs.ITCS.2021.47,
author = {Geoffroy Couteau and Pooya Farshim and Mohammad Mahmoody},
title = {{BlackBox Uselessness: Composing Separations in Cryptography}},
booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
pages = {47:147:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771771},
ISSN = {18688969},
year = {2021},
volume = {185},
editor = {James R. Lee},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/13586},
URN = {urn:nbn:de:0030drops135869},
doi = {10.4230/LIPIcs.ITCS.2021.47},
annote = {Keywords: BlackBox Reductions, Separations, OneWay Functions, Key Agreement}
}
Keywords: 

BlackBox Reductions, Separations, OneWay Functions, Key Agreement 
Collection: 

12th Innovations in Theoretical Computer Science Conference (ITCS 2021) 
Issue Date: 

2021 
Date of publication: 

04.02.2021 