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

50 questions
Filter by
Sorted by
Tagged with
25 views

### Is f.splitting_field() a one-way function candidate?

Is computing the splitting field of a polynomial a candidate for a one-way function? Let $K$ be a number field and $f, g \in K[x]$. Let L_f = f.splitting_field() ...
21 views

### Why is the existence of one-way functions not proven? [duplicate]

Weisstein, Eric W. "One-Way Function." From MathWorld--A Wolfram Web Resource.: The existence of one-way functions is not proven. Why not?
• 154
77 views

### Time bounded Kolmogorov complexity and one way functions

I recently read the following article https://www.quantamagazine.org/researchers-identify-master-problem-underlying-all-cryptography-20220406/ which links to https://arxiv.org/abs/2009.11514 that ...
28 views

### Reversible computing as a path to a useful PRNG or hash function?

There's a question I've long had about reversible computing: do non-trivial algorithms usually end up generating strongly pseudorandom data as an artifact of the computation? The most straightforward ...
• 306
33 views

### Is this restatement of one-way functions accurate?

I realize this is sort of a trivial ask, but I want to make sure I understand OWFs and it's usually explained with some jargon that I don't find clarifying. So, I'd just like to know whether or not my ...
• 306
1 vote
105 views

### P = NP ==> there exists no OWF: proof using NTM and binary tree

I read a proof in my script: If $P = NP\implies$ there exists no OWF $f$. A function $f$ is a OWF $\iff$ $f\in PTIME \space \land$ $f^{-1}\notin PTIME$ Their proof was a bit messy so I want to ask if ...
• 25
254 views

56 views

### One-way-function based on Friedberg numberings

A one-way-function is an easy to compute function $y=f(x)$ which is hard to invert. In 2000 Levin showed an example of a function which is one-way if there are one-way functions. As far as I know, it ...
37 views

### vector hashing function having collisions for permutations

let's consider vectors in space dim=3 and values {0,1,2,...,99} on each dimension I would like to create hash function but with special trait: collisions only for ...
• 109
1 vote
173 views

### Difficulty in proving the existence of one-way functions

By definition: A polynomial-time computable function $f:$ $\{$0,1$\}$$^*→ \{0,1\}$$^*$ is a one-way function if for every probabilistic polynomial time Turing Machine $PTM$ there is a ...
• 1,073
1 vote