TY - GEN
T1 - On Building Fine-Grained One-Way Functions from Strong Average-Case Hardness
AU - Brzuska, Chris
AU - Couteau, Geoffroy
N1 - Funding Information:
Acknowledgements. We thank Félix Richart for help with the experimental verification of some probability claims, and the anonymous Eurocrypt reviewers for their careful proofreading of the paper. C. Brzuska supported by the academy of Finland. G. Couteau supported by the ANR SCENE.
Publisher Copyright:
© 2022, International Association for Cryptologic Research.
PY - 2022
Y1 - 2022
N2 - Constructing one-way functions from average-case hardness is a long-standing open problem. A positive result would exclude Pessiland (Impagliazzo ’95) and establish a highly desirable win-win situation: either (symmetric) cryptography exists unconditionally, or all NP problems can be solved efficiently on the average. Motivated by the lack of progress on this seemingly very hard question, we initiate the investigation of weaker yet meaningful candidate win-win results of the following type: either there are fine-grained one-way functions (FGOWF), or nontrivial speedups can be obtained for all NP problems on the average. FGOWFs only require a fixed polynomial gap (as opposed to superpolynomial) between the running time of the function and the running time of an inverter. We obtain three main results: Construction. We show that if there is an NP language having a very strong form of average-case hardness, which we call block finding hardness, then FGOWF exist. We provide heuristic support for this very strong average-case hardness notion by showing that it holds for a random language. Then, we study whether weaker (and more natural) forms of average-case hardness could already suffice to obtain FGOWF, and obtain two negative results: Separation I. We provide a strong oracle separation for the implication (∃ exponentially average-case hard language ⇒ ∃ FGOWF). Separation II. We provide a second strong negative result for an even weaker candidate win-win result. Namely, we rule out a black-box proof for the implication (∃ exponentially average-case hard language whose hardness amplifies optimally through parallel repetitions ⇒ ∃ FGOWF). This separation forms the core technical contribution of our work.
AB - Constructing one-way functions from average-case hardness is a long-standing open problem. A positive result would exclude Pessiland (Impagliazzo ’95) and establish a highly desirable win-win situation: either (symmetric) cryptography exists unconditionally, or all NP problems can be solved efficiently on the average. Motivated by the lack of progress on this seemingly very hard question, we initiate the investigation of weaker yet meaningful candidate win-win results of the following type: either there are fine-grained one-way functions (FGOWF), or nontrivial speedups can be obtained for all NP problems on the average. FGOWFs only require a fixed polynomial gap (as opposed to superpolynomial) between the running time of the function and the running time of an inverter. We obtain three main results: Construction. We show that if there is an NP language having a very strong form of average-case hardness, which we call block finding hardness, then FGOWF exist. We provide heuristic support for this very strong average-case hardness notion by showing that it holds for a random language. Then, we study whether weaker (and more natural) forms of average-case hardness could already suffice to obtain FGOWF, and obtain two negative results: Separation I. We provide a strong oracle separation for the implication (∃ exponentially average-case hard language ⇒ ∃ FGOWF). Separation II. We provide a second strong negative result for an even weaker candidate win-win result. Namely, we rule out a black-box proof for the implication (∃ exponentially average-case hard language whose hardness amplifies optimally through parallel repetitions ⇒ ∃ FGOWF). This separation forms the core technical contribution of our work.
UR - http://www.scopus.com/inward/record.url?scp=85132130283&partnerID=8YFLogxK
U2 - 10.1007/978-3-031-07085-3_20
DO - 10.1007/978-3-031-07085-3_20
M3 - Conference article in proceedings
AN - SCOPUS:85132130283
SN - 978-3-031-07084-6
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 584
EP - 613
BT - Advances in Cryptology – EUROCRYPT 2022 - 41st Annual International Conference on the Theory and Applications of Cryptographic Techniques, 2022, Proceedings
A2 - Dunkelman, Orr
A2 - Dziembowski, Stefan
PB - Springer
T2 - Annual International Conference on the Theory and Applications of Cryptographic Techniques
Y2 - 30 May 2022 through 3 June 2022
ER -