文章基本信息

标题：Black-Box Uselessness: Composing Separations in Cryptography
本地全文：下载
作者：Geoffroy Couteau ; Pooya Farshim ; Mohammad Mahmoody 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2021
卷号：185
页码：47:1-47:20
DOI：10.4230/LIPIcs.ITCS.2021.47
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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 ð'« 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 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 ð'« 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. We also show that certain techniques for proving black-box 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 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. 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 amplification of hardness.
关键词：Black-Box Reductions; Separations; One-Way Functions; Key Agreement