<p>A reasonable approach is probably to take a lightweight block cipher, <span class="math-container">$E_\cdot(\cdot)$</span>, fix a constant <span class="math-container">$c$</span>, and use the function <span class="math-container">$f(k) = E_k(c)$</span> as the function.  While we have no proof that <span class="math-container">$f$</span> is a one-way function, it is a good candidate for a one-way function.  In particular, if the block cipher is secure, then <span class="math-container">$f$</span> will be a one-way function.</p>
<p>There are a number of designs of lightweight block ciphers.  As a starting point, you might look at <a href="https://www.iacr.org/archive/ches2011/69170343/69170343.pdf" rel="nofollow noreferrer">Piccolo</a> and <a href="https://eprint.iacr.org/2012/529.pdf" rel="nofollow noreferrer">PRINCE</a>, <a href="https://csrc.nist.gov/csrc/media/events/lightweight-cryptography-workshop-2015/documents/papers/session1-shors-paper.pdf" rel="nofollow noreferrer">Simon</a>, <a href="https://eprint.iacr.org/2011/345.pdf" rel="nofollow noreferrer">LBlock</a>, <a href="https://en.wikipedia.org/wiki/PRESENT" rel="nofollow noreferrer">PRESENT</a>, <a href="https://www.researchgate.net/profile/Je-Sen-Teh/publication/335471871_2_A_Lightweight_Block_Cipher/links/5d6dcee092851c85388891a1/2-A-Lightweight-Block-Cipher.pdf" rel="nofollow noreferrer">µ2</a>.  There might be better designs.</p>
<p>Another plausible approach is to use a lightweight stream cipher.  Any secure stream cipher will also be a one-way function.  For instance, you could look at using A5/1 or ACORN.</p>

CC BY-SA 4.0
2023-02-02T08:19:38.340Z
2023-02-02T08:19:38.340Z
D.W.
<p>What is the simplest known one-way function?</p>
<p>By simplest, I mean, when implemented as boolean logic, the number of AND/OR/NOT gates needed is minimal (smallest circuit complexity).</p>
<p>(I'm trying to find out if it's possible to build a one-way function using a mechanical computer, so simplicity would be very important.)</p>

CC BY-SA 4.0
2023-03-02T06:49:49.357Z
I answered a very similar question [here](https://crypto.stackexchange.com/questions/42656/are-there-simple-cryptographically-safe-one-way-hashing-functions). If simplicity is the goal, I think this candidate is considerably better than the lightweight block ciphers and stream ciphers from D.W.'s answer, which are optimized for speed on embedded systems and small key size (none of that has anything to do with simplicity)
Geoffroy Couteau
CC BY-SA 4.0
2023-02-02T06:45:49.200Z
There is no known one-way function.
Emil Jeřábek
CC BY-SA 4.0
2023-02-02T07:33:09.327Z
To elaborate on @EmilJeřábek 's answer: There are many functions that are conjectured to be one-way, but we cannot prove it for any of them (since such a proof implies that P is different than NP).
Or Meir
CC BY-SA 4.0
2023-02-03T10:00:23.907Z
@EmilJeřábek It seems according to Or Meir's comment that there are very likely several known one-way functions.
mathworker21
CC BY-SA 4.0
2023-02-03T10:23:01.743Z
@mathworker21 I don't know what you misunderstood in Or Meir's comment, but he confirms what I wrote: there are various functions that are *conjectured* to be one-way, but none that are *known* to be one-way. And since the existence (even nonconstructive) of one-way functions is an even stronger statement than $\mathrm{P\ne NP}$, it may take a while to prove, to put it diplomatically.
Emil Jeřábek
CC BY-SA 4.0
2023-02-03T13:55:04.300Z
@EmilJeřábek Let $f$ be an explicit example of a function that we strongly believe is one-way but cannot prove. Clearly $f$ is a known function (we know it). Therefore, if $f$ turns out to be a one-way function, then $f$ is a known one-way function. Maybe I am misunderstanding.
mathworker21
CC BY-SA 4.0
2023-02-03T14:30:24.093Z
@mathworker21 A “known one-way function” is a function that is known to be one-way. What you are describing is a “possibly one-way, known function”. If my neighbour is engaged in covert criminal operation, that does not make him a “known criminal” just because I know *him*.
Emil Jeřábek
CC BY-SA 4.0
2023-02-03T15:41:54.710Z
@EmilJeřábek Thanks! You are right. How would you describe the situation in which every function someone has proposed has been proven to not be one-way?
mathworker21
CC BY-SA 4.0
2023-02-03T16:26:24.177Z
@mathworker21 “Every function someone has proposed has been proven to not be one-way” sounds like a good description as is. But more concisely, and with a “known” inside, one could say something like “no plausible candidates for one-way functions are known”.
Emil Jeřábek
<cc.complexity-theory><circuit-complexity><boolean-functions><one-way-function>
What is the simplest one-way function (in terms of boolean circuit complexity)?
Azuresonance
# What is the simplest one-way function (in terms of boolean circuit complexity)?

(Asked by: username_0 on 2023-02-02)

What is the simplest known one-way function?

By simplest, I mean, when implemented as boolean logic, the number of AND/OR/NOT gates needed is minimal (smallest circuit complexity).

(I'm trying to find out if it's possible to build a one-way function using a mechanical computer, so simplicity would be very important.)

**Tags:** cc.complexity-theory, circuit-complexity, boolean-functions, one-way-function
> **Comments:**
> **username_2**: There is no known one-way function.  
> **username_3**: To elaborate on @EmilJeřábek 's answer: There are many functions that are conjectured to be one-way, but we cannot prove it for any of them (since such a proof implies that P is different than NP).  
> **username_4**: @EmilJeřábek It seems according to Or Meir's comment that there are very likely several known one-way functions.  
> **username_2**: @mathworker21 I don't know what you misunderstood in Or Meir's comment, but he confirms what I wrote: there are various functions that are *conjectured* to be one-way, but none that are *known* to be one-way. And since the existence (even nonconstructive) of one-way functions is an even stronger statement than $\mathrm{P\ne NP}$, it may take a while to prove, to put it diplomatically.  
> **username_4**: @EmilJeřábek Let $f$ be an explicit example of a function that we strongly believe is one-way but cannot prove. Clearly $f$ is a known function (we know it). Therefore, if $f$ turns out to be a one-way function, then $f$ is a known one-way function. Maybe I am misunderstanding.  
> **username_2**: @mathworker21 A “known one-way function” is a function that is known to be one-way. What you are describing is a “possibly one-way, known function”. If my neighbour is engaged in covert criminal operation, that does not make him a “known criminal” just because I know *him*.  
> **username_4**: @EmilJeřábek Thanks! You are right. How would you describe the situation in which every function someone has proposed has been proven to not be one-way?  
> **username_2**: @mathworker21 “Every function someone has proposed has been proven to not be one-way” sounds like a good description as is. But more concisely, and with a “known” inside, one could say something like “no plausible candidates for one-way functions are known”.  
> **username_1**: I answered a very similar question [here](https://crypto.stackexchange.com/questions/42656/are-there-simple-cryptographically-safe-one-way-hashing-functions). If simplicity is the goal, I think this candidate is considerably better than the lightweight block ciphers and stream ciphers from D.W.'s answer, which are optimized for speed on embedded systems and small key size (none of that has anything to do with simplicity)  

---

## 1 answers

### Answer by username_5 on 2023-02-02. Score: 3 | Accepted answer

A reasonable approach is probably to take a lightweight block cipher, $E\_\cdot(\cdot)$, fix a constant $c$, and use the function $f(k) = E\_k(c)$ as the function. While we have no proof that $f$ is a one-way function, it is a good candidate for a one-way function. In particular, if the block cipher is secure, then $f$ will be a one-way function.

There are a number of designs of lightweight block ciphers. As a starting point, you might look at [Piccolo](https://www.iacr.org/archive/ches2011/69170343/69170343.pdf) and [PRINCE](https://eprint.iacr.org/2012/529.pdf), [Simon](https://csrc.nist.gov/csrc/media/events/lightweight-cryptography-workshop-2015/documents/papers/session1-shors-paper.pdf), [LBlock](https://eprint.iacr.org/2011/345.pdf), [PRESENT](https://en.wikipedia.org/wiki/PRESENT), [µ2](https://www.researchgate.net/profile/Je-Sen-Teh/publication/335471871_2_A_Lightweight_Block_Cipher/links/5d6dcee092851c85388891a1/2-A-Lightweight-Block-Cipher.pdf). There might be better designs.

Another plausible approach is to use a lightweight stream cipher. Any secure stream cipher will also be a one-way function. For instance, you could look at using A5/1 or ACORN.


---

