Examples
Let F be a random instance of the DES block cipher. This cipher has 64-bit blocks and a 56-bit key. The key therefore selects one of a family of 256 permutations on the 264 possible 64-bit blocks. A "random DES instance" means our oracle F computes DES using some key K (which is unknown to the adversary) where K is selected from the 256 possible keys with equal probability.
We want to compare the DES instance with an idealized 64-bit block cipher, meaning a permutation selected at random from the (264)! possible permutations on 64-bit blocks. Call this randomly selected permutation G. Note from Stirling's approximation that (264)! is around, so even specifying which permutation is selected requires writing down a number too large to represent exactly in any real computer. Viewed another way, G is an instance of a "cipher" whose "key length" is about 1021 bits, which again is too large to fit in a computer. (We can, however, implement G with storage space proportional to the number of queries, using a random oracle).
Note that because the oracles we're given encrypt plaintext of our choosing, we're modelling a chosen-plaintext attack or CPA, and the advantage we're calculating can be called the CPA-advantage of a given adversary. If we also had decryption oracles available, we'd be doing a chosen-ciphertext attack or CCA and finding the CCA-advantage of the adversary.
We'll look at several different adversaries and see how they perform.
Read more about this topic: Advantage (cryptography)
Famous quotes containing the word examples:
“Histories are more full of examples of the fidelity of dogs than of friends.”
—Alexander Pope (1688–1744)
“It is hardly to be believed how spiritual reflections when mixed with a little physics can hold people’s attention and give them a livelier idea of God than do the often ill-applied examples of his wrath.”
—G.C. (Georg Christoph)
“No rules exist, and examples are simply life-savers answering the appeals of rules making vain attempts to exist.”
—André Breton (1896–1966)