Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR20-095 | 24th June 2020 15:22

On Basing Auxiliary-Input Cryptography on NP-hardness via Nonadaptive Black-Box Reductions



A black-box (BB) reduction is a central proof technique in theoretical computer science. However, the limitations on BB reductions have been revealed for several decades, and the series of previous work gives strong evidence that we should avoid a nonadaptive BB reduction to base cryptography on NP-hardness (e.g., Akavia et al., 2006). Then should we also give up such a familiar proof technique even for an intermediate step towards cryptography?

In this paper, we continue to explore the capability of nonadaptive BB reductions and extend our knowledge on such a central technique out of the current (worst-to-average) framework. In particular, we investigate the attempt to base weaker cryptographic notions allowed to take auxiliary-input via nonadaptive BB reductions. As a result, we prove the following theorems: (1) if we base an auxiliary-input pseudorandom generator (AIPRG) on NP-hardness via a nonadaptive BB reduction, then the polynomial hierarchy collapses; (2) if we base an auxiliary-input one-way function (AIOWF) or auxiliary-input hitting set generator (AIHSG) on NP-hardness via a nonadaptive BB reduction, then an (i.o.-)one-way function also exists based on NP-hardness (via an adaptive BB reduction).

The first result gives new evidence that nonadaptive BB reductions are insufficient to base AIPRG. The second result also yields a weaker but still surprising consequence of nonadaptive BB reductions, that is, a one-way function based on NP-hardness. In fact, the second result is interpreted as the following two opposite ways. Pessimistically, it shows that basing AIOWF or AIHSG via nonadaptive BB reductions is harder than constructing a one-way function based on NP-hardness, which can be regarded as a negative result. Note that AIHSG is a weak primitive implied even by the hardness of learning; thus, this pessimistic view gives conceptually stronger limitations than the currently known limitations on nonadaptive BB reductions. Optimistically, our result gives a new hope: a breakthrough construction of auxiliary-input primitives might also be useful to construct standard cryptographic primitives. This optimistic view enhances the significance of further investigation on constructing auxiliary-input or other intermediate cryptographic primitives instead of standard cryptographic primitives.

ISSN 1433-8092 | Imprint