Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Pseudorandom permutation
Summary
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.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.