News for hackers. Stuff that matters.
Re:The existence of true one-way functions depends on Kolmog... by SilasX on Wednesday April 06, 2022 @04:19PM (#30936998)
> There's Levin's complete one way function [1; Section 4.3]. Breaking it is proven to be as hard as any other one-way function, in other words if there exist one-way functions then this is one of them.

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.

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