funzione unidirezionale

Una funzione unidirezionale (funzione one-way in inglese o semplicemente OWF) è una funzione matematica "facile da calcolare" ma "difficile da invertire". "Facile da calcolare" significa che esistono algoritmi che possono calcolare la funzione f(x) in tempo polinomiale (nella dimensione dell'input). "Difficile da invertire" significa che nessun algoritmo probabilisticamente polinomiale (classe di complessità temporale ) può calcolare una controimmagine di f(x) a meno di una probabilità trascurabile, quando x viene scelta in modo casuale. Si noti che, a differenza del concetto di difficoltà più comunemente diffuso nella teoria della complessità computazionale, "difficile", nel contesto delle funzioni unidirezionali, si riferisce alla difficoltà nel caso medio e non a quella nel caso peggiore.