EPFL - I&C - ISC - LASEC
Station 14 - Building INF
CH-1015 Lausanne
Switzerland
Tel. +41 21 693 7603
Fax. +41 21 693 7689
Last update: July 15th, 2002.
For this we consider block ciphers as random permutations in a mathematical sense: the random choice of the secret key K induce a distribution on the permutation C_{K}. In the following we will omit the reference to the key.
The goal of the designer of the block cipher is to make it "look like" a truly random permutation, i.e. like a random permutation C^{*} with a uniform distribution among the set of permutations. For this we need tools to compare C and C^{*}.
Intuitively, we can compare C and C^{*} at different level of depth. Namely, if for any fixed plaintext x the corresponding ciphertext C(x) is uniformly distributed, we say that C and C^{*} are similar "to the order 1". Similarly, if for any two different plaintexts x_{1} and x_{2} the corresponding ciphertext pair (C(x_{1}),C(x_{2})) has a uniform distribution among all the pairs of different ciphertexts, we say that C and C^{*} are similar "to the order 2". And so on. This intuitively defined the notion of order of decorrelation.
Beginners do not really need to understand where this matrix come from. For the others, here is the formal definition.
The most important property we need to know is the following.
Interestingly, if C^{*} denotes the ideal random permutation (which means it has a uniform distribution), we have
In the introduction was addressed the problem of comparing a cipher C to the ideal cipher C^{*} "to a given order". Now we can be a little more precise. We will compare [C]^{d} and [C^{*}]^{d}.
Random functions F must be compared to an ideal random function F^{*} which has a uniform distribution. For this we define
Similarly, ciphers C must be compared to the ideal cipher C^{*}, and we define
The question on the choice of the norm remains.
What we can already notice is that a decorrelation distance of zero do not
depend on this choice, but holds for any norm.
Thus we say that
F and G have the same decorrelation of order d
if their d-wise decorrelation distance is zero.
Similarly, we say that a
function F is perfectly decorrelated to the order d
if its d-wise decorrelation bias is zero.
We say that a cipher C is perfectly decorrelated to the order d
if its d-wise decorrelation bias is zero.
We can notice the link with well-known combinatorial properties. First of all, when a cipher C is perfectly decorrelated to the order 1, it obviously achieve perfect secrecy in Shannon's sense when used only once. Second we notice that a random hash function H is perfectly decorrelated to the order 2 if, and only if it is strong universal_{2} hash function in Carter-Wegman's sense. (See Ref. [CW79,WC81].)
We have an equivalent to the Shannon Theorem.
Hence we need a lot of random bits in order to construct perfectly decorrelated functions.
If we measure decorrelation biases with matrix norms, from the property of matrix norms, the definitions and Proposition 2, we have the interesting property that
For the fourth problem, the strategy consists of considering any regular conservative designs, and plugging into it a few decorrelated primitives which are called decorrelation modules. If we choose the right notion of decorrelation (the right norm), the rights decorrelation modules and plug them in the right positions, we obtain a decorrelated cipher which may be protected against the right attacks.
A much more convenient norm is the |||.|||_{oo} norm. For any matrix A, the norm |||A|||_{oo} is the maximum over all rows of the sum of the absolute values of all entries:
Other interesting matrix norms are the ||.||_{a} norm and the ||.||_{s} norm defined by
Here are important results which motivate the choice of the |||.|||_{oo}, ||.||_{a} and ||.||_{s} matrix norms.
This formalism turns out to make trivial (from the matrix norm properties) the following intuitive results. If we consider r independent instances C_{1}, ..., C_{r} of the same cipher C, we consider the iterated cipher C_{r}o...oC_{1}. We have
The first possibility consists of choosing the maximal prime p smaller than 2^{m}. Let us write
It shall be outlined that it makes trivial the extension of Luby-Rackoff Theorem to pseudorandom functions instead of random ones: assuming that the advantage of any distinguisher which is limited to d chosen plaintext is at most epsilon against any round function F_{i} of a Feistel construction with at least three rounds, we obtain that any distinguisher which is limited to d chosen plaintext against the Feistel cipher is at most
We can use the following constructions.
In Ref. [Stacs98] was propose the Coconut98 cipher with a perfect pairwise decorrelation with
In Ref. [Aes98] (see also Ref. [Aes99]) was propose the DFC cipher with pairwise decorrelation with
These are the NUT-IV decorrelation module. In Ref. [Sac98] this construction was adapted to the L_{2} norm in order to propose the Peanut97 cipher with pairwise decorrelation with
Other constructions can be adapted. In the literature we can find many theorems of constructions in the ideal cases. For instance Ref. [ZMI89] investigates generalized Feistel schemes with more than two branches. Ref. [NR99] improves the Luby-Rackoff construction by using the same round functions several times. Ref. [PRS99] investigates a new construction, ...
Given a function f we define
There is a similar treatment for linear distinguishers. They are formalized by n,a,b and an acceptance set B:
This treatment is quite useful when desiging block ciphers: if we manage to construct one with low decorrelation of order 2, we can guaranty for free that no differential or linear characteristic has a useful bias on average over the distribution of the key.
[CW79] | Universal Classes of Hash Functions. By Carter and Wegman. In Journal of Computer and System Sciences vol. 18, pp. 143-154, 1979. |
[WC81] | New Hash Functions and their Use in Authentication and Set Equality. By Wegman and Carter. In Journal of Computer and System Sciences vol. 22, pp. 265-279, 1981. |
[LR88] | How to Construct Pseudorandom Permutations from Pseudorandom Functions. By Luby and Rackoff. In SIAM Journal on Computing vol. 17, pp. 373-386, 1988. |
[CG89] | On the Power of Two-Point Based Sampling. By Chor and Goldreich. In Jounal of Complexity vol. 5, pp. 96-106, 1989. |
[ZMI89] | Impossibility and Optimality Results on Constructing Pseudorandom Permutations. By Zheng, Matsumoto and Imai. In EUROCRYPT' 89, pp. 412-422, LNCS 434, Springer-Verlag, 1990. |
[LM90] | A Proposal for a New Block Encryption Standard. By Lai and Massey. In EUROCRYPT' 90, pp. 389-404, LNCS 473, Springer-Verlag, 1991. |
[Lai92] | On the Design and Security of Block Ciphers. By Lai. In ETH Series in Information Processing vol. 1, Hartung-Gorre Verlag Konstanz, 1992. |
[Liens-97-3] | A Cheap Paradigm for Block Cipher Security Strengthening. Technical report LIENS-97-3, Ecole Normale Supérieure, 1997. |
[Stacs98] | Provable Security for Block Ciphers by Decorrelation. In STACS' 98, pp. 249-275, LNCS 1373, Springer-Verlag, 1998. |
[Sac98] | Feistel Ciphers with L_{2} Decorrelation. In SAC' 98, pp. 1-14, LNCS 1556, Springer-Verlag, 1999. |
[Aes98] | Decorrelated Fast Cipher: an AES Candidate. By Gilbert, Girault, Hoogvoorst, Noilhan, Pornin, Poupard, Stern and Vaudenay. In the Proceedings from the First Advanced Encryption Standard Candidate Conference, National Institute of Standards and Technology (NIST), 1998. |
[NR99] | On the Construction of Pseudorandom Permutations: Luby-Rackoff Revisited. By Naor and Reingold. In Journal of Cryptology vol. 12, pp. 29-66, 1999. |
[Aes99] | DFC Update. By Baudron, Gilbert, Granboulan, Handschuh, Harley, Joux, Nguyen, Noilhan, Pointcheval, Pornin, Poupard, Stern and Vaudenay. In the Proceedings from the Second Advanced Encryption Standard Candidate Conference, National Institute of Standards and Technology (NIST), 1999. |
[PRS99] | Towards Making Luby-Rackoff Ciphers Optimal and Practical. By Patel, Ramzan, Sundaram. In Fast Software Encryption' 99, pp. 171-185, LNCS 1636, Springer-Verlag, 1999. |
[Eurocrypt99] | Resistance Against General Iterated Attacks. In EUROCRYPT' 99, pp. 255-271, LNCS 1592, Springer-Verlag, 1999. |
[Sac99] | Adaptive-Attack Norm for Decorrelation and Super-Pseudorandomness. Technical report LIENS-99-2, Ecole Normale Supérieure, 1999. To appear in SAC'99. |
[Asiacrypt99] | On the Lai-Massey Scheme. Technical report LIENS-99-3, Ecole Normale Supérieure, 1999. To appear in ASIACRYPT'99. |