I remember reading somewhere that (under certain reasonable assumptions) a Boolean circuit with many inputs and outputs (assume equal number for now) chosen at random will be a one-way function with high probability. Is this true?

  • 1
    $\begingroup$ It depends on how you define random circuit. If you use $n$ block inputs, $m$ NAND gates each with 2 inputs and one output, with the block's outputs these $m$ gate outputs, and randomly connect each of the $2m$ gate inputs to one of the $n+m$ block inputs and gate outputs, you often end up with something that is not a function (two NAND gates can make an RS latch). If you add some rules preventing this, that's a function but not a one-way function. You need to hide many of the outputs to hope for that. I know no quantitative result (hence this is not an answer) [fixed] $\endgroup$ – fgrieu Mar 1 '16 at 11:30

The claim that you remember is to good to be true. It is yet unknown (because the question P ?= NP is still open) whether there are one-way functions. If the claim you remember was true, it would prove the existence of one-way functions.

P.S. While P = NP excludes the existence of one-way functions, even with P != NP the existence of one-way functions is still an open problem.

  • 2
    $\begingroup$ This is mathematically correct; but from an applied cryptography standpoint, there are one-way functions. $\endgroup$ – fgrieu Mar 1 '16 at 11:32
  • 2
    $\begingroup$ I would count "the existence of one-way functions" as a reasonable (even if unproven) assumption. $\endgroup$ – poncho Mar 1 '16 at 14:07
  • $\begingroup$ @fgrieu: I am explicitly referring to the original question. The vaguely remembered claim about some random circuits as stated by the OP would imply the existence of one-way functions. $\endgroup$ – jk - Reinstate Monica Mar 1 '16 at 14:13
  • $\begingroup$ It could be a claim under some widely believed assumption. Although it seems very unlikely for average-case hard OWF, the question is interesting for worst-case hard OWF. $\endgroup$ – Geoffroy Couteau Mar 1 '16 at 14:18
  • $\begingroup$ My question mentioned "reasonable assumptions". That includes "there is a one-way function". $\endgroup$ – Demi Mar 1 '16 at 15:14

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.