8
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • $\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, 2014 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$
    – Sadeq Dousti
    Jun 28, 2014 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, 2014 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, 2018 at 22:13

3 Answers 3

Reset to default
8
$\begingroup$

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.

Improve this answer
$\endgroup$
4
$\begingroup$

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).

Improve this answer
$\endgroup$
1
  • $\begingroup$ Another candidate using latin squares has been presented by Danilo Gligoroski. $\endgroup$
    – Arash Ahadi
    Jun 27, 2014 at 19:30
-3
$\begingroup$

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:

Improve this answer
$\endgroup$
5
  • 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, 2014 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, 2014 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, 2014 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, 2014 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, 2014 at 15:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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