# What is the simplest one-way function (in terms of boolean circuit complexity)?

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

• There is no known one-way function. Feb 2 at 6:45
• 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). Feb 2 at 7:33
• @EmilJeřábek It seems according to Or Meir's comment that there are very likely several known one-way functions. Feb 3 at 10:00
• @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. Feb 3 at 10:23
• @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. Feb 3 at 13:55

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.