Questions tagged [one-way-functions]
One-way functions (OWF) are easy to compute, but hard to invert. They exists only if P$\ne$NP. Many cryptographic primitives are based on (or are implied by) the existence of one-way functions.
4
questions
7
votes
1answer
1k views
Length-preserving one-way functions
Unfortunately my background in computational complexity is still weak, but I am working on it.
As I understand, the question of existence of one-way functions is very important in the field.
Assume ...
4
votes
1answer
2k views
How to show composition of one way function is not such?
I was wondering how should I proceed in order to show that the composition of (say) two one-way functions (either weak or strong or both together) is not a one-way function?
Specifically: Say $f$ and ...
3
votes
1answer
76 views
What are the examples of the easily computable “wild” permutations?
I am looking for the function $y=f(x)$ that would map the integer interval $[0,n)$ into itself $[0,n)$. The function must be bijective, so it is a permutation of n elements. It should "randomize" the ...
2
votes
1answer
103 views
Does the inverse of a one-way function $f$ being reducible to a predicate $b$ imply that $b$ is a hard-core bit for $f$?
I'm working with this definition for one-way functions:
We call $f$ a (strong) one-way function if
it is computable in polynomial time
for any polynomial time randomized algorithm $B$ ...
