Abstract
Advances in the design of Boolean functions using heuristic techniques are reported. A genetic algorithm capable of generating highly nonlinear balanced Boolean functions is presented. Hill climbing techniques are adapted to locate balanced, highly nonlinear Boolean functions that also almost satisfy correlation immunity. The definitions for some cryptographic properties are generalised, providing a measure suitable for use as a fitness function in a genetic algorithm seeking balanced Boolean functions that satisfy both correlation immunity and the strict avalanche criterion. Results are presented demonstrating the effectiveness of the methods.
Chapter PDF
Similar content being viewed by others
References
E. Biham and A. Shamir. Differential cryptanalysis of DES-like cryptosystems. In Advances in Cryptology — Crypto '90, Proceedings, LNCS, volume 537, pages 2–21. Springer-Verlag, 1991.
C. Carlet. Partially-Bent Functions. In Advances in Cryptology — Crypto '92, Proceedings, LNCS, volume 740, pages 280–291. Springer-Verlag, 1993.
A. Clark and E. Dawson. A Parallel Genetic Algorithm for Cryptanalysis of the Polyalphabetic Substitution Cipher. Cryptologia, 21(2):129–138, April 1997.
A. Clark, E. Dawson, and H. Bergen. Combinatorial Optimisation and the Knapsack Cipher. Cryptologia, 20(1):85–93, January 1996.
E. Dawson and A. Clark. Discrete Optimisation: A Powerful Tool for Cryptanalysis? In Proceedings of Pragocrypt '96, pages 425–451, 1996.
H. Dobbertin. Construction of Bent Functions and Balanced Boolean Functions with High Nonlinearity. In Fast Software Encryption, 1994 Leuven Workshop, LNCS, volume 1008, pages 61–74. Springer-Verlag, 1994.
T. Honda, T. Satoh, T. Iwata, and K. Kurosawa. Balanced Boolean functions satisfying PC(2) and very large degree. In Workshop on Selected Areas in Cryptology 1997, Workshop Record, pages 64–72, 1997.
X.-D. Hou. On the Norm and Covering Radius of the First-Order Reed-Muller Codes. IEEE Transactions on Information Theory, 43(3):1025–1027, May 1997.
F.J. MacWilliams and N.J.A. Sloane. The Theory of Error Correcting Codes. North-Holland Publishing Company, Amsterdam, 1978.
M. Matsui. Linear Cryptanalysis Method for DES Cipher. In Advances in Cryptology — Eurocrypt '93, Proceedings, LNCS, volume 765, pages 386–397. Springer-Verlag, 1994.
Robert A. J. Matthews. The use of genetic algorithms in cryptanalysis. Cryptologia, 17(2): 187–201, April 1993.
W. Millan, A. Clark, and E. Dawson. An Effective Genetic Algorithm for Finding Highly Nonlinear Boolean Functions. In First International Conference on Information and Communications Security, volume 1334 of Lecture Notes in Computer Science, pages 149–158. Springer-Verlag, 1997.
W. Millan, A. Clark, and E. Dawson. Smart Hill Climbing Finds Better Boolean Functions. In Workshop on Selected Areas in Cryptology 1997, Workshop Record, pages 50–63, 1997.
N.J. Patterson and D.H. Wiedemann. The Covering Radius of the (215,16) Reed-Muller Code is at least 16276. IEEE Transactions on Information Theory, 29(3):354–356, May 1983.
B. Preneel. Analysis and Design of Cryptographic Hash Functions. PhD thesis, Cathoic University of Leuven, 1994.
B. Preneel, W. Van Leekwijck, L. Van Linden, R. Govaerts, and J. Vandewalle. Propagation Characteristics of Boolean Functions. In Advances in Cryptology — Eurocrypt '90, Proceedings, LNCS, volume 473, pages 161–173. Springer-Verlag, 1991.
M. Schneider. On the Construction and Upper Bounds of Balanced and Correlation-immune Functions. In Workshop on Selected Areas in Cryptology 1997, Workshop Record, pages 73–87, 1997.
J. Seberry, X.-M. Zhang, and Y. Zheng. Nonlinearly balanced boolean functions and their propagation characteristics. In Advances in Cryptology — Crypto '93, Proceedings, LNCS, volume 773, pages 49–60. Springer-Verlag, 1994.
J. Seberry, X.-M. Zhang, and Y. Zheng. On Constructions and Nonlinearity of Correlation Immune Functions. In Advances in Cryptology — Eurocrypt '93, Proceedings, LNCS, pages 181–199. Springer-Verlag, 1994.
T. Siegenthaler. Correlation-Immunity of Nonlinear Combining Functions for Cryptographic Applications. IEEE Transactions on Information Theory, 30(5):776–780, September 1984.
J.J. Son, J.I. Lim, S. Chee, and S.H. Sung. Global Avalanche Characteristics and Nonlinearity of Balanced Boolean Functions, 1997. Submtted to Information Processing Letters.
R. Spillman. Cryptanalysis of Knapsack Ciphers using Genetic Algorithms. Cryptologia, 17(4):367–377, October 1993.
R. Spillman, M. Janssen, B. Nelson, and M. Kepner. Use of a Genetic Algorithm in the Cryptanalysis of Simple Substitution Ciphers. Cryptologia, 17(1):31–44, January 1993.
D.R. Stinson. Resilient functions and large sets of orthogonal arrays. Congressus Numerantium, 92:105–110, 1993.
A.F. Webster and S.E. Tavares. On the Design of S-Boxes. In Advances in Cryptology — Crypto '85, Proceedings, LNCS, volume 218, pages 523–534. Springer-Verlag, 1986.
G-Z. Xiao and J.L. Massey. A Spectral Characterization of Correlation-Immune Combining Functions. IEEE Transactions on Information Theory, 34(3):569–571, May 1988.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1998 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Millan, W., Clark, A., Dawson, E. (1998). Heuristic design of cryptographically strong balanced Boolean functions. In: Nyberg, K. (eds) Advances in Cryptology — EUROCRYPT'98. EUROCRYPT 1998. Lecture Notes in Computer Science, vol 1403. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0054148
Download citation
DOI: https://doi.org/10.1007/BFb0054148
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-64518-4
Online ISBN: 978-3-540-69795-4
eBook Packages: Springer Book Archive
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.