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 [15]. He proved that the very simple Vernam Cipher (also known as one-time pad) provides perfect secrecy [18]. 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) [1]. 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) [8].
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 [11], Nyberg and Knudsen [12] and Chabaud and Vaudenay [5]. We also use the analysis of the network from Heys and Tavares [6].
Second, we review another approach for getting proven security against differential and linear cryptanalysis from a Theorem due to Nyberg and Knudsen [12] recently improved by Aoki and Ohta [2]. We also discuss about a nice construction from Matsui [9].
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 [10]) to get other design criteria.
Finally, we discuss about a theoretical approach due to Luby and Rackoff [7] which has been improved by Patarin [13] 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 [14]. This would correspond to the strongest possible security.
[1] Data Encryption Standard. Federal Information Processing Standard Publication 46, U. S. National Bureau of Standards, 1977.
[2] 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.
[3] 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.
[4] E. Biham, A. Shamir. Differential Cryptanalysis of the Data Encryption Standard, Springer-Verlag, 1993.
[5] 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, 1995.
[6] H. M. Heys, S. E. Tavares. Substitution-Permutation Networks resistant to differential and linear cryptanalysis. Journal of Cryptology, vol. 9, pp. 1-19, 1996.
[7] M. Luby, C. Rackoff. How to construct pseudorandom permutations from pseudorandom functions. SIAM Journal on Computing, vol. 17, pp. 373- 386, 1988.
[8] 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, 1994.
[9] 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.
[10] S. Murphy, F. Piper, M. Walker, P. Wild. Likehood estimation for block cipher keys. Unpublished.
[11] 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.
[12] K. Nyberg, L. R. Knudsen. Provable security against a differential cryptanalysis. Journal of Cryptology, vol. 8, pp. 27-37, 1995.
[13] 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.
[14] J. Patarin. In Advances in Cryptology EUROCRYPT'92, Balatonfured, Hungary, Lectures Notes in Computer Science 658, pp. 256-266, SpringerVerlag, 1993.
[15] C. E. Shannon. Communication theory of secrecy systems. Bell system technical journal, vol. 28, pp. 656- 715, 1949.
[16] 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.
[17] 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.
[18] 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.