Funcția unidirecțională

O funcție unidirecțională ( funcție unidirecțională în limba engleză sau pur și simplu OWF) este o funcție matematică „ușor de calculat”, dar „dificil de inversat ” ^[1] ^[2] .

„Ușor de calculat” înseamnă că există algoritmi care pot calcula funcția f (x) în timp polinomial (în dimensiunea intrării ). „Dificil de inversat” înseamnă că nici un algoritm probabilistic polinomial ( clasa de complexitate temporală PP ) nu poate calcula o imagine din spate a lui f (x) decât dacă este o probabilitate neglijabilă, când x este ales aleatoriu.

Rețineți că, spre deosebire de conceptul de dificultate cel mai des întâlnit în teoria complexității de calcul , „dificil”, în contextul funcțiilor unidirecționale, se referă la dificultatea în cazul mijlociu și nu la dificultatea în cel mai rău caz.

Definiție formală

O functie $f\colon \{0,1\}^{*}\to \{0,1\}^{*}$ ${\ displaystyle f \ colon \ {0,1 \} ^ {*} \ to \ {0,1 \} ^ {*}}$ ${\ displaystyle f \ colon \ {0,1 \} ^ {*} \ to \ {0,1 \} ^ {*}}$ este unidirecțional dacă există un algoritm care mapează în timp polinomial $X$ ${\ displaystyle x}$ $X$ în $f(x)$ ${\ displaystyle f (x)}$ $f (x)$ pentru fiecare $x\in \{0,1\}^{*}$ ${\ displaystyle x \ in \ {0,1 \} ^ {*}}$ ${\ displaystyle x \ in \ {0,1 \} ^ {*}}$ și pentru fiecare algoritm PPT aleatoriu $LA$ ${\ displaystyle A}$ $LA$ , orice polinom $p(\cdot )$ ${\ displaystyle p (\ cdot)}$ ${\ displaystyle p (\ cdot)}$ iar pentru valorile de $n$ ${\ displaystyle n}$ $n$ suficient de mari avem că:

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

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

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

unde probabilitatea este la alegerea $X$ ${\ displaystyle x}$ $X$ dintr-o distribuție discretă uniformă pe $\{0,1\}^{n}$ ${\ displaystyle \ {0,1 \} ^ {n}}$ $\ {0,1 \} ^ n$ și asupra întâmplării de $LA$ ${\ displaystyle A}$ $LA$ .

Funcție slabă într-un singur sens

O funcție slabă într-un singur sens, pe de altă parte, este de așa natură încât orice PPT aleatoriu $LA$ ${\ displaystyle A}$ $LA$ încercând să calculeze orice preimagine a $f(x)$ ${\ displaystyle f (x)}$ $f (x)$ eșuează cu o probabilitate deloc neglijabilă. Într-un mod formal, se spune că $f$ ${\ displaystyle f}$ $f$ este o funcție slab unidirecțională dacă poate fi calculată în timp polinomial și există un polinom $p$ ${\ displaystyle p}$ $p$ astfel încât pentru orice algoritm aleatoriu $LA$ ${\ displaystyle A}$ $LA$ iar pentru valorile de $n$ ${\ displaystyle n}$ $n$ suficient de mare:

\mathrm {Pr} [f(A(f(x)))\neq f(x)]\leq 1-{\frac {1}{p(n)}},

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

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

unde probabilitatea este la alegerea $X$ ${\ displaystyle x}$ $X$ dintr-o distribuție discretă uniformă pe $\{0,1\}^{n}$ ${\ displaystyle \ {0,1 \} ^ {n}}$ $\ {0,1 \} ^ n$ și asupra întâmplării de $LA$ ${\ displaystyle A}$ $LA$

Permutare unidirecțională

O functie $f$ ${\ displaystyle f}$ $f$ este o permutație unidirecțională dacă:

este o funcție unidirecțională
este bijectiv

Conjectura OWF

Funcțiile unidirecționale sunt una dintre cele mai rudimentare primitive din criptografia modernă , iar existența lor este necesară pentru marea majoritate a obiectelor criptografice de interes. Existența funcțiilor unidirecționale este, de fapt, echivalentă cu existența generatoarelor pseudorandom ^[3] , a funcțiilor pseudorandom ^[4] , a semnăturilor digitale ^[5] , a dovezilor de cunoaștere zero pentru fiecare limbaj NP ^[6] și a multor alte elemente.

Mai mult, existența funcțiilor unidirecționale implică faptul că P ≠ NP ^[7] .

Candidați

Există un număr de candidați pentru funcții unidirecționale. Unele dintre ele sunt ^[8] ^[9] :

înmulțirea și factorizarea numerelor prime
funcția RSA
funcția Rabin
logaritmul discret

Notă

^ Venturi , p. 54 .
^ Katz , p. 242 .
^ Johan HÅstad, Russell Impagliazzo și Leonid A. Levin, A Pseudorandom Generator from any One-way Function , în SIAM Journal on Computing , vol. 28, nr. 4, 1999-01, pp. 1364–1396, DOI : 10.1137 / s0097539793244708 . Adus pe 23 martie 2020 .
^ Goldreich, Oded., How to construct random functions , Massachusetts Institute of Technology, Laboratory for Computer Science, 1983,OCLC 13335506 . Adus pe 23 martie 2020 .
^ J. Rompel, Funcțiile unidirecționale sunt necesare și suficiente pentru semnături sigure , în Proceedings of the XXI-lea simpozion anual ACM on Theory of computing - STOC '90 , ACM Press, 1990, DOI : 10.1145 / 100216.100269 . Adus pe 23 martie 2020 .
^ Oded Goldreich, Silvio Micali și Avi Wigderson, Furnizarea unor fundații solide pentru criptografie: despre lucrările lui Shafi Goldwasser și Silvio Micali , Asociația pentru mașini de calcul, 9 octombrie 2019, ISBN 978-1-4503-7266-4 . Adus pe 23 martie 2020 .
^ Venturi , p. 57 .
^ Venturi , p. 56 .
^ Goldreich , pp. 55-58 .

Bibliografie

Daniele Venturi, Criptografie în Țara Minunilor , în UNITEXT , Springer Milano, 2012, DOI : 10.1007 / 978-88-470-2481-6 , ISBN 978-88-470-2480-9 . Adus la 16 ianuarie 2020 .
( EN ) Goldreich, Oded., Fundamente ale criptologiei. [Volumul 1], Instrumente de bază , [Rev. ed.], Cambridge University Press, 2003, ISBN 0-511-04120-9 ,OCLC 56317390 . Adus pe 24 martie 2020 .
( EN ) Jonathan Katz și Yehuda Lindell, Introducere în criptografie modernă , ediția a II-a, ISBN 978-1-4665-7026-9 ,OCLC 893721520 . Adus pe 24 martie 2020 .

Elemente conexe

Portal de criptografie

Portalul de matematică

[1] Venturi , p. 54 .

[2] Katz , p. 242 .

[3] Johan HÅstad, Russell Impagliazzo și Leonid A. Levin, A Pseudorandom Generator from any One-way Function , în SIAM Journal on Computing , vol. 28, nr. 4, 1999-01, pp. 1364–1396, DOI : 10.1137 / s0097539793244708 . Adus pe 23 martie 2020 .

[4] Goldreich, Oded., How to construct random functions , Massachusetts Institute of Technology, Laboratory for Computer Science, 1983,OCLC 13335506 . Adus pe 23 martie 2020 .

[5] J. Rompel, Funcțiile unidirecționale sunt necesare și suficiente pentru semnături sigure , în Proceedings of the XXI-lea simpozion anual ACM on Theory of computing - STOC '90 , ACM Press, 1990, DOI : 10.1145 / 100216.100269 . Adus pe 23 martie 2020 .

[6] Oded Goldreich, Silvio Micali și Avi Wigderson, Furnizarea unor fundații solide pentru criptografie: despre lucrările lui Shafi Goldwasser și Silvio Micali , Asociația pentru mașini de calcul, 9 octombrie 2019, ISBN 978-1-4503-7266-4 . Adus pe 23 martie 2020 .

[7] Venturi , p. 57 .

[8] Venturi , p. 56 .

[9] Goldreich , pp. 55-58 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]