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

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

<p>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.</p>

CC BY-SA 3.0
2014-06-27T18:00:44.287Z
2014-06-27T18:00:44.287Z
usul
<p>As for your last question, the are several  candidates for combinatorial one-way functions. This paper by <a href="http://logic.pdmi.ras.ru/~arist/papers/cowf.pdf" rel="nofollow noreferrer">Kojevnikov and Nikolenko</a> 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).</p>

<p><em>Update</em>: A more interesting candidate was given by Gligoroski. <a href="https://eprint.iacr.org/2005/352.pdf" rel="nofollow noreferrer">He proposed candidate combinatorial one-way function</a> based on Latin squares (Quasigroups). </p>

CC BY-SA 3.0
2014-06-27T19:30:10.673Z
Another candidate using latin squares has been presented by Danilo Gligoroski.
Arash Ahadi
CC BY-SA 3.0
2014-06-27T18:05:51.037Z
2018-01-12T21:59:58.243Z
2018-01-12T21:59:58.243Z
Mohammad Al-Turkistany
<p>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, <a href="http://eccc.hpi-web.de/report/2012/175/download/" rel="nofollow">On the One-Way Function Candidate Proposed by Goldreich</a> 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).</p>

<p>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 <a href="http://rads.stackoverflow.com/amzn/click/0521424267" rel="nofollow">Complexity theory: a modern approach</a> as <em>complexity theory's Waterloo</em>.</p>

<p>here is one ref by leading researchers on this angle that may be helpful:</p>

<ul>
<li><a href="http://people.csail.mit.edu/akavia/AGGM.pdf" rel="nofollow">On Basing One-Way Functions on NP-Hardness</a> Adi Akavia, Oded Goldreich, Shafi Goldwasser, Dana Moshkovitz</li>
</ul>

CC BY-SA 3.0
2014-06-29T23:23:40.430Z
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.
Sasho Nikolov
CC BY-SA 3.0
2014-06-30T01:12:09.003Z
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.
vzn
CC BY-SA 3.0
2014-06-30T01:52:12.767Z
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.
Sasho Nikolov
CC BY-SA 3.0
2014-06-30T04:18:45.790Z
_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.
vzn
CC BY-SA 3.0
2014-07-03T15:27:34.857Z
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](http://en.wikipedia.org/wiki/Berman%E2%80%93Hartmanis_conjecture)
vzn
CC BY-SA 3.0
2014-06-29T17:20:47.207Z
2014-06-29T17:20:47.207Z
vzn
<p>Why are the candidates for one-way functions so few? </p>

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

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

CC BY-SA 3.0
2014-06-27T20:56:03.670Z
huh? isnt _every_ NP complete problem a candidate for a one-way function? maybe there is some other core question here?
vzn
CC BY-SA 3.0
2014-06-28T08:43:50.870Z
@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](http://cstheory.stackexchange.com/q/1026/873) for more information.
Sadeq Dousti
CC BY-SA 3.0
2014-06-28T15:19:54.303Z
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
vzn
CC BY-SA 3.0
2018-01-12T22:13:49.173Z
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.
D.W.
<cc.complexity-theory><cr.crypto-security><one-way-function>
Candidates for One-Way Function
Arash Ahadi
# Candidates for One-Way Function

(Asked by: username_0 on 2014-06-27)

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?

**Tags:** cc.complexity-theory, cr.crypto-security, one-way-function

> **Comments:**
> **username_1**: huh? isnt _every_ NP complete problem a candidate for a one-way function? maybe there is some other core question here?  
> **username_2**: @username_1: 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](http://cstheory.stackexchange.com/q/1026/873) for more information.  
> **username_1**: 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  
> **username_3**: 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.  

---

## 3 answers

### Answer by username_4 on 2014-06-27. Score: 8

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.


---

### Answer by username_5 on 2014-06-27. Score: 4

As for your last question, the are several candidates for combinatorial one-way functions. This paper by [Kojevnikov and Nikolenko](http://logic.pdmi.ras.ru/~arist/papers/cowf.pdf) 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](https://eprint.iacr.org/2005/352.pdf) based on Latin squares (Quasigroups).

> **Comments:**
> **username_0**: Another candidate using latin squares has been presented by Danilo Gligoroski.  

---

### Answer by username_1 on 2014-06-29. Score: -3

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](http://eccc.hpi-web.de/report/2012/175/download/) 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](http://rads.stackoverflow.com/amzn/click/0521424267) as *complexity theory's Waterloo*.

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

* [On Basing One-Way Functions on NP-Hardness](http://people.csail.mit.edu/akavia/AGGM.pdf) Adi Akavia, Oded Goldreich, Shafi Goldwasser, Dana Moshkovitz

> **Comments:**
> **username_6**: 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.  
> **username_1**: 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.  
> **username_6**: 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.  
> **username_1**: _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.  
> **username_1**: 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](http://en.wikipedia.org/wiki/Berman%E2%80%93Hartmanis_conjecture)  

---

