Família de funcions pseudoaleatòries

De Viquipèdia
Dreceres ràpides: navegació, cerca

En criptografia, una família de funcions pseudoaleatòries (PRF en anglès) és una col·lecció de funcions computables de manera eficient que emulen un oracle aleatori de la següent manera: cap algorisme eficient pot distingir (amb avantatge significant) entre una funció escollida a l'atzar de la família PRF i un oracle aleatori (una funció les sortides del qual han estat fixades de forma completament aleatòria). Les funcions pseudoaleatòries són una eina primordial per a la construcció de primitives criptogràfiques i en especial esquemes de xifratge segurs.

No s'ha de confondre les funcions pseudoaleatòries amb generadors pseudoaleatoris (PRG en anglès). La garantia d'un PRG és que una sortida individual sembla aleatòria si l'entrada ha estat escollida a l'atzar. D'altra banda, la garantia d'una PRF és que totes les seves sortides semblen aleatòries, sense tenir en compte com s'han escollit les entrades, sempre que la funció s'hagi escollit a l'atzar de la família PRF.

Una família de funcions pseudoaleatòries es pot construir a partir de qualsevol generador pseudoaleatori utilitzant, per exemple, la construcció de Goldreich, Goldwasser i Micali.[1]

Referències[modifica | modifica el codi]

  1. Oded Goldreich, Shafi Goldwasser, Silvio Micali "How to Construct Random Functions", Journal of the ACM, (1986) vol.33, no.4, p.792-807. doi:10.1145/6490.6503
    preprint; web page and preprint