research-article

Correlation Immunity of Boolean Functions: An Evolutionary Algorithms Perspective

Authors:

Domagoj Jakobovic,

Julian F. Miller,

Lejla BatinaAuthors Info & Claims

GECCO '15: Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation

Pages 1095 - 1102

https://doi.org/10.1145/2739480.2754764

Published: 11 July 2015 Publication History

Abstract

Boolean functions are essential in many stream ciphers. When used in combiner generators, they need to have sufficiently high values of correlation immunity, alongside other properties. In addition, correlation immune functions with small Hamming weight reduce the cost of masking countermeasures against side-channel attacks. Various papers have examined the applicability of evolutionary algorithms for evolving cryptographic Boolean functions. However, even when authors considered correlation immunity, it was not given the highest priority. Here, we examine the effectiveness of three different EAs, namely, Genetic Algorithms, Genetic Programming (GP) and Cartesian GP for evolving correlation immune Boolean functions. Besides the properties of balancedness and correlation immunity, we consider several other relevant cryptographic properties while maintaining the optimal trade-offs among them. We show that evolving correlation immune Boolean functions is an even harder objective than maximizing nonlinearity.

References

[1]

In J. F. Miller, editor, Cartesian Genetic Programming, Natural Computing Series. Springer Berlin Heidelberg, 2011.

[2]

S. Bhasin, C. Carlet, and S. Guilley. Theory of masking with codewords in hardware: low-weight dth-order correlation-immune boolean functions. Cryptology ePrint Archive, Report 2013/303, 2013. http://eprint.iacr.org/.

[3]

L. Burnett, W. Millan, E. Dawson, and A. Clark. Simpler methods for generating better Boolean functions with good cryptographic properties. Australasian Journal of Combinatorics, 29:231--247, 2004.

[4]

P. Camion and A. Canteaut. Correlation-immune and resilient functions over a finite alphabet and their applications in cryptography. Des. Codes Cryptography, 16(2):121--149, 1999.

Digital Library

[5]

C. Carlet. Boolean Functions for Cryptography and Error Correcting Codes. In Y. Crama and P. L. Hammer, editors, Boolean Models and Methods in Mathematics, Computer Science, and Engineering, pages 257--397. Cambridge University Press, New York, NY, USA, 1st edition, 2010.

[6]

C. Carlet, J.-L. Danger, S. Guilley, and H. Maghrebi. Leakage squeezing of order two. In S. Galbraith and M. Nandi, editors, Progress in Cryptology - INDOCRYPT 2012, volume 7668 of Lecture Notes in Computer Science, pages 120--139. Springer Berlin Heidelberg, 2012.

[7]

C. Carlet and K. Feng. An Infinite Class of Balanced Functions with Optimal Algebraic Immunity, Good Immunity to Fast Algebraic Attacks and Good Nonlinearity. In J. Pieprzyk, editor, Advances in Cryptology - ASIACRYPT 2008, volume 5350 of Lecture Notes in Computer Science, pages 425--440. Springer Berlin Heidelberg, 2008.

Digital Library

[8]

C. Carlet and S. Guilley. Side-channel indistinguishability. In Proceedings of the 2Nd International Workshop on Hardware and Architectural Support for Security and Privacy, HASP '13, pages 9:1--9:8, New York, NY, USA, 2013. ACM.

Digital Library

[9]

C. Carlet and S. Guilley. Correlation-immune boolean functions for easing counter measures to side-channel attacks. In H. E. Niederreiter, O. E. Alina, and e. a. Daniel, Panario (Ed.), editors, Algebraic Curves and Finite Fields. Cryptography and Other Applications., pages 41--70. Berlin, Boston: De Gruyter., 2014.

[10]

C. Carlet and P. Sarkar. Spectral Domain Analysis of Correlation Immune and Resilient Boolean Functions. Finite Fields Appl., 8(1):120--130, Jan. 2002.

Digital Library

[11]

N. Carrasco, J.-M. L. Bars, and A. Viola. Enumerative encoding of correlation-immune boolean functions. Theoretical Computer Science, 487(0):23--36, 2013.

[12]

C. Cid, S. Kiyomoto, and J. Kurihara. The RAKAPOSHI Stream Cipher. In S. Qing, C. Mitchell, and G. Wang, editors, Information and Communications Security, volume 5927 of Lecture Notes in Computer Science, pages 32--46. Springer Berlin Heidelberg, 2009.

Digital Library

[13]

J. A. Clark, J. L. Jacob, S. Stepney, S. Maitra, and W. Millan. Evolving Boolean Functions Satisfying Multiple Criteria. In Progress in Cryptology - INDOCRYPT 2002, pages 246--259, 2002.

[14]

N. Courtois. Fast Algebraic Attacks on Stream Ciphers with Linear Feedback. In D. Boneh, editor, Advances in Cryptology - CRYPTO 2003, volume 2729 of Lecture Notes in Computer Science, pages 176--194. Springer Berlin Heidelberg, 2003.

[15]

N. Courtois and W. Meier. Algebraic Attacks on Stream Ciphers with Linear Feedback. In E. Biham, editor, Advances in Cryptology - EUROCRYPT 2003, volume 2656 of Lecture Notes in Computer Science, pages 345--359. Springer Berlin Heidelberg, 2003.

Digital Library

[16]

A. E. Eiben and J. E. Smith. Introduction to Evolutionary Computing. Springer-Verlag, Berlin Heidelberg New York, USA, 2003.

[17]

B. M. Gammel, R. Gottfert, and O. Kniffler. The Achterbahn Stream Cipher, 2005.

[18]

J. Katz and Y. Lindell. Introduction to Modern Cryptography. Chapman and Hall/CRC, Boca Raton, 2008.

Digital Library

[19]

S. Kavut, S. Maitra, and M. D. Yücel. There exist Boolean functions on n (odd) variables having nonlinearity > 2^n-1 - 2^(n-1)/2 if and only if n > 7, 2006.

[20]

J.-M. Le Bars and A. Viola. Equivalence classes of boolean functions for first-order correlation. In Information Theory, 2007. ISIT 2007. IEEE International Symposium on, pages 181--185, June 2007.

[21]

S. Maitra and P. Sarkar. Highly Nonlinear Resilient Functions Optimizing Siegenthaler's Inequality. In M. Wiener, editor, Advances in Cryptology - CRYPTO'99, volume 1666 of Lecture Notes in Computer Science, pages 198--215. Springer Berlin Heidelberg, 1999.

Digital Library

[22]

S. Mangard, E. Oswald, and T. Popp. Power Analysis Attacks: Revealing the Secrets of Smart Cards (Advances in Information Security). Springer-Verlag New York, Inc., Secaucus, NJ, USA, 2007.

[23]

J. McLaughlin and J. A. Clark. 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, 2013. http://eprint.iacr.org/.

[24]

W. Millan, A. Clark, and E. Dawson. Heuristic design of cryptographically strong balanced Boolean functions. In Advances in Cryptology - EUROCRYPT '98, pages 489--499, 1998.

[25]

S. Picek, D. Jakobovic, and M. Golub. Evolving cryptographically sound boolean functions. In Proceedings of the 15th Annual Conference Companion on Genetic and Evolutionary Computation, GECCO '13 Companion, pages 191--192, New York, NY, USA, 2013. ACM.

Digital Library

[26]

P. Sarkar and S. Maitra. Construction of nonlinear boolean functions with important cryptographic properties. In B. Preneel, editor, EUROCRYPT, volume 1807 of Lecture Notes in Computer Science, pages 485--506. Springer, 2000.

Digital Library

[27]

P. Sarkar and S. Maitra. Nonlinearity bounds and constructions of resilient boolean functions. In M. Bellare, editor, CRYPTO, volume 1880 of Lecture Notes in Computer Science, pages 515--532. Springer, 2000.

Digital Library

[28]

T. Siegenthaler. Correlation-immunity of nonlinear combining functions for cryptographic applications (corresp.). IEEE Trans. Inf. Theor., 30(5):776--780, Sept. 2006.

Digital Library

[29]

Y. Tarannikov. On Resilient Boolean Functions with Maximal Possible Nonlinearity. In Proceedings of INDOCRYPT 2000, Lecture Notes in Computer Science. Springer-Verlag, 2000.

Digital Library

Cited By

Djurasevic MJakobovic DMariot LPicek S(2023)A survey of metaheuristic algorithms for the design of cryptographic Boolean functionsCryptography and Communications10.1007/s12095-023-00662-215:6(1171-1197)Online publication date: 29-Jul-2023
https://doi.org/10.1007/s12095-023-00662-2
Husa JSekanina L(2023)Semantic mutation operator for a fast and efficient design of bent Boolean functionsGenetic Programming and Evolvable Machines10.1007/s10710-023-09476-w25:1Online publication date: 8-Dec-2023
https://doi.org/10.1007/s10710-023-09476-w
Picek SJakobovic DWagner M(2022)Evolutionary computation and machine learning in securityProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3520304.3534087(1572-1601)Online publication date: 9-Jul-2022
https://dl.acm.org/doi/10.1145/3520304.3534087
Show More Cited By

Index Terms

Correlation Immunity of Boolean Functions: An Evolutionary Algorithms Perspective
1. Computing methodologies
  1. Artificial intelligence
    1. Control methods
    2. Search methodologies
2. Theory of computation
  1. Design and analysis of algorithms
    1. Algorithm design techniques
      1. Dynamic programming

Recommendations

Evolving cryptographically sound boolean functions
GECCO '13 Companion: Proceedings of the 15th annual conference companion on Genetic and evolutionary computation

This paper explores the evolution of Boolean functions for a cryptographic usage, with genetic algorithms and genetic programming. We also experiment with a new mutation operator and a new kind of initialization process. Results obtained show that those ...
Designing correlation immune boolean functions with minimal hamming weight using various genetic programming methods
GECCO '19: Proceedings of the Genetic and Evolutionary Computation Conference Companion

In this paper, we search for Boolean functions with properties useful in cryptography for preventing side-channel attacks. We use three genetic programming methods including linear genetic programming, which has not been used to design these functions ...
Look into the Mirror: Evolving Self-dual Bent Boolean Functions
Genetic Programming
Abstract
Bent 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 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '15: Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation

July 2015

1496 pages

ISBN:9781450334723

DOI:10.1145/2739480

Editor:
Sara Silva
Universidade de Lisboa, Portugal
,
General Chair:
Anna I. Esparcia-Alcázar
Universitat Politècnica de València, Spain

Copyright © 2015 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 ACM 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

SIGEVO: ACM Special Interest Group on Genetic and Evolutionary Computation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 11 July 2015

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

The Netherlands Organization for Scientific Research NWO
Technology Foundation STW
ICT COST action

Conference

GECCO '15

Sponsor:

SIGEVO

GECCO '15: Genetic and Evolutionary Computation Conference

July 11 - 15, 2015

Madrid, Spain

Acceptance Rates

GECCO '15 Paper Acceptance Rate 182 of 505 submissions, 36%;

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

17
Total Citations
View Citations
153
Total Downloads

Downloads (Last 12 months)4
Downloads (Last 6 weeks)0

Reflects downloads up to 03 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Djurasevic MJakobovic DMariot LPicek S(2023)A survey of metaheuristic algorithms for the design of cryptographic Boolean functionsCryptography and Communications10.1007/s12095-023-00662-215:6(1171-1197)Online publication date: 29-Jul-2023
https://doi.org/10.1007/s12095-023-00662-2
Husa JSekanina L(2023)Semantic mutation operator for a fast and efficient design of bent Boolean functionsGenetic Programming and Evolvable Machines10.1007/s10710-023-09476-w25:1Online publication date: 8-Dec-2023
https://doi.org/10.1007/s10710-023-09476-w
Picek SJakobovic DWagner M(2022)Evolutionary computation and machine learning in securityProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3520304.3534087(1572-1601)Online publication date: 9-Jul-2022
https://dl.acm.org/doi/10.1145/3520304.3534087
Mariot LJakobovic DBäck THernandez-Castro J(2022)Artificial Intelligence for the Design of Symmetric Cryptographic PrimitivesSecurity and Artificial Intelligence10.1007/978-3-030-98795-4_1(3-24)Online publication date: 8-Apr-2022
https://doi.org/10.1007/978-3-030-98795-4_1
Picek SJakobovic DKrawiec K(2021)Evolutionary computation and machine learning in cryptologyProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3449726.3461420(1089-1118)Online publication date: 7-Jul-2021
https://dl.acm.org/doi/10.1145/3449726.3461420
Picek SJakobovic DCoello Coello C(2020)Evolutionary computation and machine learning in cryptologyProceedings of the 2020 Genetic and Evolutionary Computation Conference Companion10.1145/3377929.3389886(1147-1173)Online publication date: 8-Jul-2020
https://dl.acm.org/doi/10.1145/3377929.3389886
Husa JSekanina L(2020)Evolving Cryptographic Boolean Functions with Minimal Multiplicative Complexity2020 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC48606.2020.9185517(1-8)Online publication date: Jul-2020
https://doi.org/10.1109/CEC48606.2020.9185517
Harmouch YEl Kouch RBen-Azza H(2019)An Improvement of Correlation Analysis for Vectorial Boolean FunctionsProgress in Cryptology – AFRICACRYPT 201910.1007/978-3-030-23696-0_13(250-269)Online publication date: 29-Jun-2019
https://doi.org/10.1007/978-3-030-23696-0_13
Husa J(2019)Comparison of Genetic Programming Methods on Design of Cryptographic Boolean FunctionsGenetic Programming10.1007/978-3-030-16670-0_15(228-244)Online publication date: 27-Mar-2019
https://doi.org/10.1007/978-3-030-16670-0_15
Behera PGangopadhyay S(2018)Analysis of Cost function using Genetic algorithm to construct balanced Boolean functionTENCON 2018 - 2018 IEEE Region 10 Conference10.1109/TENCON.2018.8650309(1445-1450)Online publication date: Oct-2018
https://doi.org/10.1109/TENCON.2018.8650309
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten