# Is a random circuit likely to compute a one-way function?

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?

• 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] – fgrieu Mar 1 '16 at 11:30