Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

The proliferation of all kinds of devices with different security requirements and constraints, and the arms-race nature of the security problem are increasingly demanding the development of tools to help on the automatic design of Boolean functions with security application. Nowadays, the design of strong cryptographic Boolean functions is a multiobjective problem. However, so far evolutionary multiobjective algorithms have been largely overlooked and not much is known about this problem from a multiobjective optimization perspective. In this work we focus on non-linearity related criteria and explore a multiobjective evolutionary approach aiming to find several balanced functions of similar characteristics satisfying multiple criteria. We show that the multiobjective approach is an efficient alternative to single objective optimization approaches presented so far. We also argue that it is a better framework for automatic design of cryptographic Boolean functions.

REFERENCES

• 1: T. Siegenthaler, "Correlation Immunity of Non-linear Combining Functions for Cryptographic Applications", IEEE Transactions on Information Theory, vol.30, pp.776--780,1984.
• 2: 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
• 3: E. Biham and A. Shamir "Differential Cryptanalysis of DES-like Cryptosystems", Journal of Cryptology, vol.4, no.1, pp.3--72, 1991.
• 4: H. M. Heys, "A Tutorial on Linear and Differential Cryptanalysis", Technical Report CORR 2001-17, Centre for Applied Cryptographic Research, Department of Combinatorics and Optimization, University of Waterloo, Mar. 2001.
• 5: S. Maitra and E. Pasalic, "Further Constructions of Resilient Boolean Functions with Very High Nonlinearity", IEEE Transactions on Information Theory, 48(7):1825--1834, July 2002.
• 6: E. Pasalic, S. Maitra, T. Johansson, and P. Sarkar, "New Constructions of Resilient and Correlation Immune Boolean Functions Achieving Upper Bound on Nonlinearity", Proc. Workshop on Coding and Cryptography - WCC 2001, Electronic Notes in Discrete Mathematics, vol.6, Elsevier Science, 2001.
• 7: Palash Sarkar , Subhamoy Maitra, Nonlinearity Bounds and Constructions of Resilient Boolean Functions, Proceedings of the 20th Annual International Cryptology Conference on Advances in Cryptology, p.515-532, August 20-24, 2000
• 8: William Millan , Andrew Clark , Ed Dawson, An effective genetic algorithm for finding highly nonlinear Boolean Functions, Proceedings of the First International Conference on Information and Communication Security, p.149-158, November 11-14, 1997
• 9: W. Millan, A. Clark and E. Dawson, "Heuristic Desing of Cryptographically Strong Balanced Boolean Functions", Proc. Advances in Cryptology - EUROCRYPT'98, Springer-Verlag, Lecture Notes in Computer Science, vol.1403, pp.489--499, 1998.
• 10: William Millan , Andrew Clark , Ed Dawson, Boolean Function Design Using Hill Climbing Methods, Proceedings of the 4th Australasian Conference on Information Security and Privacy, p.1-11, April 07-09, 1999
• 11: John Clark , Jeremy Jacob, Two-Stage Optimisation in the Design of Boolean Functions, Proceedings of the 5th Australasian Conference on Information Security and Privacy, p.242-254, July 10-12, 2000
• 12: Kalyanmoy Deb , Deb Kalyanmoy, Multi-Objective Optimization Using Evolutionary Algorithms, John Wiley & Sons, Inc., New York, NY, 2001
• 13: Carlos A. Coello Coello , Gary B. Lamont , David A. Van Veldhuizen, Evolutionary Algorithms for Solving Multi-Objective Problems (Genetic and Evolutionary Computation), Springer-Verlag New York, Inc., Secaucus, NJ, 2006
• 14: C. J. A. Jansen and D.E. Boekee, "The Algebraic Normal Form of Arbitrary Functions over Finite Fields", Proc. 8th Symposium of Information Theory in the Benelux, pp.69--76, 1987.
• 15: X. Lai, "Additive and Linear Structures of Cryptographic Functions", Proc. Fast Software Encription - FSE Leuven Workshop 1994, Springer-Verlag, Lecture Notes in Computer Science, pp.75--85, 1994.
• 16: 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
• 17: H. Aguirre and K. Tanaka, "Effects of Elitism and Population Climbing on Multiobjective MNK-Landscapes", Proc. 2004 IEEE Congress on Evolutionary Computation, IEEE Center, pp.449--456, 2004.
• 18: H. Aguirre and K. Tanaka, "Selection, Drift, Recombination, and Mutation in Multiobjective Evolutionary Algorithms on Scalable MNK-Landscapes", Proc. Third Intl. Conf. on Evolutionary Multi-Criterion Optimization, Springer, LNCS, vol.3410, pp. 355--369, 2005.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization

General Terms:
Algorithms, Design, Performance, Security

Keywords:
cryptography, evolutionary multiobjective optimization, information security, non-linear Boolean functions