Funzione unidirezionale

Da Wikipedia, l'enciclopedia libera.

Una funzione unidirezionale, o funzione one-way in inglese, è 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 (PP) può calcolare una controimmagine di f(x) a meno di una probabilità trascurabile, quando x viene scelta casualmente.

Si noti che, a differenza del concetto di difficoltà più comunemente diffuso nella teoria della complessità, "difficile" nel contesto delle funzioni unidirezionali si riferisce alla difficoltà nel caso medio e non a quella nel caso peggiore.

Voci correlate[modifica | modifica sorgente]