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:
“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)
“There are many examples of women that have excelled in learning, and even in war, but this is no reason we should bring ‘em all up to Latin and Greek or else military discipline, instead of needle-work and housewifry.”
—Bernard Mandeville (1670–1733)
“In the examples that I here bring in of what I have [read], heard, done or said, I have refrained from daring to alter even the smallest and most indifferent circumstances. My conscience falsifies not an iota; for my knowledge I cannot answer.”
—Michel de Montaigne (1533–1592)