Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Pseudorandom permutation
Résumé
In cryptography, a pseudorandom permutation (PRP) is a function that cannot be distinguished from a random permutation (that is, a permutation selected at random with uniform probability, from the family of all permutations on the function's domain) with practical effort.
Let F be a mapping . F is a PRP if and only if
For any , is a bijection from to , where .
For any , there is an "efficient" algorithm to evaluate for any ,.
For all probabilistic polynomial-time distinguishers : , where is chosen uniformly at random and is chosen uniformly at random from the set of permutations on n-bit strings.
A pseudorandom permutation family is a collection of pseudorandom permutations, where a specific permutation may be chosen using a key.
The idealized abstraction of a (keyed) block cipher is a truly random permutation on the mappings between plaintext and ciphertext. If a distinguishing algorithm exists that achieves significant advantage with less effort than specified by the block cipher's security parameter (this usually means the effort required should be about the same as a brute force search through the cipher's key space), then the cipher is considered broken at least in a certificational sense, even if such a break doesn't immediately lead to a practical security failure.
Modern ciphers are expected to have super pseudorandomness.
That is, the cipher should be indistinguishable from a randomly chosen permutation on the same message space, even if the adversary has black-box access to the forward and inverse directions of the cipher.
Michael Luby and Charles Rackoff showed that a "strong" pseudorandom permutation can be built from a pseudorandom function using a Luby–Rackoff construction which is built using a Feistel cipher.
An unpredictable permutation (UP) Fk is a permutation whose values cannot be predicted by a fast randomized algorithm. Unpredictable permutations may be used as a cryptographic primitive, a building block for cryptographic systems with more complex properties.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.