Skip to main content
4 of 5
small o to constant c, as pointed out by @Ricky Demer
ckamath
  • 5.5k
  • 2
  • 24
  • 42

An efficiently computable function $f:\{0,1\}^*\rightarrow\{0,1\}^*$ is said to be $(s,\epsilon)$-one-way if for every adversary $\mathsf{A}$ of size* at most $s=s(|x|)$ the probability $\Pr\left[{\mathsf{A}(f(x))\in f^{-1}(x)}\right]$ is at most $\epsilon=\epsilon(|x|)$, where the probability is over uniform distribution on the domain and the random coins of $\mathsf{A}$.

The standard one-wayness assumption is that $s=poly(|x|)$ and $\epsilon=negl(|x|)$ . A one-way function is subexponentially-hard if for a fixed constant $0<c<1$, it is $(2^{{|x|}^c},2^{-{|x|}^c})$-one-way that the latter implies the former and is, therefore, a stronger assumption.

Similar definitions apply for the other primitives too.

*Here, size refers either to the run-time if $\mathsf{A}$ is a probabilistic Turing machine, or the circuit-size in case $\mathsf{A}$ is a circuit.

ckamath
  • 5.5k
  • 2
  • 24
  • 42