The Decorrelation Technique
Last update: September 7th, 2000.
Content of this Document
Digital criminality is nowadays a big threat for the electronic marketplace.
For this reason, cryptography provides various algorithms based on a heart
cryptographic primitive: encryption. The Digital Encryption Standard (DES)
has been developed by IBMTM for the US Department of Commerce in the
seventies for this purpose, but its secret-key length (56 bits) provides no
sufficient security at this time, so this standard is now over.
So far, real-life encryption algorithms used to have an empirical-based
security: they were designed from an intricate substitution-permutation
network and believed to be secure until someone published an attack on them.
In parallel, research yielded several general attacks strategies, namely
Biham and Shamir's "differential cryptanalysis", and Matsui's "linear
cryptanalysis" (both are particular cases of the more general "iterated
attacks of order 2"), which provided a better understanding on how to manage
with security arguments.
The laboratory of computer sciences of the Ecole Normale Supérieure,
associated with the Centre National de la Recherche Scientifique (CNRS),
has recently developed a technique for making new encryption algorithms with
a provable security against any iterated attacks of a fixed order (e.g. of
order 2). Several properties of this technique - known as decorrelation -
have been presented at international research conferences. Additionally,
decorrelation has been used in order to propose a candidate for the
"Advanced Encryption Standard" process of the US Department of Commerce.
Provable security is an important added value for cryptographic algorithms
and is currently a hot topic in international conferences. The decorrelation
technique is a part of this program.
- 1997.
The SPI (Engineering Sciences Department of the CNRS)
published a booklet 100 Faits Marquants du Département des
Sciences Pour l'Ingénieur
which includes a pointer to the decorrelation technique (p. 15) as one of the
100 important facts in this department.
- Feb 26, 1998.
Provable Security for Block Ciphers by Decorrelation.
(Invited lecture at the STACS'98 conference)
The paper contains most of the basic materials and provide results with
the infinity-associated norm only.
- May, 1998.
Feistel Ciphers with L_2-Decorrelation.
(Published in SAC'98)
Results on the L2 decorrelation.
- May, 1998.
(External link) link to the INPI
(French National Institute for Industrial Property) where information on the
patent appliance WO9820643 on decorrelation can be found.
The patent has been applied on 04/11/1996 and is being extended through PCT.
- July, 1998.
DFC: an AES Candidate.
(Extended Abstract submitted to the AES process).
See also the DFC Web Page.
- April, 1999.
Comparison of the Randomness Provided by Some AES Candidates.
(Presented at the AES workshop #2, work still in progress).
Compare of several generalized Feistel constructions in term of
pseudorandomness and decorrelation (CAST256, MARS, ...).
- June, 1999.
Resistance Against General Iterated Attacks.
(Published in EUROCRYPT'99)
Security proofs of decorrelated ciphers against general iterated
attacks.
- August, 1999.
Adaptive-Attack Norm for Decorrelation and Super-Pseudorandomnes.
(Published in SAC'99)
Definition of the ||.||a and ||.||s norms,
relation to adaptive chosen plaintext and ciphertext attacks.
- November, 1999.
On the Lai-Massey Scheme.
(To appear in ASIACRYPT'99)
Results on the randomness and the decorrelation provided by the
Lai-Massey scheme (which is used in IDEA).
- December, 1999.
On Provable Security for Conventional Cryptography.
(To appear in ICISC'99)
Systematic proof of Luby-Rackoff-like results.
- August, 2000.
Decorrelation over Infinite Domains: the Encrypted CBC-MAC Case.
(To appear in SAC'00 and
Communications in Information and Systems (CIS))
Application of decorrelation theory to MAC, and the CBC-MAC
example.
- December, 2000.
On the Pseudorandomness of Top-Level Schemes of Block Ciphers
by S. Moriai and S. Vaudenay.
(To be presented at ASIACRYPT'00)
Application of decorrelation theory to the structure of CAST256, MARS,
RC6 and Rijndael.