$Invert_{A,f}(n)$

  1. il challenger sceglie uniformemente $x \in \{0,1\}^n$ e calcola $y= f(x)$
  2. $A$ riceve $1^n$ e $y$, dà in output $x'$
  3. output $1$ se $f(x') =y$, altrimenti $0$

Funzione one-way

Una funzione $f: \{0,1\}^* \to \{0,1\}^*$ è one-way se è

  1. Facile da calcolare: esiste un algoritmo di tempo polinomiale $M_f$ per calcolare $f$, cioè $\forall x$ $M_f(x) = f(x)$
  2. Difficile da invertire: $\forall A$ PPT $\exist$ $negl(n)$ tale che $Pr[Invert_{A,f}(n)= 1] \leq negl(n)$

Corollari