Editing Block cipher (section)

==Provable security==
When a block cipher is used in a given [[Block cipher mode of operation|mode of operation]], the resulting algorithm should ideally be about as secure as the block cipher itself. ECB (discussed above) emphatically lacks this property: regardless of how secure the underlying block cipher is, ECB mode can easily be attacked. On the other hand, CBC mode can be proven to be secure under the assumption that the underlying block cipher is likewise secure. Note, however, that making statements like this requires formal mathematical definitions for what it means for an encryption algorithm or a block cipher to "be secure". This section describes two common notions for what properties a block cipher should have. Each corresponds to a mathematical model that can be used to prove properties of higher-level algorithms, such as CBC.

This general approach to cryptography – proving higher-level algorithms (such as CBC) are secure under explicitly stated assumptions regarding their components (such as a block cipher) – is known as ''provable security''.

===Standard model===
{{main | Ciphertext indistinguishability }}
Informally, a block cipher is secure in the standard model if an attacker cannot tell the difference between the block cipher (equipped with a random key) and a random permutation.

To be a bit more precise, let ''E'' be an ''n''-bit block cipher. We imagine the following game:
# The person running the game flips a coin.
#* If the coin lands on heads, he chooses a random key ''K'' and defines the function ''f'' = ''E''<sub>''K''</sub>.
#* If the coin lands on tails, he chooses a random permutation {{pi}} on the set of ''n''-bit strings and defines the function ''f'' = {{pi}}.
# The attacker chooses an ''n''-bit string ''X'', and the person running the game tells him the value of ''f''(''X'').
# Step 2 is repeated a total of ''q'' times. (Each of these ''q'' interactions is a ''query''.)
# The attacker guesses how the coin landed. He wins if his guess is correct.

The attacker, which we can model as an algorithm, is called an ''[[Adversary (cryptography)|adversary]]''. The function ''f'' (which the adversary was able to query) is called an ''[[Oracle machine|oracle]]''.

Note that an adversary can trivially ensure a 50% chance of winning simply by guessing at random (or even by, for example, always guessing "heads"). Therefore, let ''P''<sub>''E''</sub>(''A'') denote the probability that adversary ''A'' wins this game against ''E'', and define the ''advantage'' of ''A'' as 2(''P''<sub>''E''</sub>(''A'')&nbsp;−&nbsp;1/2). It follows that if ''A'' guesses randomly, its advantage will be 0; on the other hand, if ''A'' always wins, then its advantage is 1. The block cipher ''E'' is a ''pseudo-random permutation'' (PRP) if no adversary has an advantage significantly greater than 0, given specified restrictions on ''q'' and the adversary's running time. If in Step 2 above adversaries have the option of learning ''f''<sup>−1</sup>(''X'') instead of ''f''(''X'') (but still have only small advantages) then ''E'' is a ''strong'' PRP (SPRP). An adversary is ''non-adaptive'' if it chooses all ''q'' values for ''X'' before the game begins (that is, it does not use any information gleaned from previous queries to choose each ''X'' as it goes).

These definitions have proven useful for analyzing various modes of operation. For example, one can define a similar game for measuring the security of a block cipher-based encryption algorithm, and then try to show (through a [[Reduction (complexity)|reduction argument]]) that the probability of an adversary winning this new game is not much more than ''P''<sub>''E''</sub>(''A'') for some ''A''. (The reduction typically provides limits on ''q'' and the running time of ''A''.) Equivalently, if ''P''<sub>''E''</sub>(''A'') is small for all relevant ''A'', then no attacker has a significant probability of winning the new game. This formalizes the idea that the higher-level algorithm inherits the block cipher's security.

===Ideal cipher model===
{{expand section|date=April 2012}}