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.
[5] A randomized algorithm for generating permutations generates an unpredictable permutation if its outputs are permutations on a set of items (described by length-n binary strings) that cannot be predicted with accuracy significantly better than random by an adversary that makes a polynomial (in n) number of queries to the oracle prior to the challenge round, whose running time is polynomial in n, and whose error probability is less than 1/2 for all instances.
[5] It can be shown that a function Fk is not a secure message authentication code (MAC) if it satisfies only the unpredictability requirement.
It can also be shown that one cannot build an efficient variable input length MAC from a block cipher which is modelled as a UP of n bits.
[5] Even for realistic Unpredictable Functions (UF), some partial information about the intermediate round values may be leaked through the output.
[6] There is also a theorem that has been proven in this regard which states that if there exists an efficient UP adversary Aπ that has non-negligible advantage επ in the unpredictability game against UP construction ψU,k and which makes a polynomial number of queries to the challenger, then there also exists a UF adversary Af that has non-negligible advantage in the unpredictability game against a UF sampled from the UF family F .
From this, it can be shown that the maximum advantage of the UP adversary Aπ is επ = O (εf.
Here εf denotes the maximum advantage of a UF adversary running in time O(t + (qk)5) against a UF sampled from F, where t is the running time of the PRP adversary Aψ and q is the number of queries made by it.