Skip to main content

Questions tagged [one-way-function]

Questions regarding easy-to-compute, but hard-to-invert functions.

Filter by
Sorted by
Tagged with
9 votes
2 answers

What's known about basing one-way function on the $P \neq NP$ assumption?

Is there a conditional impossibility result or the question is completely open?
user34204's user avatar
25 votes
4 answers

Arguments for existence of one-way functions

I have read in several papers that the existence of one-way functions is widely believed. Can someone shed light on why this is the case? What arguments do we have for supporting the existence of one-...
Anonymous's user avatar
  • 4,041
10 votes
1 answer

Reducing factoring prime products to factoring integer products (in average-case)

My question is about the equivalence of the security of various candidate one-way functions that can be constructed based on the hardness of factoring. Assuming the problem of FACTORING:[Given $N ...
Omid Etesami's user avatar
9 votes
2 answers

One-Way Permutations without Trapdoor

In Short: Assuming one-way permutations exist, can we construct one that has no trapdoor? More info: A one-way permutation is a permutation $\pi$ which is easy to compute, but hard to invert (see the ...
Sadeq Dousti's user avatar
  • 16.5k
1 vote
0 answers

Describe Levins 'Tile Expansion' one way functon in layman terms

I'd like some explanation on the details of the 'Complete OWF' presented on this paper in 'layman terms'. See page 13 of I'd prefer that the answerer had '...
galmeida's user avatar
  • 129