One-Way Function

• poly-time

• hard to invert: $\forall \mathtt{PPT}\;\mathcal{A}$

  $$ P(\mathcal{A}(f(x)) \in f^{-1}(x)) \le negl(n) $$

Weak OWF

• poly-time

• $\forall \mathtt{PPT}\;\mathcal{A}$

  $$ P(\mathcal{A}(f(x)) \in f^{-1}(x)) \le 1 - poly^{-1}(n) $$

One-Way Permutation

• Length Preserving
• Bijective

Examples

• PRG $g: \{0,1\}^n \rightarrow \{0,1\}^{n+1}$
• $f(x_1\dots x_n, J \subseteq \{1,\dots n\}) = (x_1, \dots x_n, \sum\limits_{i \in J}x_i \mod p)$ ($\mathtt{SUBSET\_SUM}$)
• $f(A_{\in \mathbb{Z}_p}^{m\times n}, x) = (A, Ax\mod p)\;(m \ll n, x \in \{0,1\}^n)$($\mathtt{SHORT\_INTEGER\_SOLUTION}$)
• $f(A_{\in \mathbb{Z}_p}^{m\times n}, x,e) = (A, Ax+e\mod p)\;(m \gg n)$
• $f(p,q) = p\cdot q$
  • $nextPrime(p)$, $nextPrime(q)$
  • $p,q \in Prime$
  • Weak OWF
• $f_{p,g}(x) = g^x \mod p$ ($2^x \mod \text{SinePrime}$)

OWF Construction

• $f'(x,y) = (x, f(y))$
• $f'(x, y) = (f(y), f(y))$