0
$\begingroup$

I realize this is sort of a trivial ask, but I want to make sure I understand OWFs and it's usually explained with some jargon that I don't find clarifying. So, I'd just like to know whether or not my understanding of one-way functions is "essentially correct":

$f$ is a one-way function iff it can convert $n$ input bits to $n$ output bits in poly time, such that an adversary (understanding $f$ completely and knowing the output bits produced) has no better strategy than randomly guessing all possible inputs to $f$ to try to find any particular specific output.

Is that more or less it, or am I missing anything? In particular, it's unclear to me if it's also fine for a OWF for there to exist some better attack than random guessing, just so long as it's not effective enough to take it out of exponential time.

$\endgroup$

1 Answer 1

1
$\begingroup$

It might be close, but I don't think it's 100% right. It's not clear what you mean by "find any particular specific output". Typically there's no requirement that an adversary have to try all possible inputs to $f$: it just has to be computationally infeasible to find a pre-image, on average. You could start from that intuition and you'd probably getting the main gist of things, but it won't be exactly right in situations where the details are important.

The mathematical definition is not jargon so much as a precise definition. If you want to study these subjects it's important to learn how to read these precise definitions, as the details matter.

See also https://en.wikipedia.org/wiki/One-way_function.

$\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.