A Search for Nonlinear Balanced Boolean Functions by Leveraging Phenotypic Properties
Abstract
In this paper, we consider the problem of finding perfectly balanced Boolean functions with high non-linearity values. Such functions have extensive applications in domains such as cryptography and error-correcting coding theory. We provide an approach for finding such functions by a local search method that exploits the structure of the underlying problem. Previous attempts in this vein typically focused on using the properties of the fitness landscape to guide the search. We opt for a different path in which we leverage the phenotype landscape (the mapping from genotypes to phenotypes) instead. In the context of the underlying problem, the phenotypes are represented by Walsh-Hadamard spectra of the candidate solutions (Boolean functions). We propose a novel selection criterion, under which the phenotypes are compared directly, and test whether its use increases the convergence speed (measured by the number of required spectra calculations) when compared to a competitive fitness function used in the literature. The results reveal promising convergence speed improvements for Boolean functions of sizes N = 6 to N = 9.
References
[1]
Hernán Aguirre, Hiroyuki Okazaki, and Yasushi Fuwa. 2007. An Evolutionary Multiobjective Approach to Design Highly Non-Linear Boolean Functions. In Proceedings of the 9th Annual Conference on Genetic and Evolutionary Computation (London, England) (GECCO '07). Association for Computing Machinery, New York, NY, USA, 749--756.
[2]
M Ali Al-Radhawi, Anh Phong Tran, Elizabeth A Ernst, Tianchi Chen, Christopher A Voigt, and Eduardo D Sontag. 2020. Distributed implementation of Boolean functions by transcriptional synthetic circuits. ACS Synthetic Biology 9, 8 (2020), 2172--2187.
[3]
Ismail Khalil Ali. 2009. Design Strong Boolean Functions Using Memetic Algorithm. Journal of Baghdad College of Economic sciences University 21 (2009).
[4]
Matthieu Basseur and Adrien Goëffon. 2014. On the efficiency of worst improvement for climbing NK-landscapes. In Proceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation. 413--420.
[5]
Matthieu Basseur and Adrien Goëffon. 2015. Climbing combinatorial fitness landscapes. Applied Soft Computing 30 (2015), 688--704.
[6]
Claude Carlet, Yves Crama, and Peter L Hammer. 2010. Boolean Functions for Cryptography and Error-Correcting Codes.
[7]
Claude Carlet, Yves Crama, and Peter L Hammer. 2010. Boolean Functions for Cryptography and Error-Correcting Codes.
[8]
John A Clark and Jeremy L Jacob. 2000. Two-stage optimisation in the design of Boolean functions. In Information Security and Privacy: 5th Australasian Conference, ACISP 2000, Brisbane, Australia, July 10--12, 2000. Proceedings 5. Springer, 242--254.
[9]
J. A. Clark, J. L. Jacob, S. Maitra, and P. Stanica. 2003. Almost Boolean functions: the design of Boolean functions by spectral inversion. In The 2003 Congress on Evolutionary Computation, 2003. CEC '03., Vol. 3. 2173--2180 Vol.3.
[10]
Marko Djurasevic, Domagoj Jakobovic, Luca Mariot, and Stjepan Picek. 2023. Digging Deeper: Operator Analysis for Optimizing Nonlinearity of Boolean Functions. arXiv preprint arXiv:2302.05890 (2023).
[11]
Marko Djurasevic, Domagoj Jakobovic, Luca Mariot, and Stjepan Picek. 2023. A Survey of Metaheuristic Algorithms for the Design of Cryptographic Boolean Functions. arXiv preprint arXiv:2301.08012 (2023).
[12]
Hans Dobbertin. 2005. Construction of bent functions and balanced Boolean functions with high nonlinearity. In Fast Software Encryption: Second International Workshop Leuven, Belgium, December 14--16, 1994 Proceedings. Springer, 61--74.
[13]
Bernard J. Fino and V. Ralph Algazi. 1976. Unified matrix treatment of the fast Walsh-Hadamard transform. IEEE Trans. Comput. 25, 11 (1976), 1142--1146.
[14]
Joanne Fuller, Edward Dawson, and William Millan. 2003. Evolutionary generation of bent functions for cryptography. In The 2003 Congress on Evolutionary Computation, 2003. CEC'03., Vol. 3. IEEE, 1655--1661.
[15]
Edgar Galván-López, Riccardo Poli, Ahmed Kattan, Michael O'Neill, and Anthony Brabazon. 2011. Neutrality in evolutionary algorithms... What do we know? Evolving Systems 2 (2011), 145--163.
[16]
Domagoj Jakobovic, Stjepan Picek, Marcella SR Martins, and Markus Wagner. 2021. Toward more efficient heuristic construction of Boolean functions. Applied Soft Computing 107 (2021), 107327.
[17]
Joel Lehman and Kenneth O Stanley. 2011. Novelty search and the problem with objectives. Genetic programming theory and practice IX (2011), 37--56.
[18]
Luca Manzoni, Luca Mariot, and Eva Tuba. 2021. Tip the Balance: Improving Exploration of Balanced Crossover Operators by Adaptive Bias. In Ninth International Symposium on Computing and Networking, CANDAR 2021 - Workshops, Matsue, Japan, 23--26 November 2021. IEEE, 234--240.
[19]
Luca Manzoni, Luca Mariot, and Eva Tuba. 2022. The Influence of Local Search over Genetic Algorithms with Balanced Representations. arXiv preprint arXiv:2206.10974 (2022).
[20]
Luca Mariot and Alberto Leporati. 2015. Heuristic search by particle swarm optimization of boolean functions for cryptographic applications. In Proceedings of the companion publication of the 2015 annual conference on genetic and evolutionary computation. 1425--1426.
[21]
Luca Mariot and Alberto Leporati. 2015. Heuristic Search by Particle Swarm Optimization of Boolean Functions for Cryptographic Applications. In Proceedings of the Companion Publication of the 2015 Annual Conference on Genetic and Evolutionary Computation (Madrid, Spain) (GECCO Companion '15). Association for Computing Machinery, New York, NY, USA, 1425--1426.
[22]
James McLaughlin and John A. Clark. 2013. Evolving balanced Boolean functions with optimal resistance to algebraic and fast algebraic attacks, maximal algebraic degree, and very high nonlinearity. Cryptology ePrint Archive, Report 2013/011. https://eprint.iacr.org/2013/011.
[23]
William Millan, Andrew Clark, and Ed Dawson. 1997. An effective genetic algorithm for finding highly nonlinear Boolean functions. In Information and Communications Security: First International Conference, ICIS'97 Beijing, China, November 11--14, 1997 Proceedings 1. Springer, 149--158.
[24]
William Millan, Andrew Clark, and Ed Dawson. 1998. Heuristic design of cryptographically strong balanced Boolean functions. In Advances in Cryptology---EUROCRYPT'98: International Conference on the Theory and Application of Cryptographic Techniques Espoo, Finland, May 31--June 4, 1998 Proceedings 17. Springer, 489--499.
[25]
William Millan, Andrew Clark, and Ed Dawson. 1999. Boolean function design using hill climbing methods. In Information Security and Privacy: 4th Australasian Conference, ACISP'99 Wollongong, NSW, Australia, April 7--9, 1999 Proceedings 4. Springer, 1--11.
[26]
Gabriela Ochoa, Sébastien Verel, and Marco Tomassini. 2010. First-improvement vs. best-improvement local optima networks of nk landscapes. In Parallel Problem Solving from Nature, PPSN XI: 11th International Conference, Kraków, Poland, September 11--15, 2010, Proceedings, Part I 11. Springer, 104--113.
[27]
Kenneth G Paterson. 2004. Dentist 2: 00on codes with low peak-to-average power ratio for multicode cdma. IEEE Transactions on Information Theory 50, 3 (2004), 550--559.
[28]
Stjepan Picek, Lejla Batina, and Domagoj Jakobovic. 2014. Evolving DPA-Resistant Boolean Functions. In Parallel Problem Solving from Nature - PPSN XIII, Thomas Bartz-Beielstein, Jürgen Branke, Bogdan Filipič, and Jim Smith (Eds.). Springer International Publishing, Cham, 812--821.
[29]
Stjepan Picek, Claude Carlet, Sylvain Guilley, Julian F Miller, and Domagoj Jakobovic. 2016. Evolutionary algorithms for boolean functions in diverse domains of cryptography. Evolutionary computation 24, 4 (2016), 667--694.
[30]
Stjepan Picek, Sylvain Guilley, Claude Carlet, Domagoj Jakobovic, and Julian F. Miller. 2015. Evolutionary Approach for Finding Correlation Immune Boolean Functions of Order t with Minimal Hamming Weight. In Theory and Practice of Natural Computing, Adrian-Horia Dediu, Luis Magdalena, and Carlos Martín-Vide (Eds.). Springer International Publishing, Cham, 71--82.
[31]
Stjepan Picek, Domagoj Jakobovic, and Marin Golub. 2013. Evolving Cryptographically Sound Boolean Functions. In Proceedings of the 15th Annual Conference Companion on Genetic and Evolutionary Computation (Amsterdam, The Netherlands) (GECCO '13 Companion). Association for Computing Machinery, New York, NY, USA, 191--192.
[32]
Stjepan Picek, Domagoj Jakobovic, Julian F. Miller, Elena Marchiori, and Lejla Batina. 2015. Evolutionary Methods for the Construction of Cryptographic Boolean Functions. In Genetic Programming, Penousal Machado, Malcolm I. Heywood, James McDermott, Mauro Castelli, Pablo García-Sánchez, Paolo Burelli, Sebastian Risi, and Kevin Sim (Eds.). Springer International Publishing, Cham, 192--204.
[33]
Stjepan Picek, Karlo Knezevic, Luca Mariot, Domagoj Jakobovic, and Alberto Leporati. 2018. Evolving Bent Quaternary Functions. In 2018 IEEE Congress on Evolutionary Computation, CEC 2018, Rio de Janeiro, Brazil, July 8--13, 2018. IEEE, 1--8.
[34]
Stjepan Picek, Robert I McKay, Roberto Santana, and Tom D Gedeon. 2015. Fighting the symmetries: The structure of cryptographic boolean function spaces. In Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation. 457--464.
[35]
Stjepan Picek, Roberto Santana, and Domagoj Jakobovic. 2016. Maximal nonlinearity in balanced boolean functions with even number of inputs, revisited. In 2016 IEEE Congress on Evolutionary Computation (CEC). IEEE, 3222--3229.
[36]
Stjepan Picek, Roberto Santana, and Domagoj Jakobovic. 2016. Maximal nonlinearity in balanced boolean functions with even number of inputs, revisited. In 2016 IEEE Congress on Evolutionary Computation (CEC). 3222--3229.
[37]
Stjepan Picek, Dominik Sisejkovic, and Domagoj Jakobovic. 2017. Immunological algorithms paradigm for construction of Boolean functions with good cryptographic properties. Engineering Applications of Artificial Intelligence 62 (2017), 320--330.
[38]
Stjepan Picek, Dominik Sisejkovic, and Domagoj Jakobovic. 2017. Immunological algorithms paradigm for construction of Boolean functions with good cryptographic properties. Engineering Applications of Artificial Intelligence 62 (2017), 320--330.
[39]
Justin K Pugh, Lisa B Soros, and Kenneth O Stanley. 2016. Quality diversity: A new frontier for evolutionary computation. Frontiers in Robotics and AI (2016), 40.
[40]
Rui-Sheng Wang, Assieh Saadatpour, and Reka Albert. 2012. Boolean modeling in systems biology: an overview of methodology and applications. Physical biology 9, 5 (2012), 055001.
[41]
Darrell Whitley, Adele Howe, and Doug Hains. 2013. Greedy or not? best improving versus first improving stochastic local search for MAXSAT. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 27. 940--946.
[42]
Wei-Guo Zhang and Enes Pasalic. 2014. Generalized Maiorana-McFarland construction of resilient Boolean functions with high nonlinearity and good algebraic properties. IEEE Transactions on Information Theory 60, 10 (2014), 6681--6695.
Index Terms
- A Search for Nonlinear Balanced Boolean Functions by Leveraging Phenotypic Properties
Recommendations
Bent and Semi-bent Functions via Linear Translators
IMACC 2015: Proceedings of the 15th IMA International Conference on Cryptography and Coding - Volume 9496The paper is dealing with two important subclasses of plateaued functions: bent and semi-bent functions. In the first part of the paper, we construct mainly bent and semi-bent functions in the Maiorana-McFarland class using Boolean functions having ...
Look into the Mirror: Evolving Self-dual Bent Boolean Functions
Genetic ProgrammingAbstractBent Boolean functions are important objects in cryptography and coding theory, and there are several general approaches for constructing such functions. Metaheuristics proved to be a strong choice as they can provide many bent functions, even ...
Constructing Hyper-Bent Functions from Boolean Functions with the Walsh Spectrum Taking the Same Value Twice
Sequences and Their Applications - SETA 2014AbstractHyper-bent functions as a subclass of bent functions attract much interest and it is elusive to completely characterize hyper-bent functions. Most of known hyper-bent functions are Boolean functions with Dillon exponents and they are often ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
July 2023
2519 pages
Copyright © 2023 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 24 July 2023
Check for updates
Author Tags
Qualifiers
- Research-article
Conference
GECCO '23 Companion
Sponsor:
GECCO '23 Companion: Companion Conference on Genetic and Evolutionary Computation
July 15 - 19, 2023
Lisbon, Portugal
Acceptance Rates
Overall Acceptance Rate 1,669 of 4,410 submissions, 38%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 29Total Downloads
- Downloads (Last 12 months)11
- Downloads (Last 6 weeks)0
Reflects downloads up to 25 Dec 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in