Why are the candidates for one-way functions so few?

Today, almost all candidates are based on elementary mathematics, except Goldreich's candidate 2000 and ... (?!).

Why one can not generate several candidates by using advanced mathematics, for example using complex structures of combinatorics?

  • $\begingroup$ huh? isnt every NP complete problem a candidate for a one-way function? maybe there is some other core question here? $\endgroup$ – vzn Jun 27 '14 at 20:56
  • 7
    $\begingroup$ @vzn: NP-complete problems are hard in worst cases, while one-way functions (OWFs) are hard on average. For this reason, most NP-complete problems cannot be used (or at least, we don't know how to use them) as a basis for OWFs. To further complicate things, not every hard-on-average problem can be used as a OWF! See Impagliazzo's Five Worlds for more information. $\endgroup$ – M.S. Dousti Jun 28 '14 at 8:43
  • $\begingroup$ right. anyway "candidate" means also roughly "conjectured" and isnt it an open conjecture that every NP complete problem could "somehow" be used as a OWF? anyway it would seem that this question comes down to the same ubiquitous difficulty in the field of proving lower bounds... referred to in Arora/Barak as "complexity theory's Waterloo". (also tightly coupled with basic open questions in average case complexity theory about how to find uniformly hard distributions for NP complete problems...) in other words it cuts to the heart of key open conjectures in TCS close to P=?NP $\endgroup$ – vzn Jun 28 '14 at 15:19
  • 2
    $\begingroup$ The premise in the question seems faulty. For instance, $f(k) = \text{AES}(k,0)$ (the AES encryption of the all-zeros plaintext under the key $k$) is a good candidate for a one-way function. I'd hesitate to say that it is based on elementary mathematics; it's not really based on any kind of mathematics, exactly. That also makes it clear that there are many candidate one-way function (the candidates aren't few at all); there are at least as many candidates as proposed block ciphers, and there are many proposed block ciphers out there. $\endgroup$ – D.W. Jan 12 '18 at 22:13

Here is a "canned" answer that might be useful, but has no cryptographic depth (hopefully we get answers with depth as well).

What makes for a good candidate OWF? The naive answer tends to boil down to "something that looks hard to invert to me", but the expert's response is usually more like "something that many smart people have tried to invert but failed" (or something whose invertability would imply that of such a function). From this perspective, it is worse for the problem to be more obscure (fewer have tried it), and it may be worse that the function is more complicated (this obfuscates whether it is truly difficult or you just cannot see the solution yourself).

To put the intuition another way, a common "bad intuition" is that if a problem looks more complicated or difficult to define/understand, then it is more likely to be computationally difficult to solve. Theoretical crypto does not accept this premise. The primary evidence we have for computational hardness is a history of failed attempts, which means good candidates should be simple, well-known functions with long histories.


As for your last question, the are several candidates for combinatorial one-way functions. This paper by Kojevnikov and Nikolenko lists three combinatorial complete one-way functions that are based on the tiling problem of Levin, semi- Thue systems, and Post Correspondence problem ( complete means those functions are one-way if one-way functions do exist).

Update: A more interesting candidate was given by Gligoroski. He proposed candidate combinatorial one-way function based on Latin squares (Quasigroups).

  • $\begingroup$ Another candidate using latin squares has been presented by Danilo Gligoroski. $\endgroup$ – Arash Ahadi Jun 27 '14 at 19:30

the conjecture that (roughly) "every NP complete function could somehow be used to create one way functions" has not been disproven so there is not really a shortage of "candidates" in at least that sense. an interesting recent formulation of this is by Cook et al, On the One-Way Function Candidate Proposed by Goldreich where they analyze the complexity of Goldreich's function by reducing it to SAT and doing empirical SAT experiments which give circumstantial evidence of its hardness (along with theoretical evidence also).

also existence of one way functions is tightly coupled to core long open problems in complexity theory eg the P=?NP problem. which is in turn tightly coupled with proving lower bounds in complexity theory, referred to by Arora/Barak in Complexity theory: a modern approach as complexity theory's Waterloo.

here is one ref by leading researchers on this angle that may be helpful:

  • 4
    $\begingroup$ What "conjecture" are you talking about? The "somehow" statement is so fluffy that it's meaningless. I don't see how Cook et al relates to it at all, it's about a specific candidate OWF and not about a general scheme to construct OWFs from NP-complete languages. The Akavia et al. results are relevant and give a specific meaning to something like your "conjecture" -- existence of an efficient reduction from a worst-case NP-complete problem to inverting an OWF on average -- but their results are negative, i.e. they rule out some reductions. $\endgroup$ – Sasho Nikolov Jun 29 '14 at 23:23
  • $\begingroup$ admittedly sketchy, some imagination & connecting-the-dots & further assembly reqd. cook ref demonstrates how "reverse-engineering"/breaking a OWF seems to be universally reducible to solving a SAT construction (ie case study as circumstantial evidence). the Akavia paper shows the general idea (of OWFs based on NP hardness) is at least under consideration. $\endgroup$ – vzn Jun 30 '14 at 1:12
  • 1
    $\begingroup$ Reducing inverting OWF to solving SAT is an easy exercise. You probably want the reverse direction, but Akavia et al. give some evidence that this is unlikely. If anything is known about the Akavia et al. formalization of the "conjecture", it is that it is likely to be wrong. $\endgroup$ – Sasho Nikolov Jun 30 '14 at 1:52
  • $\begingroup$ ok! anyway the basic idea, loosely aligned with the refs & in contrast to the basic premise of the question, is that knowledge in this area seems to be limited based on existing/known theoretical "machinery/technology" which is not up to the task of answering definitively (and in many ways this is tied to a/ the central quandary of the field), & conceivably there could be a large undiscovered universe of OWFs, nothing known really rules it out, and that a seeming "lack of candidates" may be more related to a human-oriented lack of imagination or ingenuity at this point. $\endgroup$ – vzn Jun 30 '14 at 4:18
  • $\begingroup$ filling in more bkg thinking. the Cook paper seems to show in particular (and by analogy, in general) that OWFs can be thought of as generators for "always hard" instances of SAT. by properties/defn of NP completeness there exist P-time 1-1 instance conversions between SAT and every other NP complete problem. so it seems any "secure" OWF can also be a generator for "always hard" instances of any NP complete problem and each one seems a "different version/variant" of the OWF.... reminiscent of Berman-Hartmanis conjecture $\endgroup$ – vzn Jul 3 '14 at 15:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.