Speaker:
Chris Brzuska

Title:
On the existence of one-way functions

Abstract:

One-way functions (OWFs) are easy to compute in one direction and hard to invert for polynomial-time inverters, on the average. OWFs are minimal objects in cryptography. I.e., essentially all objects (public-key encryption, signature schemes etc.) in cryptography imply OWFs. As the entire field of cryptography hinges on the existence of OWFs, showing the existence of OWFs is a major open problem in the foundations of cryptography.

Unfortunately, the existence of OWFs implies that NP differs from P. Therefore, showing the existence of OWFs seems currently elusive. Yet, even showing the existence of OWFs conditional on NP differing from P is currently not known. We explain the known barriers by Akavia, Goldreich, Goldwasser and Moshkovitz (STOC 2006) and Bogdanov and Brzuska (TCC 2015).

We then discuss Goldreich’s One-Way Function Candidate which is a appealing simple construction whose hardness relates to Random Constraint Satisfaction Problems (RandomCSP). We discuss the plausibility that Goldreich’s One-Way Function Candidate might be based on NP-hardness in light of known barriers.

We conclude with remarks on the related open question of basing fine-grained one-way functions on worst-case assumptions such as the exponential-time hypothesis.

**

Helsinki Algorithms Seminar is a weekly meeting of researchers in the Helsinki area interested in the art of algorithms and algorithm design, broadly interpreted to cover both theoretical ideas and algorithm engineering on concrete computing platforms. In most cases we have a presentation prepared for each meeting to communicate an idea, a recent result, work-in-progress, or demo, but this should not be at the expense of discussion and simply having fun with algorithms.

Our affiliations are with Aalto University and the University of Helsinki, and accordingly our activities alternate between the Otaniemi Campus of Aalto University and the Kumpula Campus of University of Helsinki, catalyzed by the Helsinki Institute for Information Technology HIIT, under the Algorithmic Data Analysis (ADA) programme.

For the season programme, please see the seminar webpage.