Família de funcions pseudoaleatòries: diferència entre les revisions
mCap resum de modificació |
mCap resum de modificació |
||
| Línia 1: | Línia 1: | ||
En [[criptografia]], una '''família de funcions pseudoaleatòries''' ('''PRF''' en anglès) és una coŀlecció de [[subrutina|funcions]] [[Complexitat computacional|computables de manera eficient] que emulen un [[oracle aleatori]] de la següent manera: cap algorisme eficient pot distingir (amb [[avantatge (criptografia)|avantage]] 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 [[primitiva criptogràfica|primitives criptogràfiques]] i en especial [[esquema de xifratge|esquemes de xifratge]] segurs. |
En [[criptografia]], una '''família de funcions pseudoaleatòries''' ('''PRF''' en anglès) és una coŀlecció de [[subrutina|funcions]] [[Complexitat computacional|computables de manera eficient]] que emulen un [[oracle aleatori]] de la següent manera: cap algorisme eficient pot distingir (amb [[avantatge (criptografia)|avantage]] 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 [[primitiva criptogràfica|primitives criptogràfiques]] i en especial [[esquema de xifratge|esquemes de xifratge]] segurs. |
||
No s'ha de confondre les funcions pseudoaleatòries amb [[generador de nombres pseudoaleatoris|generadors pseudoaleatoris]] ('''PRG''' en anglès). La garantia d'un ''PRG'' és que una sortida individual sembla [[atzar|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 i quant la funció s'hagi escollit a l'atzar de la família PRF. |
No s'ha de confondre les funcions pseudoaleatòries amb [[generador de nombres pseudoaleatoris|generadors pseudoaleatoris]] ('''PRG''' en anglès). La garantia d'un ''PRG'' és que una sortida individual sembla [[atzar|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 i quant la funció s'hagi escollit a l'atzar de la família PRF. |
||
Revisió del 17:30, 7 jul 2012
En criptografia, una família de funcions pseudoaleatòries (PRF en anglès) és una coŀlecció de funcions computables de manera eficient que emulen un oracle aleatori de la següent manera: cap algorisme eficient pot distingir (amb avantage 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 i quant 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]
Vegeu també
Referències
- ↑ Oded Goldreich, Shafi Goldwasser, Silvio Micali (1986) "How to Construct Random Functions", Journal of the ACM, vol.33, no.4, p.792-807. doi:10.1145/6490.6503; preprint; web page and preprint