Back دالة وحيدة الاتجاه Arabic Jednosměrná funkce Czech Einwegfunktion German One-way function English Función unidireccional Spanish Ühesuunaline funktsioon Estonian تابع یکطرفه Persian Fonction à sens unique French פונקציה חד-כיוונית HE 一方向性関数 Japanese
Una funzione unidirezionale (funzione one-way in inglese o semplicemente OWF) è una funzione matematica "facile da calcolare" ma "difficile da invertire"[1][2].
"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 PP) 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.