Funzione unidirezionale

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.

Definizione formale

Una funzione f : { 0 , 1 } ∗ → { 0 , 1 } ∗ {\displaystyle f\colon \{0,1\}^{*}\to \{0,1\}^{*}} è unidirezionale se esiste un algoritmo che in tempo polinomiale mappa x {\displaystyle x} in f ( x ) {\displaystyle f(x)} per ogni x ∈ { 0 , 1 } ∗ {\displaystyle x\in \{0,1\}^{*}} e per ogni algoritmo casuale PPT A {\displaystyle A} , ogni polinomio p ( ⋅ ) {\displaystyle p(\cdot )} e per valori di n {\displaystyle n} sufficientemente grandi si ha che:

P r [ f ( A ( f ( x ) ) ) = f ( x ) ] < 1 p ( n ) , {\displaystyle \mathrm {Pr} [f(A(f(x)))=f(x)]<{\frac {1}{p(n)}},}

dove la probabilità è sulla scelta delle x {\displaystyle x} da una distribuzione discreta uniforme su { 0 , 1 } n {\displaystyle \{0,1\}^{n}} e sulla casualità di A {\displaystyle A} .

Funzione unidirezionale debole

Una funzione unidirezionale debole, invece, è tale per cui ogni algoritmo casuale PPT A {\displaystyle A} che prova a calcolare una qualsiasi preimmagine di f ( x ) {\displaystyle f(x)} fallisce con probabilità non trascurabile. In modo formale, si dice che f {\displaystyle f} è una funzione debolmente unidirezionale se è calcolabile in tempo polinomiale ed esiste un polinomio p {\displaystyle p} tale che per ogni algoritmo casuale A {\displaystyle A} e per valori di n {\displaystyle n} sufficientemente grandi:

P r [ f ( A ( f ( x ) ) ) ≠ f ( x ) ] ≤ 1 − 1 p ( n ) , {\displaystyle \mathrm {Pr} [f(A(f(x)))\neq f(x)]\leq 1-{\frac {1}{p(n)}},}

dove la probabilità è sulla scelta delle x {\displaystyle x} da una distribuzione discreta uniforme su { 0 , 1 } n {\displaystyle \{0,1\}^{n}} e sulla casualità di A {\displaystyle A}

Permutazione unidirezionale

Una funzione f {\displaystyle f} è una permutazione unidirezionale se:

  • è una funzione unidirezionale
  • è biettiva

Congettura OWF

Le funzioni unidirezionali sono una delle primitive più rudimentali della moderna crittografia e la loro esistenza è necessaria per la stragrande maggioranza degli oggetti crittografici di interesse. L'esistenza delle funzioni unidirezionali, infatti, è equivalente all'esistenza dei generatori pseudocasuali[3], delle funzioni pseudocasuali[4], delle firme digitali[5], delle prove a conoscenza zero per ogni linguaggio NP[6] e di molti altri oggetti.

L'esistenza delle funzioni unidirezionali, inoltre, implica che P ≠ NP[7].

Candidati

Esistono numerosi candidati per le funzioni unidirezionali. Alcuni di essi sono[8][9]:

Note

  1. ^ Venturi, p. 54.
  2. ^ Katz, p. 242.
  3. ^ Johan HÅstad, Russell Impagliazzo e Leonid A. Levin, A Pseudorandom Generator from any One-way Function, in SIAM Journal on Computing, vol. 28, n. 4, 1999-01, pp. 1364–1396, DOI:10.1137/s0097539793244708. URL consultato il 23 marzo 2020.
  4. ^ Goldreich, Oded., How to construct random functions, Massachusetts Institute of Technology, Laboratory for Computer Science, 1983, OCLC 13335506. URL consultato il 23 marzo 2020.
  5. ^ J. Rompel, One-way functions are necessary and sufficient for secure signatures, in Proceedings of the twenty-second annual ACM symposium on Theory of computing - STOC '90, ACM Press, 1990, DOI:10.1145/100216.100269. URL consultato il 23 marzo 2020.
  6. ^ Oded Goldreich, Silvio Micali e Avi Wigderson, Providing Sound Foundations for Cryptography: On the Work of Shafi Goldwasser and Silvio Micali, Association for Computing Machinery, 9 ottobre 2019, ISBN 978-1-4503-7266-4. URL consultato il 23 marzo 2020.
  7. ^ Venturi, p. 57.
  8. ^ Venturi, p. 56.
  9. ^ Goldreich, pp. 55-58.

Bibliografia

  • Daniele Venturi, Crittografia nel Paese delle Meraviglie, collana UNITEXT, Springer Milan, 2012, DOI:10.1007/978-88-470-2481-6, ISBN 978-88-470-2480-9. URL consultato il 16 gennaio 2020.
  • (EN) Goldreich, Oded., Foundations of cryptology. [Volume 1], Basic tools, [Rev. ed.], Cambridge University Press, 2003, ISBN 0-511-04120-9, OCLC 56317390. URL consultato il 24 marzo 2020.
  • (EN) Jonathan Katz e Yehuda Lindell, Introduction to modern cryptography, 2ª ed., ISBN 978-1-4665-7026-9, OCLC 893721520. URL consultato il 24 marzo 2020.

Voci correlate

Collegamenti esterni

  Portale Crittografia
  Portale Matematica