License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2021.29
URN: urn:nbn:de:0030-drops-135686
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/13568/
Nanashima, Mikito
On Basing Auxiliary-Input Cryptography on NP-Hardness via Nonadaptive Black-Box Reductions
Abstract
Constructing one-way functions based on NP-hardness is a central challenge in theoretical computer science. Unfortunately, Akavia et al. [Akavia et al., 2006] presented strong evidence that a nonadaptive black-box (BB) reduction is insufficient to solve this challenge. However, should we give up such a central proof technique even for an intermediate step?
In this paper, we turn our eyes from standard cryptographic primitives to weaker cryptographic primitives allowed to take auxiliary-input and continue to explore the capability of nonadaptive BB reductions to base auxiliary-input primitives on NP-hardness. Specifically, we prove the followings:
- if we base an auxiliary-input pseudorandom generator (AIPRG) on NP-hardness via a nonadaptive BB reduction, then the polynomial hierarchy collapses;
- 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).
These theorems extend our knowledge on nonadaptive BB reductions out of the current worst-to-average framework. The first result provides new evidence that nonadaptive BB reductions are insufficient to base AIPRG on NP-hardness. The second result also yields a weaker but still surprising consequence of nonadaptive BB reductions, i.e., a one-way function based on NP-hardness. In fact, the second result is interpreted in the following two opposite ways. Pessimistically, it shows that basing AIOWF or AIHSG on NP-hardness 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 provides conceptually stronger limitations than the currently known limitations on nonadaptive BB reductions. Optimistically, it offers a new hope: breakthrough construction of auxiliary-input primitives might also provide construction 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.
BibTeX - Entry
@InProceedings{nanashima:LIPIcs.ITCS.2021.29,
author = {Mikito Nanashima},
title = {{On Basing Auxiliary-Input Cryptography on NP-Hardness via Nonadaptive Black-Box Reductions}},
booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
pages = {29:1--29:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-177-1},
ISSN = {1868-8969},
year = {2021},
volume = {185},
editor = {James R. Lee},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/13568},
URN = {urn:nbn:de:0030-drops-135686},
doi = {10.4230/LIPIcs.ITCS.2021.29},
annote = {Keywords: Auxiliary-input cryptographic primitives, nonadaptive black-box reductions}
}
|
Keywords: |
|
Auxiliary-input cryptographic primitives, nonadaptive black-box reductions |
|
Collection: |
|
12th Innovations in Theoretical Computer Science Conference (ITCS 2021) |
|
Issue Date: |
|
2021 |
|
Date of publication: |
|
04.02.2021 |
