Extended Abstract:- In the early 40's, the second world war raised the big issue of providing
secrecy for electronic telecommunication. Of course, this was for military purposes, but it also
initiated similar inquiries for commercial use. In 1949, Shannon published the first (public)
scientific treatment of encryption . He proved that the very simple Vernam Cipher (also
known as one-time pad) provides perfect secrecy . This encryption algorithm is however
not really an encryption function because the sender and the receiver need to be synchronized.
It also uses a quite cumbersome huge secret key.
For banking matters, the U.S. Government developed in 1977 the Data Encryption Standard
(DES) which is a 4-bit to 64-bit encryption function that uses a small secret key (namely 56
bits) . This was build around the Feistel scheme (from the name of the designer of the
preliminary version), which appears to be very efficient. It however has no proven security,
and its development criteria have been kept secret. Since then, researchers from this area have
been working on its cryptanalysis.
During twenty years, only two important approaches inspired new knowledge about the
security of DES. First, Biham and Shamir discovered in the early 90's the notion of differential
cryptanalysis which gave the first (theoretical) attack against DES better than exhaustive search
(namely with complexity 2 17 instead of 255) [3, 4]. Later on, Matsui discovered a quite dual
approach, called linear cryptanalysis which raised the first experimental attack of DES (with
complexity 243) .
Now, the DES is getting old, and we have new applications for encryption. For instance,
security purposes on Internet require high rate encryption. We thus need a global approach for
security on block ciphers.
In this talk, we investigate different approaches for providing security against
both differential and linear cryptanalysis. First, we review a heuristic approach
that consists in designing strong computation boxes in strong computation networks. We use the strength analysis
from Nyberg , Nyberg and Knudsen
 and Chabaud and Vaudenay . We also use the analysis of the network from Heys and Tavares .
Second, we review another approach for getting proven security against
differential and linear cryptanalysis from a Theorem due to Nyberg and Knudsen
 recently improved by Aoki and Ohta . We also discuss about a nice
construction from Matsui .
We also try to generalize the analysis method into statistical attacks (by using the general frame independently
found by Vaudenay [16, 17] and Murphy, Piper, Walker and Wild ) to get other design criteria.
Finally, we discuss about a theoretical approach due to Luby and Rackoff  which has been improved by Patarin
 proved that a n-bit to n-bit three-
round Feistel scheme is secure for about 2^(n/4) uses when using a 3n/2 2^(n/2) -bit secret
key. Patarin also conjectured that some special four-round Feistel scheme may
be secure for 2^(n/2) uses with a n 2^(n/2)-bit key . This would correspond to the strongest possible security.
 Data Encryption Standard. Federal Information Processing Standard Publication 46, U. S. National
Bureau of Standards, 1977.
 K. Aoki, K. Ohta. Strict evaluation of the maximum average of differential probability and the maximum
average of linear probability. IEICE Transactions on Fundamentals, vol. E80-A, pp. 1-8, 1997.
 E. Biham, A. Shamir. Differential cryptanalysis of the full 16-round DES.
In Advances in Cryptology CRYPTO'92, Santa Barbara, California, U.S.A., Lectures Notes in Computer
Science 740, pp. 487-496, Springer-Verlag, 1993.
 E. Biham, A. Shamir. Differential Cryptanalysis of the Data Encryption Standard, Springer-Verlag, 1993.
 F. Chabaud, S. Vaudenay. Links between differential and linear cryptanalysis. In Advances in Cryptology
EUROCRYPT'94, Perugia, Italy, Lectures Notes in Computer Science 950, pp. 356-365, Springer-Verlag,
 H. M. Heys, S. E. Tavares. Substitution-Permutation Networks resistant to differential and linear
cryptanalysis. Journal of Cryptology, vol. 9, pp. 1-19, 1996.
 M. Luby, C. Rackoff. How to construct pseudorandom permutations from
pseudorandom functions. SIAM Journal on Computing, vol. 17, pp. 373-
 M. Matsui. The first experimental cryptanalysis of the Data Encryption Standard. In Advances in Cryptology
CRYPTO'94, Santa Barbara, California, U.S.A., Lectures Notes in Computer Science 839, pp. 1-11, SpringerVerlag,
 M. Matsui. New structure of block ciphers with provable security against
differential and linear cryptanalysis. In Fast Software Encryption, Cambridge, United Kingdom, Lectures
Notes in Computer Science 1039, pp. 205-218, Springer-Verlag, 1996.
 S. Murphy, F. Piper, M. Walker, P. Wild. Likehood estimation for block cipher keys. Unpublished.
 K. Nyberg. Perfect nonlinear S-boxes. In Advances in Cryptology EUROCRYPT'91, Brighton, United
Kingdom, Lectures Notes in Computer Science 547, pp. 378-385, Springer-Verlag, 1991.
 K. Nyberg, L. R. Knudsen. Provable security against a differential cryptanalysis. Journal of Cryptology, vol.
8, pp. 27-37, 1995.
 J. Patarin. Etude des Ge'ne'rateurs de Permutations Base's sur le Sche'ma du D.E.S., The'se de Doctorat de
l'Universite' de Paris 6, 1991.
 J. Patarin. In Advances in Cryptology EUROCRYPT'92, Balatonfured, Hungary, Lectures Notes in
Computer Science 658, pp. 256-266, SpringerVerlag, 1993.
 C. E. Shannon. Communication theory of secrecy systems. Bell system technical journal, vol. 28, pp. 656-
 S. Vaudenay. La Se'curite' des Primitives Cryptographiques, The'se de Doctorat de l'Universite' de Paris 7,
Technical Report LIENS-95-10 of the Laboratoire d'Informatique de I'Ecole Normale Supe'ieure, 1995.
 S. Vaudenav. An experiment on DES - Statistical cryptanalysis. In 3rd ACM Conference on Computer and
Communications Security, New Delhi, India, pp. 139-147, ACM Press, 1996.
 G. S. Vernam. Cipher printing telegraph systems for secret wire and radio telegraphic communications.
Journal of the American Institute of Electrical Engineers, vol. 45, pp. 109-115, 1926.