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
540 views

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
4k views

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
379 views

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
987 views

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
73 views

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 https://arxiv.org/pdf/cs/0012023.pdf I'd prefer that the answerer had '...
galmeida's user avatar
  • 129