Heuristic search of (semi-)bent functions based on cellular automata. (English) Zbl 1530.68180
Summary: An interesting thread in the research of Boolean functions for cryptography and coding theory is the study of secondary constructions: given a known function with a good cryptographic profile, the aim is to extend it to a (usually larger) function possessing analogous properties. In this work, we continue the investigation of a secondary construction based on cellular automata (CA), focusing on the classes of bent and semi-bent functions. We prove that our construction preserves the algebraic degree of the local rule, and we narrow our attention to the subclass of quadratic functions, performing several experiments based on exhaustive combinatorial search and heuristic optimization through Evolutionary Strategies (ES). Finally, we classify the obtained results up to permutation equivalence, remarking that the number of equivalence classes that our CA-XOR construction can successfully extend grows very quickly with respect to the CA diameter.
Keywords:
cellular automata; symmetric cryptography; bent functions; nonlinearity; combinatorial search; evolutionary strategiesReferences:
| [1] | Bassham, LE III; Rukhin, AL; Soto, J.; Nechvatal, JR; Smid, ME; Barker, EB; Leigh, SD; Levenson, M.; Vangel, M.; Banks, DL, SP 800-22 Rev. 1a: a statistical test suite for random and pseudorandom number generators for cryptographic applications (2010), Gaithersburg: NIST, Gaithersburg · doi:10.6028/NIST.SP.800-22r1a |
| [2] | Bertoni G, Daemen J, Peeters M, Assche GV (2011) The Keccak reference, January 2011. http://keccak.noekeon.org/ · Zbl 1306.94028 |
| [3] | Bhattacharjee, K.; Das, S., Random number generation using decimal cellular automata, Commun Nonlinear Sci Numer Simul, 78, 104878 (2019) · Zbl 1472.68103 · doi:10.1016/j.cnsns.2019.104878 |
| [4] | Bhattacharjee, K.; Paul, D.; Das, S., Pseudo-random number generation using a 3-state cellular automaton, Int J Mod Phys C, 28, 6, 1750078 (2017) · doi:10.1142/S0129183117500784 |
| [5] | Carlet, C., Boolean functions for cryptography and coding theory (2021), Cambridge: Cambridge University Press, Cambridge · Zbl 1512.94001 |
| [6] | Castro JCH, Isasi P, and del Arco-Calderón CL (2003). Finding efficient nonlinear functions by means of genetic programming. In: Palade V, Howlett RJ, Jain LC (eds) Proceedings of KES 2003, Part I, LNCS, vol 2773. Springer, pp 1192-1198 |
| [7] | Daemen, J.; Rijmen, V., The design of Rijndael—the advanced encryption standard (AES) (2020), Berlin: Springer, Berlin · Zbl 1437.94001 · doi:10.1007/978-3-662-60769-5 |
| [8] | Daemen, J.; Govaerts, R.; Vandewalle, J., Invertible shift-invariant transformations on binary arrays, Appl Math Comput, 62, 2-3, 259-277 (1994) · Zbl 0809.68088 |
| [9] | Dillon JF (1974) Elementary Hadamard difference sets. PhD Thesis · Zbl 0346.05003 |
| [10] | Formenti, E.; Imai, K.; Martin, B.; Yunès, JB; Calude, CS; Freivalds, R.; Kazuo, I., Advances on random sequence generation by uniform cellular automata, Computing with new resources, 56-70 (2014), Cham: Springer, Cham · Zbl 1323.68392 · doi:10.1007/978-3-319-13350-8_5 |
| [11] | Gadouleau M, Mariot L, Picek S (2020) Bent functions from cellular automata. IACR cryptology ePrint archive, p 1272 |
| [12] | Hazari, R.; Kundu, S.; Bhardwaj, M.; Das, S., ECA 184 can implement any logic circuits, J Cell Autom, 13, 4, 359-371 (2018) · Zbl 1467.68110 |
| [13] | Hrbacek R, Dvorak V (2014) Bent function synthesis by means of Cartesian genetic programming. In: Proceedings of PPSN 2014, LNCS, pp 414-423 |
| [14] | John A, Nandu BC, Ajesh A, Jose J (2020) PENTAVIUM: potent trivium-like stream cipher using higher radii cellular automata. In: Gwizdalla TM, Manzoni L, Sirakoulis GC, Bandini S, Podlaski K (eds) Cellular automata—14th international conference on cellular automata for research and industry, ACRI 2020, Proceedings, Lodz, Poland, 2-4 December 2020, LNCS, vol 12599. Springer, pp 90-100 |
| [15] | Koc, CK; Apohan, A., Inversion of cellular automata iterations, IEE Proc Comput Digit Tech, 144, 5, 279-284 (1997) · doi:10.1049/ip-cdt:19971518 |
| [16] | Kurka P (2003) Topological and symbolic dynamics. Société mathématique de France · Zbl 1038.37011 |
| [17] | Lakra R, John A, Jose J (2018) Carpenter: a cellular automata based resilient pentavalent stream cipher. In: Mauri G, Yacoubi SF, Dennunzio A, Nishinari K, Manzoni L (eds) Cellular automata—13th international conference on cellular automata for research and industry, ACRI 2018, proceedings, Como, Italy, 17-21 September 2018, LNCS, vol 11115. Springer, pp 352-363 · Zbl 1515.94080 |
| [18] | Leporati, A.; Mariot, L., Cryptographic properties of bipermutive cellular automata rules, J Cell Autom, 9, 5-6, 437-475 (2014) · Zbl 1338.94078 |
| [19] | Luke, S., Essentials of metaheuristics (2015), Raleigh: Lulu, Raleigh |
| [20] | Manzoni L, Mariot L (2018) Cellular automata pseudo-random number generators and their resistance to asynchrony. In: Mauri G, Yacoubi SE, Dennunzio A, Nishinari K, Manzoni L (eds) ACRI 2018, LNCS, vol 11115. Springer, pp 428-437 · Zbl 1515.68195 |
| [21] | Manzoni, L.; Mariot, L.; Tuba, E., Balanced crossover operators in genetic algorithms, Swarm Evol Comput, 54, 100646 (2020) · doi:10.1016/j.swevo.2020.100646 |
| [22] | Mariot L (2021) Hip to be (Latin) square: maximal period sequences from orthogonal cellular automata. CoRR, abs/2106.07750 |
| [23] | Mariot L, Leporati A (2015a) A genetic algorithm for evolving plateaued cryptographic Boolean functions. In: Dediu A, Magdalena L, Martín-Vide C (eds) Proceedings of TPNC 2015, LNCS, vol 9477. Springer, pp 33-45 |
| [24] | Mariot L, Leporati A (2015b) Heuristic search by particle swarm optimization of Boolean functions for cryptographic applications. In: Silva S, Esparcia-Alcázar AI (eds) Companion proceedings of GECCO 2015. ACM, pp 1425-1426 |
| [25] | Mariot L, Leporati A (2018) Inversion of mutually orthogonal cellular automata. In: Mauri G, Yacoubi SE, Dennunzio A, Nishinari K, Manzoni L (eds) Cellular automata—13th international conference on cellular automata for research and industry, ACRI 2018, proceedings, Como, Italy, 17-21 September 2018, LNCS, vol 11115. Springer, pp 364-376 · Zbl 1515.68196 |
| [26] | Mariot, L.; Picek, S.; Leporati, A.; Jakobovic, D., Cellular automata based S-boxes, Cryptogr Commun, 11, 1, 41-62 (2019) · Zbl 1420.94087 · doi:10.1007/s12095-018-0311-8 |
| [27] | Mariot, L.; Gadouleau, M.; Formenti, E.; Leporati, A., Mutually orthogonal Latin squares based on cellular automata, Des Codes Cryptogr, 88, 2, 391-411 (2020) · Zbl 1447.05040 · doi:10.1007/s10623-019-00689-8 |
| [28] | Mariot L, Saletta M, Leporati A, Manzoni L (2020b) Exploring semi-bent Boolean functions arising from cellular automata. In: Gwizdalla TM, Manzoni L, Sirakoulis GC, Bandini S, Podlaski K (eds) Cellular automata—14th international conference on cellular automata for research and industry, ACRI 2020, proceedings, Lodz, Poland, 2-4 December 2020, LNCS, vol 12599. Springer, pp 56-66 · Zbl 1492.68092 |
| [29] | Marsaglia G (1996) Diehard: a battery of tests of randomness. http://www.stat.fsu.edu/-geo/diehard.html |
| [30] | Martin, B., A Walsh exploration of elementary CA rules, J Cell Autom, 3, 2, 145-156 (2008) · Zbl 1146.68393 |
| [31] | McFarland, RL, A family of difference sets in non-cyclic groups, J Comb Theory A, 15, 1, 1-10 (1973) · Zbl 0268.05011 · doi:10.1016/0097-3165(73)90031-9 |
| [32] | Meier W, Staffelbach O (1991) Analysis of pseudo random sequence generated by cellular automata. In: Davies DW (ed) Advances in cryptology—EUROCRYPT ’91, workshop on the theory and application of cryptographic techniques, proceedings, Brighton, UK, 8-11 April 1991, LNCS, vol 547. Springer, pp 186-199 · Zbl 0791.68121 |
| [33] | Millan W, Clark AJ, Dawson E (1998) Heuristic design of cryptographically strong balanced Boolean functions. In: Nyberg K (ed) Advances in cryptology—EUROCRYPT ’98, international conference on the theory and application of cryptographic techniques, proceedings, Espoo, Finland, 31 May-4 June 1998, LNCS, vol 1403. Springer, pp 489-499 · Zbl 0919.94017 |
| [34] | Picek, S.; Guilley, S.; Carlet, C.; Jakobovic, D.; Miller, JF, Evolutionary approach for finding correlation immune Boolean functions of order t with minimal Hamming weight, Proc TPNC, 2015, 71-82 (2015) |
| [35] | Rothaus, OS, On “bent” functions, J Comb Theory A, 20, 3, 300-305 (1976) · Zbl 0336.12012 · doi:10.1016/0097-3165(76)90024-8 |
| [36] | Saber, Z.; Uddin, MF; Youssef, AM, On the existence of (9, 3, 5, 240) resilient functions, IEEE Trans Inf Theory, 52, 5, 2269-2270 (2006) · Zbl 1318.94078 · doi:10.1109/TIT.2006.872862 |
| [37] | Seredynski, F.; Bouvry, P.; Zomaya, AY, Cellular automata computations and secret key cryptography, Parallel Comput, 30, 5-6, 753-766 (2004) · doi:10.1016/j.parco.2003.12.014 |
| [38] | Shannon, CE, Communication theory of secrecy systems, Bell Syst Tech J, 28, 4, 656-715 (1949) · Zbl 1200.94005 · doi:10.1002/j.1538-7305.1949.tb00928.x |
| [39] | Sipper M, Tomassini M (1996) Co-evolving parallel random number generators. In: Voigt H, Ebeling W, Rechenberg I, Schwefel H (eds) Parallel problem solving from nature—PPSN IV, international conference on evolutionary computation. The 4th international conference on parallel problem solving from nature, proceedings, Berlin, Germany, 22-26 September 1996, LNCS, vol 1141. Springer, pp 950-959 |
| [40] | Stinson, DR; Paterson, M., Cryptography: theory and practice (2018), Boca Raton: CRC Press, Boca Raton · Zbl 1480.94003 · doi:10.1201/9781315282497 |
| [41] | Tokareva, N., Bent functions: results and applications to cryptography (2015), New York: Academic, New York · Zbl 1372.94002 · doi:10.1016/B978-0-12-802318-1.00002-9 |
| [42] | Tomassini, M.; Perrenoud, M., Cryptography with cellular automata, Appl Soft Comput, 1, 2, 151-160 (2001) · doi:10.1016/S1568-4946(01)00015-1 |
| [43] | Ulam S (1952) Random processes and transformations. In: Proceedings of the international congress on mathematics, vol 2, pp 264-275 · Zbl 0049.09511 |
| [44] | Von Neumann, J.; Burks, AW, Theory of self-reproducing automata (1966), Champaign: University of Illinois Press, Champaign |
| [45] | Wolfram, S., Statistical mechanics of cellular automata, Rev Mod Phys, 55, 3, 601 (1983) · Zbl 1174.82319 · doi:10.1103/RevModPhys.55.601 |
| [46] | Wolfram S (1986) Cryptography with cellular automata. In: Williams HC (ed) CRYPTO ’85, LNCS, vol 218, pp 429-432 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
