Information leakage of boolean functions and its relationship to other cryptographic criteria

ABSTRACT

This paper presents some results on the cryptographic strength of Boolean functions from the information theoretic point of view. It is argued that a Boolean function is resistant to statistical analysis if there is no significant static and dynamic information leakage between its inputs and its output(s). In particular we relate information leakage to nonlinearity, higher order SAC, correlation immunity and resilient functions. It is shown that reducing information leakage increases resistance to the differential attack and the linear attack. We note that some conventional cryptographic criteria require zero static or dynamic information leakage in only one domain. Such a requirement can result in a large information leakage in another domain. To avoid this weakness, it is better to jointly constrain all kinds of information leakage in the function. In fact, we claim that information leakage can be used as a fundamental measure of the strength of a cryptographic algorithm.

REFERENCES

• 1: T. Siegenthaler. Decryption a Class of S~ Ciphers Using Ciphertext Only. IEEE Transactions on Computer, Vol. C-34, No. 1:81-85, 1985.
• 2: S. Mund, D. Gohlmann, and T. Beth. Some Remarks on the Cross Correlation Analysis of Pseudo Random Generators. Advances in Cryptology, Proceedings of Eurocrypt' 87, Springer- Verlag, pages 25-35, 1988.
• 3: Willi Meier , Othmar Staffelbach, Fast correlation attacks on certain stream ciphers, Journal of Cryptology, v.1 n.3, p.159-176, 1989 [doi>10.1007/BF02252874]
• 4: E. Biham and A. Shamir. Differential Cryptanalysis of DES-like Cryptosystems. Journal of Cryptology, Vol. 4:3-72, 1991.
• 5: Mitsuru Matsui, Linear cryptanalysis method for DES cipher, Workshop on the theory and application of cryptographic techniques on Advances in cryptology, p.386-397, January 1994, Lofthus, Norway
• 6: R. Forré, Methods and instruments for designing S-Boxes, Journal of Cryptology, v.2 n.3, p.115-130, 1990
• 7: M.H. Dawson and S.E. Tavares. An Expanded Set of S-box Design Criteria Based on Information Theory and its Relation to Differential Attacks. Advances in Cryptology, Procee&'ngs of Eurocrypt'91, Springer- Verlag, pages 352-365, 1992.
• 8: M. Sivabalan , Stafford E. Tavares , Lloyd E. Peppard, On the Design of SP Networks From an Information Theoretic Point of View, Proceedings of the 12th Annual International Cryptology Conference on Advances in Cryptology, p.260-279, August 16-20, 1992
• 9: L. Brynielsson. The Information Leakage through a Randomly Generated Function. Advances in Cryptology, Proceedings of Eurocrypt'91, Springer- Verlag, pages 552-553, 1992.
• 10: J.B. Kam and G.I. Davida. Structured Design of Substitution-Permutation Encryption Networks. IEEE Transaction on Computers, C-28:747-753, 1979.
• 11: A F Webster , S E Tavares, On the design of S-boxes, Lecture notes in computer sciences; 218 on Advances in cryptology---CRYPTO 85, p.523-534, June 1986, Santa Barbara, California, United States
• 12: T. Siegenthaler. Ccrrelation-lmmunity of Nonlinear Combining Functions for Cryptographic Applicarims. IEEE Transactions on Info. Theory, VoI.IT-30, No.5:776--780, Sept. 1984.
• 13: Willi Meier , Othmar Staffelbach, Nonlinearity criteria for cryptographic functions, Proceedings of the workshop on the theory and application of cryptographic techniques on Advances in cryptology, p.549-562, November 1990, Houthalen, Belgium
• 14: C. M. Adams and S.E. Tavares. The Use of Bent Sequences to Achieve Higher-Order Strict Avalanche Criterion in S-Box Design. Techn. Rept. TR 90--013, Dept. of Electrical Engineering, Queen's University, Kingston, Ontario, 1990.
• 15: Carlisle M. Adams, On immunity against Biham and Shamir's “differential cryptanalysis”, Information Processing Letters, v.41 n.2, p.77-80, Feb. 14, 1992 [doi>10.1016/0020-0190(92)90258-W]
• 16: Bart Preneel , Werner Van Leekwijck , Luc Van Linden , René Govaerts , Joos Vandewalle, Propagation characteristics of Boolean functions, Proceedings of the workshop on the theory and application of cryptographic techniques on Advances in cryptology, p.161-173, February 1991, Aarhus, Denmark
• 17: R. Forré, The strict avalanche criterion: spectral properties of boolean functions and an extended definition, Proceedings on Advances in cryptology, p.450-468, February 1990, Santa Barbara, California, United States
• 18: Thomas M. Cover , Joy A. Thomas, Elements of information theory, Wiley-Interscience, New York, NY, 1991
• 19: J.-H. Evertse. Linear Structures in the Block Ciphers. Advances in Cryptology, Proceedings of Eurocrypt'87, Springer-Verlag, pages 249-266, 1988.
• 20: Sheelagh Lloyd, Counting functions satisfying a higher order strict avalanche criterion, Proceedings of the workshop on the theory and application of cryptographic techniques on Advances in cryptology, p.63-74, November 1990, Houthalen, Belgium
• 21: B. Chor, O. Goldreich, J. Hastad, J. Friedman, S. Rudich, and R. Smolensky. The Bit Extraction Problem or t-resilient Functions. Proc. 26th IEEE Symposium on Foundations of Computer Science, pages 396--407, 1985.
• 22: Charles H. Bennett , Gilles Brassard , Jean-Marc Robert, Privacy amplification by public discussion, SIAM Journal on Computing, v.17 n.2, p.210-229, April 1988 [doi>10.1137/0217014]
• 23: G.Z. Xiao and J.L. Massey. A Spectral Characterization of Correlation-lmmune Combing Functions. IEEE Transactions lnfo. Theory, Vol IT-34:569-571, 1988.
• 24: B. Preneel, R. Govaerts, and J. Vandewalle. Boolean Functions Satisfying Higher Order Propagation Critexia. Advances in Cryptology, Proceedings of Eurocrypt'91, SpringeroVerla&, pages 141-152, 1992.

INDEX TERMS

Primary Classification:
  E. Data

Additional Classification:
  E. Data

General Terms:
Theory, Verification