doi: 10.3934/amc.2022013
Online First

Online First articles are published articles within a journal that have not yet been assigned to a formal issue. This means they do not yet have a volume number, issue number, or page numbers assigned to them, however, they can still be found and cited using their DOI (Digital Object Identifier). Online First publication benefits the research community by making new scientific discoveries known as quickly as possible.

Readers can access Online First articles via the “Online First” tab for the selected journal.

Parameterization of Boolean functions by vectorial functions and associated constructions

Department of informatics, University of Bergen, Norway and LAGA, University of Paris 8, France

Received  October 2021 Early access March 2022

Fund Project: The research of the author is partly supported by the Trond Mohn Foundation and Norwegian Research Council

Too few general constructions of Boolean functions satisfying all cryptographic criteria are known. We investigate the construction in which the support of $ f $ equals the image set of an injective vectorial function $ F $, that we call a parameterization of $ f $. Every balanced Boolean function can be obtained this way. We study five illustrations of this general construction. The three first correspond to known classes (Maiorana-McFarland, majority functions and balanced functions in odd numbers of variables with optimal algebraic immunity). The two last correspond to new classes:

- the sums of indicators of disjoint graphs of $ (k,n-k $)-functions,

- functions parameterized through $ (n-1,n) $-functions due to Beelen and Leander.

We study the cryptographic parameters of balanced Boolean functions, according to those of their parameterizations: the algebraic degree of $ f $, that we relate to the algebraic degrees of $ F $ and of its graph indicator, the nonlinearity of $ f $, that we relate by a bound to the nonlinearity of $ F $, and the algebraic immunity (AI), whose optimality is related to a natural question in linear algebra, and which may be approached (in two ways) by using the graph indicator of $ F $. We revisit each of the five classes for each criterion. The fourth class is very promising, thanks to a lower bound on the nonlinearity by means of the nonlinearity of the chosen $ (k,n-k $)-functions. The sub-class of the sums of indicators of affine functions, for which we prove an upper bound and a lower bound on the nonlinearity, seems also interesting. The fifth class includes functions with an optimal algebraic degree, good nonlinearity and good AI.

Citation: Claude Carlet. Parameterization of Boolean functions by vectorial functions and associated constructions. Advances in Mathematics of Communications, doi: 10.3934/amc.2022013
References:
[1] E. F. AssmusJr. and J. D. Key, Designs and Their Codes, volume 103 of Cambridge Tracts in Mathematics. Cambridge University Press, Cambridge, UK, 1992.  doi: 10.1017/CBO9781316529836.
[2]

P. Beelen and G. Leander, A new construction of highly nonlinear S-boxes, Cryptogr. Commun., 4 (2012), 65-77.  doi: 10.1007/s12095-011-0052-4.

[3]

A. Canteaut, Open problems related to algebraic attacks on stream ciphers, Coding and Cryptography, 3969 (2006), 120-134.  doi: 10.1007/11779360_10.

[4]

C. Carlet, A larger class of cryptographic Boolean functions via a study of the Maiorana-McFarland construction, Advances in Cryptology—CRYPTO, 2442 (2002), 549-564.  doi: 10.1007/3-540-45708-9_35.

[5]

C. Carlet, Handling vectorial functions by means of their graph indicators, IEEE Trans. Inform. Theory, 66 (2020), 6324-6339.  doi: 10.1109/TIT.2020.2981524.

[6]

C. Carlet, Graph indicators of vectorial functions and bounds on the algebraic degree of composite functions, IEEE Trans. Inform. Theory, 66 (2020), 7702-7716.  doi: 10.1109/TIT.2020.3017494.

[7]

C. Carlet, Boolean Functions for Cryptography and Coding Theory, Monograph in Cambridge University Press 562 pages, 2021. doi: 10.1017/9781108606806.

[8]

C. CarletP. Charpin and V. Zinoviev, Codes, bent functions and permutations suitable for DES-like cryptosystems, Des. Codes Cryptogr., 15 (1998), 125-156.  doi: 10.1023/A:1008344232130.

[9]

C. CarletD. DalaiK. Gupta and S. Maitra, Algebraic immunity for cryptographically significant Boolean functions: Analysis and construction, IEEE Trans. Inform. Theory, 52 (2006), 3105-3121.  doi: 10.1109/TIT.2006.876253.

[10]

C. Carlet and K. Feng, An infinite class of balanced functions with optimum algebraic immunity, good immunity to fast algebraic attacks and good nonlinearity, Advances in cryptology—ASIACRYPT, 5350 (2008), 425-440.  doi: 10.1007/978-3-540-89255-7_26.

[11]

C. Carlet and P. Méaux, Boolean functions for homomorphic-friendly stream ciphers, Algebra, Codes and Cryptology, 1133 (2019), 166-182.  doi: 10.1007/978-3-030-36237-9_10.

[12]

C. Carlet and S. Picek, On the practical limits of a generalization of the hidden weight bit function and of another construction of highly nonlinear functions, Preprint, 2022.

[13]

D. K. DalaiS. Maitra and S. Sarkar, Basic theory in construction of boolean functions with maximum possible annihilator immunity, Des. Codes Cryptogr., 40 (2006), 41-58.  doi: 10.1007/s10623-005-6300-x.

[14]

C. DingC. Li and Y. Xia, Another generalisation of the binary Reed-Muller codes and its applications, Finite Fields Appl., 53 (2018), 144-174.  doi: 10.1016/j.ffa.2018.06.006.

[15]

H. Dobbertin, Construction of bent functions and balanced Boolean functions with high nonlinearity, Fast Software Encryption, 1008 (1995), 61-74.  doi: 10.1007/3-540-60590-8_5.

[16]

I. Dumer and O. Kapralova, Spherically punctured Reed-Muller codes, IEEE Trans. Inform. Theory, 63 (2017), 2773-2780. 

[17]

K. LiS. Mesnager and L. Qu, Further study of 2-to-1 mappings over $\mathbb{F}_2^n$, IEEE Trans. Inform. Theory, 67 (2021), 3486-3496.  doi: 10.1109/TIT.2021.3057094.

[18]

F. J. MacWilliams and N. J. Sloane, The Theory of Error-Correcting Codes, Amsterdam-New York-Oxford, 1977.

[19]

P. MéauxC. CarletA. Journault and F.-X. Standaert, Improved filter permutators for efficient FHE: Better instances and implementations, Proceedings of Indocrypt 2019, Lecture Notes in Computer Science, 11898 (2019), 68-91. 

[20]

P. MéauxA. JournaultF.-X. Standaert and C. Carlet, Towards stream ciphers for efficient FHE with low-noise ciphertexts, Advances in Cryptology—EUROCRYPT, 9665 (2016), 311-343.  doi: 10.1007/978-3-662-49890-3_13.

[21]

S. Mesnager, Linear Codes from Functions, Chapter 20 in "A Concise Encyclopedia 1419 Coding Theory" CRC Press/Taylor and Francis Group (Publisher), London, New York, 2021 (94 pages).

[22]

S. Mesnager and L. Qu, On two-to-one mappings over finite fields, IEEE Trans. Inform. Theory, 65 (2019), 7884-7895.  doi: 10.1109/TIT.2019.2933832.

[23]

G. Mullen and D. Panario, Handbook of Finite Fields, CRC Press Book, 2013. doi: 10.1201/b15006.

[24]

Q. WangC. CarletP. Stănică and C. H. Tan, Cryptographic properties of the hidden weighted bit function, Discrete Appl. Math., 174 (2014), 1-10.  doi: 10.1016/j.dam.2014.01.010.

show all references

References:
[1] E. F. AssmusJr. and J. D. Key, Designs and Their Codes, volume 103 of Cambridge Tracts in Mathematics. Cambridge University Press, Cambridge, UK, 1992.  doi: 10.1017/CBO9781316529836.
[2]

P. Beelen and G. Leander, A new construction of highly nonlinear S-boxes, Cryptogr. Commun., 4 (2012), 65-77.  doi: 10.1007/s12095-011-0052-4.

[3]

A. Canteaut, Open problems related to algebraic attacks on stream ciphers, Coding and Cryptography, 3969 (2006), 120-134.  doi: 10.1007/11779360_10.

[4]

C. Carlet, A larger class of cryptographic Boolean functions via a study of the Maiorana-McFarland construction, Advances in Cryptology—CRYPTO, 2442 (2002), 549-564.  doi: 10.1007/3-540-45708-9_35.

[5]

C. Carlet, Handling vectorial functions by means of their graph indicators, IEEE Trans. Inform. Theory, 66 (2020), 6324-6339.  doi: 10.1109/TIT.2020.2981524.

[6]

C. Carlet, Graph indicators of vectorial functions and bounds on the algebraic degree of composite functions, IEEE Trans. Inform. Theory, 66 (2020), 7702-7716.  doi: 10.1109/TIT.2020.3017494.

[7]

C. Carlet, Boolean Functions for Cryptography and Coding Theory, Monograph in Cambridge University Press 562 pages, 2021. doi: 10.1017/9781108606806.

[8]

C. CarletP. Charpin and V. Zinoviev, Codes, bent functions and permutations suitable for DES-like cryptosystems, Des. Codes Cryptogr., 15 (1998), 125-156.  doi: 10.1023/A:1008344232130.

[9]

C. CarletD. DalaiK. Gupta and S. Maitra, Algebraic immunity for cryptographically significant Boolean functions: Analysis and construction, IEEE Trans. Inform. Theory, 52 (2006), 3105-3121.  doi: 10.1109/TIT.2006.876253.

[10]

C. Carlet and K. Feng, An infinite class of balanced functions with optimum algebraic immunity, good immunity to fast algebraic attacks and good nonlinearity, Advances in cryptology—ASIACRYPT, 5350 (2008), 425-440.  doi: 10.1007/978-3-540-89255-7_26.

[11]

C. Carlet and P. Méaux, Boolean functions for homomorphic-friendly stream ciphers, Algebra, Codes and Cryptology, 1133 (2019), 166-182.  doi: 10.1007/978-3-030-36237-9_10.

[12]

C. Carlet and S. Picek, On the practical limits of a generalization of the hidden weight bit function and of another construction of highly nonlinear functions, Preprint, 2022.

[13]

D. K. DalaiS. Maitra and S. Sarkar, Basic theory in construction of boolean functions with maximum possible annihilator immunity, Des. Codes Cryptogr., 40 (2006), 41-58.  doi: 10.1007/s10623-005-6300-x.

[14]

C. DingC. Li and Y. Xia, Another generalisation of the binary Reed-Muller codes and its applications, Finite Fields Appl., 53 (2018), 144-174.  doi: 10.1016/j.ffa.2018.06.006.

[15]

H. Dobbertin, Construction of bent functions and balanced Boolean functions with high nonlinearity, Fast Software Encryption, 1008 (1995), 61-74.  doi: 10.1007/3-540-60590-8_5.

[16]

I. Dumer and O. Kapralova, Spherically punctured Reed-Muller codes, IEEE Trans. Inform. Theory, 63 (2017), 2773-2780. 

[17]

K. LiS. Mesnager and L. Qu, Further study of 2-to-1 mappings over $\mathbb{F}_2^n$, IEEE Trans. Inform. Theory, 67 (2021), 3486-3496.  doi: 10.1109/TIT.2021.3057094.

[18]

F. J. MacWilliams and N. J. Sloane, The Theory of Error-Correcting Codes, Amsterdam-New York-Oxford, 1977.

[19]

P. MéauxC. CarletA. Journault and F.-X. Standaert, Improved filter permutators for efficient FHE: Better instances and implementations, Proceedings of Indocrypt 2019, Lecture Notes in Computer Science, 11898 (2019), 68-91. 

[20]

P. MéauxA. JournaultF.-X. Standaert and C. Carlet, Towards stream ciphers for efficient FHE with low-noise ciphertexts, Advances in Cryptology—EUROCRYPT, 9665 (2016), 311-343.  doi: 10.1007/978-3-662-49890-3_13.

[21]

S. Mesnager, Linear Codes from Functions, Chapter 20 in "A Concise Encyclopedia 1419 Coding Theory" CRC Press/Taylor and Francis Group (Publisher), London, New York, 2021 (94 pages).

[22]

S. Mesnager and L. Qu, On two-to-one mappings over finite fields, IEEE Trans. Inform. Theory, 65 (2019), 7884-7895.  doi: 10.1109/TIT.2019.2933832.

[23]

G. Mullen and D. Panario, Handbook of Finite Fields, CRC Press Book, 2013. doi: 10.1201/b15006.

[24]

Q. WangC. CarletP. Stănică and C. H. Tan, Cryptographic properties of the hidden weighted bit function, Discrete Appl. Math., 174 (2014), 1-10.  doi: 10.1016/j.dam.2014.01.010.

[1]

Sihem Mesnager, Gérard Cohen. Fast algebraic immunity of Boolean functions. Advances in Mathematics of Communications, 2017, 11 (2) : 373-377. doi: 10.3934/amc.2017031

[2]

Claude Carlet, Brahim Merabet. Asymptotic lower bound on the algebraic immunity of random balanced multi-output Boolean functions. Advances in Mathematics of Communications, 2013, 7 (2) : 197-217. doi: 10.3934/amc.2013.7.197

[3]

Jian Liu, Sihem Mesnager, Lusheng Chen. Variation on correlation immune Boolean and vectorial functions. Advances in Mathematics of Communications, 2016, 10 (4) : 895-919. doi: 10.3934/amc.2016048

[4]

SelÇuk Kavut, Seher Tutdere. Highly nonlinear (vectorial) Boolean functions that are symmetric under some permutations. Advances in Mathematics of Communications, 2020, 14 (1) : 127-136. doi: 10.3934/amc.2020010

[5]

Deng Tang. A note on the fast algebraic immunity and its consequences on modified majority functions. Advances in Mathematics of Communications, 2020, 14 (1) : 111-125. doi: 10.3934/amc.2020009

[6]

Yuri Latushkin, Alim Sukhtayev. The Evans function and the Weyl-Titchmarsh function. Discrete and Continuous Dynamical Systems - S, 2012, 5 (5) : 939-970. doi: 10.3934/dcdss.2012.5.939

[7]

J. William Hoffman. Remarks on the zeta function of a graph. Conference Publications, 2003, 2003 (Special) : 413-422. doi: 10.3934/proc.2003.2003.413

[8]

H. N. Mhaskar, T. Poggio. Function approximation by deep networks. Communications on Pure and Applied Analysis, 2020, 19 (8) : 4085-4095. doi: 10.3934/cpaa.2020181

[9]

Hassan Emamirad, Philippe Rogeon. Semiclassical limit of Husimi function. Discrete and Continuous Dynamical Systems - S, 2013, 6 (3) : 669-676. doi: 10.3934/dcdss.2013.6.669

[10]

Ken Ono. Parity of the partition function. Electronic Research Announcements, 1995, 1: 35-42.

[11]

Tomasz Downarowicz, Yonatan Gutman, Dawid Huczek. Rank as a function of measure. Discrete and Continuous Dynamical Systems, 2014, 34 (7) : 2741-2750. doi: 10.3934/dcds.2014.34.2741

[12]

Yvjing Yang, Yang Liu, Jungang Lou, Zhen Wang. Observability of switched Boolean control networks using algebraic forms. Discrete and Continuous Dynamical Systems - S, 2021, 14 (4) : 1519-1533. doi: 10.3934/dcdss.2020373

[13]

Qian Liu. The lower bounds on the second-order nonlinearity of three classes of Boolean functions. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2020136

[14]

Giovanni Colombo, Khai T. Nguyen. On the minimum time function around the origin. Mathematical Control and Related Fields, 2013, 3 (1) : 51-82. doi: 10.3934/mcrf.2013.3.51

[15]

Welington Cordeiro, Manfred Denker, Michiko Yuri. A note on specification for iterated function systems. Discrete and Continuous Dynamical Systems - B, 2015, 20 (10) : 3475-3485. doi: 10.3934/dcdsb.2015.20.3475

[16]

Luc Robbiano. Counting function for interior transmission eigenvalues. Mathematical Control and Related Fields, 2016, 6 (1) : 167-183. doi: 10.3934/mcrf.2016.6.167

[17]

Todd Kapitula, Björn Sandstede. Eigenvalues and resonances using the Evans function. Discrete and Continuous Dynamical Systems, 2004, 10 (4) : 857-869. doi: 10.3934/dcds.2004.10.857

[18]

Martin D. Buhmann, Slawomir Dinew. Limits of radial basis function interpolants. Communications on Pure and Applied Analysis, 2007, 6 (3) : 569-585. doi: 10.3934/cpaa.2007.6.569

[19]

Yulin Zhao. On the monotonicity of the period function of a quadratic system. Discrete and Continuous Dynamical Systems, 2005, 13 (3) : 795-810. doi: 10.3934/dcds.2005.13.795

[20]

Christian Wolf. A shift map with a discontinuous entropy function. Discrete and Continuous Dynamical Systems, 2020, 40 (1) : 319-329. doi: 10.3934/dcds.2020012

2021 Impact Factor: 1.015

Article outline

Figures and Tables

[Back to Top]