3 ms·
> 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 o
by SilasX 5y ago
> 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.
- gnull 5y agoAnd 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).
- SilasX 5y agoWhat 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).