Re:The existence of true one-way functions depends on Kolmog...
by gnull on Thursday April 07, 2022 @01:39PM
(#30947819)
And one-way functions are not necessarily the hardest to invert. They are, in some sense, "hard enough", at least as hard as certain threshold (speaking informally).
Re:The existence of true one-way functions depends on Kolmog...
by SilasX on Saturday April 09, 2022 @12:38PM
(#30969522)
What I meant was, the set of OWFs includes the upper bound on inversion difficulty (for functions easy in the forward direction) -- that is, you cannot remove a function from the set of OWFs by making it harder to invert (while preserving forward-direction-easiness).
So you could refer to Levin's complete OWF as "one-way-function-inversion-complete"? And, since one-way functions are, by construction, the hardest to invert, it's function-inversion-complete?
Edit: Wait, I guess the second part wouldn't follow, because OWFs only include functions that are easy in the forward direction, so they don't necessarily cover functions that are hard in both directions.