En informàtica, una funció unidireccional és una funció que és fàcil de calcular en cada entrada, però difícil d' invertir donada la imatge d'una entrada aleatòria. Aquí, "fàcil" i "difícil" s'han d'entendre en el sentit de la teoria de la complexitat computacional, específicament la teoria dels problemes de temps polinòmic. Això no té res a veure amb si la funció és unidireccional; trobar qualsevol entrada amb la imatge desitjada es considera una inversió reeixida.
L'existència d'aquestes funcions unidireccionals encara és una conjectura oberta. La seva existència demostraria que les classes de complexitat P i NP no són iguals, resolent així la qüestió més important sense resoldre de la informàtica teòrica.Oded Goldreich (2001). Foundations of Cryptography: Volume 1, Basic Tools (draft available from author's site). Cambridge University Press. . See also wisdom.weizmann.ac.il. No se sap si el contrari és cert, és a dir, l'existència d'una prova que P≠NP no implicaria directament l'existència de funcions unidireccionals.Goldwasser, S. and Bellare, M. "Lecture Notes on Cryptography" . Summer course on cryptography, MIT, 1996–2001.
En contextos aplicats, els termes "fàcil" i "difícil" s'interpreten normalment en relació amb alguna entitat informàtica específica; normalment "prou barat per als usuaris legítims" i "prohibitivament car per a qualsevol agent maliciós". Les funcions unidireccionals, en aquest sentit, són eines fonamentals per a la criptografia, la identificació personal, l'autenticació i altres aplicacions de seguretat de dades. Si bé l'existència de funcions unidireccionals en aquest sentit també és una conjectura oberta, hi ha diverses candidates que han resistit dècades d'intens escrutini. Algunes d'elles són ingredients essencials de la majoria de sistemes de telecomunicacions, comerç electrònic i banca electrònica a tot el món.
Definició teòrica Una funció f: {0,1} * → {0,1} * és unidireccional si f es pot calcular mitjançant un algorisme de temps polinòmic, però qualsevol algorisme aleatoritzat de temps polinòmic que intenta calcular una pseudoinversa per a f té èxit amb una probabilitat negligible. (El superíndex * significa qualsevol nombre de repeticions, vegeu l'estrella de Kleene.) És a dir, per a tots els algoritmes aleatoris , tots els enters positius c i tots els prou grans n = length(x),
on la probabilitat és superior a l'elecció de x de la distribució uniforme discreta sobre {0, 1}n, i l'aleatorietat de Many authors view this definition as strong one-way function. A weak one-way function can be defined similarly except that the probability that every adversarial fails to invert f is noticeable. However, one may construct strong one-way functions based on weak ones. Loosely speaking, strong and weak versions of one-way function are equivalent theoretically. See Goldreich's Foundations of Cryptography, vol. 1, ch. 2.1–2.3.
Cal tenir en compte que, segons aquesta definició, la funció ha de ser "difícil d'invertir" en el sentit del cas mitjà, en lloc del pitjor dels casos. Això és diferent de gran part de la teoria de la complexitat (per exemple, la NP-duresa), on el terme "difícil" s'entén en el pitjor dels casos. És per això que, fins i tot si se sap que alguns candidats a funcions unidireccionals (descrits a continuació) són NP-completes, això no implica la seva unidireccionalitat. Aquesta última propietat només es basa en la manca d'algoritmes coneguts per resoldre el problema.
No n'hi ha prou amb fer que una funció sigui "amb pèrdues" (no un a un) per tenir una funció unidireccional. En particular, la funció que genera la cadena de n zeros a qualsevol entrada de longitud n no és una funció unidireccional perquè és fàcil generar una entrada que doni com a resultat la mateixa sortida. Més precisament: per a una funció d'aquest tipus que simplement genera una cadena de zeros, un algorisme F que genera qualsevol cadena de longitud n a l'entrada f(x) "trobarà" una preimatge adequada de la sortida, fins i tot si no és l'entrada que es va utilitzar originalment per trobar la cadena de sortida.
Conceptes relacionats Una permutació unidireccional és una funció unidireccional que també és una permutació, és a dir, una funció unidireccional que és bijectiva. Les permutacions unidireccionals són una primitiva criptogràfica important, i no se sap si la seva existència està implicada per l'existència de funcions unidireccionals.
Implicacions teòriques de les funcions unidireccionals Si f és una funció unidireccional, aleshores la inversió de f seria un problema la sortida del qual és difícil de calcular (per definició) però fàcil de comprovar (només calculant-hi f ). Per tant, l'existència d'una funció unidireccional implica que FP≠FNP, que al seu torn implica que P ≠ NP. Tanmateix, P≠NP no implica l'existència de funcions unidireccionals.
L'existència d'una funció unidireccional implica l'existència de molts altres conceptes útils, com ara:
Generadors pseudoaleatoris Famílies de funcions pseudoaleatòries Esquemes de compromís de bits Esquemes de xifratge de clau privada que protegeixen contra atacs de text xifrat adaptatiu escollit Codis d'autenticació de missatges Esquemes de signatura digital (segurs contra atacs adaptatius de missatge escollit)
Candidats per a funcions unidireccionals Les següents són diverses candidates per a funcions unidireccionals (a l'abril de 2009). Clarament, no se sap si aquestes funcions són realment unidireccionals; però fins ara s'han fet investigacions exhaustives que no han aconseguit produir un algorisme d'inversió eficient per a cap d'elles.
Multiplicació i factorització La funció f pren com a entrades dos nombres primers p i q en notació binària i retorna el seu producte. Aquesta funció es pot calcular "fàcilment" en temps O(b²), on b és el nombre total de bits de les entrades. Invertir aquesta funció requereix trobar els factors d'un enter N donat. Els millors algoritmes de factorització coneguts s'executen en temps, on b és el nombre de bits necessaris per representar N.
Aquesta funció es pot generalitzar permetent que p i q es moguin dins d'un conjunt adequat de semiprimers. Cal tenir en compte que f no és unidireccional per a enters seleccionats aleatòriament , ja que el producte tindrà 2 com a factor amb probabilitat 3/4 (perquè la probabilitat que un p arbitrari sigui senar és 1/2, i igualment per a q, de manera que si es trien independentment, la probabilitat que tots dos siguin senars és, per tant, 1/4; per tant, la probabilitat que p o q siguin parells és ).
La funció de Rabin (elevació al quadrat modular) La funció de Rabin,Oded Goldreich (2001). Foundations of Cryptography: Volume 1, Basic Tools (draft available from author's site). Cambridge University Press. . See also wisdom.weizmann.ac.il.o mòdul al quadrat , on i són nombres primers es creu que és una col·lecció de funcions unidireccionals. Escrivim
per denotar quadrat mòdul : un membre específic de la col·lecció de Rabin. Es pot demostrar que extreure arrels quadrades, és a dir, invertir la funció de Rabin, és computacionalment equivalent a factoritzar (en el sentit de reducció en temps polinòmic). Per tant, es pot demostrar que la col·lecció de Rabin és unidireccional si i només si la factorització és difícil. Això també és vàlid per al cas especial en què i tenen la mateixa longitud de bit. L'algoritme de signatura de Rabin es basa en la suposició que aquesta funció de Rabin és unidireccional.
Exponencial discreta i logaritme L'exponenciació modular es pot fer en temps polinòmic. Invertir aquesta funció requereix calcular el logaritme discret. Actualment hi ha diversos grups populars per als quals no es coneix cap algorisme per calcular el logaritme discret subjacent en temps polinòmic. Tots aquests grups són grups abelians finits i el problema general del logaritme discret es pot descriure així.
Sigui G un grup abelià finit de cardinalitat n. Denotem la seva operació de grup per multiplicació. Considerem un element primitiu i un altre element El problema del logaritme discret és trobar l'enter positiu k, on , de manera que:
El nombre enter k que resol l'equació s'anomena logaritme discret de β a la base α. S'escriu .
Les opcions populars per al grup G en criptografia logarítmica discreta són els grups cíclics (Zp)× (per exemple, xifratge ElGamal, intercanvi de claus Diffie-Hellman i l'algoritme de signatura digital) i els subgrups cíclics de corbes el·líptiques sobre camps finits (vegeu criptografia de corbes el·líptiques).
Una corba el·líptica és un conjunt de parells d'elements d'un camp que satisfan . Els elements de la corba formen un grup sota una operació anomenada "suma de punts" (que no és el mateix que l'operació de suma del camp). La multiplicació kP d'un punt P per un enter k ( és a dir, una acció de grup del grup additiu dels enters) es defineix com una suma repetida del punt a si mateix. Si es coneixen k i P, és fàcil calcular , però si només es coneixen R i P, se suposa que és difícil calcular k .
Funcions hash criptogràficament segures Hi ha diverses funcions hash criptogràfiques que es calculen ràpidament, com ara SHA-256. Algunes de les versions més senzilles han caigut a causa d'anàlisis sofisticades, però les versions més potents continuen oferint solucions ràpides i pràctiques per a la computació unidireccional. La major part del suport teòric per a les funcions són més aviat tècniques per frustrar alguns dels atacs anteriorment reeixits.
Altres candidats Altres candidats per a funcions unidireccionals inclouen la duresa de la descodificació de codis lineals aleatoris, la duresa de certs problemes de xarxa i el problema de la suma de subconjunts (criptosistema de motxilla de Naccache-Stern).
Funció unidireccional universal Hi ha una funció explícita f que s'ha demostrat que és unidireccional, si i només si existeixen funcions unidireccionals. En altres paraules, si alguna funció és unidireccional, aleshores f també ho és. Com que aquesta funció va ser la primera funció unidireccional completa combinatòria que es va demostrar, es coneix com la "funció unidireccional universal . El problema de trobar una funció unidireccional es redueix, doncs, a demostrar de manera no constructiva— que existeix una d'aquestes funcions.
També existeix una funció que és unidireccional si la complexitat de Kolmogorov limitada en temps polinòmic és lleugerament difícil de mitjana. Com que l'existència de funcions unidireccionals implica que la complexitat de Kolmogorov limitada en temps polinòmic és lleugerament difícil de mitjana, la funció és una funció unidireccional universal.
Referències
Categoria:Criptografia Categoria:Teoria de la informació