Jump to content

Pseudorandom permutations on arbitrary finite domains

Add links
From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by Purplie (talk | contribs) at 20:00, 23 March 2010. The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

In cryptography, the pseudorandom permutations used for ciphers are generally block ciphers (e.g. AES) that operate on fixed power-of-two domain sizes (block sizes) such as 2^64 or 2^128.

However, sometimes there is a need for a permutation on a domain of some other arbitrary domain size N. Examples include

  • Encrypting the data in-place in a fixed-width database field, when increasing the size of the field is not possible.
  • Generating a pseudorandom sequence of numbers of a required length, such as credit card numbers.
  • Encrypting the data while preserving its format, in the case that the plaintext length is always the same, to obscure the fact that the data has been encrypted.

Various methods have been explored to generate such permutations (or families of them).

Prefix Ciphers

For a very small domain, O(N) operations of a standard block cipher such as DES may be used to perform an in-memory shuffle of the array {1,...,N}, giving a provably pseudorandom permutation[1].

Cycle-walking ciphers

For a domain not much smaller than the domain of an existing block cipher (for example, N=2^63 which is not much smaller than the DES block size 2^64), repeatedly encrypt the input until the result falls into the original domain. This also gives a probably pseudorandom permutation[1].

Generalized Feistel ciphers

Black and Rogaway give an algorithm[1] for a generalization of the Feistel cipher, that creates a permutation on any domain size AB where A and B are integers. This may be considered not provably secure when N is less than around 2^60[1][2], but see [3].

Thorp shuffles

A Thorp shuffle is like an idealized card-shuffle, or equivalently a maximally-unbalanced Feistel cipher where one side is a single bit. This method and its provable security bounds are discussed in [2].

VIL mode

For domain sizes that are a power of two, and larger than the block size of an existing block cipher, a new cipher may be created using VIL mode as described by Bellare, Rogaway[4].

Hasty Pudding Cipher

The Hasty Pudding Cipher uses custom constructions (not depending on existing block ciphers as primitives) to encrypt arbitrary finite small domains.


References

  1. ^ a b c d Rogaway, Phillip (2002), Ciphers with Arbitrary Finite domains
  2. ^ a b Rogaway, Phillip (2009), "How to Encipher Messages on a Small Domain" (PDF), Advances in Cryptology
  3. ^ Patarin, Jacques (2003), "Luby-Rackoff: 7 Rounds Are Enough for 2n(1−ε) Security" (PDF), Advances in Cryptology—CRYPTO 2003, Lecture Notes in Computer Science, 2729: 513–529, doi:10.1007/b11817, retrieved 2009-07-27 {{citation}}: Unknown parameter |month= ignored (help)
  4. ^ Bellare, Mihir (1999), On the construction of Variable-Input-Length Ciphers (PDF)
Retrieved from "https://en.wikipedia.org/w/index.php?title=Pseudorandom_permutations_on_arbitrary_finite_domains&oldid=351624264"