0
$\begingroup$

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

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

1 Answer 1

3
$\begingroup$

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 and PRINCE, Simon, LBlock, PRESENT, µ2. 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.

$\endgroup$

Your Answer

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

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