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

Improve this question
$\endgroup$
9
  • 7
    $\begingroup$ There is no known one-way function. $\endgroup$
    – Emil Jeřábek
    Feb 2 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
    Feb 2 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$
    – mathworker21
    Feb 3 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$
    – Emil Jeřábek
    Feb 3 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$
    – mathworker21
    Feb 3 at 13:55

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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