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.

7 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
2
votes
0answers
50 views

On possible existence of OWFs

Assuming $P\neq NP$, is there a computational model in which OWFs cannot exist? What more should we include beyond non-determinism, randomness, quantum model to preclude existence of OWFs?
1
vote
0answers
54 views

Is it possible to build a secure PRG from two functions one of them being a PRG?

Having two deterministic functions $G_1, G_2 : \left\{0,1\right\}^\lambda \rightarrow \left\{0,1\right\}^{\lambda+l}$, at least one of which is a secure PRG. Being $\alpha$ a constant, is it possible ...
1
vote
0answers
115 views

What is the relation between reversible circuits and invertible functions?

A reversible circuit, if I understand it correctly, is a circuit where every gate in the circuit is invertible, i.e. can simply be “turned in the opposite direction”, so that the entire circuit can in ...
0
votes
0answers
21 views

A set that is not polynomial time enumerable

For a set $I\subseteq \Bbb N$, defined $s_{I}(n)=\min\{i\in I\mid i>n\}$. The set $I$ is called polynomial-time-enumerable if $s_I(n)$ is computable in $\mathsf{poly}(n)$ time. Most of the sets I ...
0
votes
0answers
34 views

If g is a PRG and f is a OWF, is G'(x) = f(g(x)) a PRG?

Just like the title states. If I have a pseudo-random generator $g\colon \Sigma^n \rightarrow \Sigma^{2n}$ and a one-way function $f$, is $g'(x)=f(g(x))$ a pseudo-random generator? And why? My ...
0
votes
0answers
41 views

What complexity class results would be implied by a proof of the existence of one way functions

What complexity class results would be implied by a proof of the existence of one way functions. (Apart from the obvious $P \neq NP$) I thik it would imply $P \neq UP$, but what else?
0
votes
0answers
31 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 ...