Cellular Automata (CA) represent an interesting approach to design Substitution Boxes (S-boxes) having good cryptographic properties and low implementation costs. From the cryptographic perspective, up to now there have been only ad-hoc studies about specific kinds of CA, the best known example being the χ nonlinear transformation used in Keccak. In this paper, we undertake a systematic investigation of the cryptographic properties of S-boxes defined by CA, proving some upper bounds on their nonlinearity and differential uniformity. Next, we extend some previous published results about the construction of CA-based S-boxes by means of a heuristic technique, namely Genetic Programming (GP). In particular, we propose a “reverse engineering” method based on De Bruijn graphs to determine whether a specific S-box is expressible through a single CA rule. Then, we use GP to assess if some CA-based S-box with optimal cryptographic properties can be described by a smaller CA. The results show that GP is able to find much smaller CA rules defining the same reference S-boxes up to the size 7 × 7 , suggesting that our method could be used to find more efficient representations of CA-based S-boxes for hardware implementations. Finally, we classify up to affine equivalence all 3 × 3 and 4 × 4 CA-based S-boxes.

Mariot, L., Picek, S., Leporati, A., Jakobovic, D. (2019). Cellular automata based S-boxes. CRYPTOGRAPHY AND COMMUNICATIONS, 11(1), 41-62 [10.1007/s12095-018-0311-8].

Cellular automata based S-boxes

Mariot, L
Membro del Collaboration Group
;
Leporati, A
Membro del Collaboration Group
;
2019

Abstract

Cellular Automata (CA) represent an interesting approach to design Substitution Boxes (S-boxes) having good cryptographic properties and low implementation costs. From the cryptographic perspective, up to now there have been only ad-hoc studies about specific kinds of CA, the best known example being the χ nonlinear transformation used in Keccak. In this paper, we undertake a systematic investigation of the cryptographic properties of S-boxes defined by CA, proving some upper bounds on their nonlinearity and differential uniformity. Next, we extend some previous published results about the construction of CA-based S-boxes by means of a heuristic technique, namely Genetic Programming (GP). In particular, we propose a “reverse engineering” method based on De Bruijn graphs to determine whether a specific S-box is expressible through a single CA rule. Then, we use GP to assess if some CA-based S-box with optimal cryptographic properties can be described by a smaller CA. The results show that GP is able to find much smaller CA rules defining the same reference S-boxes up to the size 7 × 7 , suggesting that our method could be used to find more efficient representations of CA-based S-boxes for hardware implementations. Finally, we classify up to affine equivalence all 3 × 3 and 4 × 4 CA-based S-boxes.
Articolo in rivista - Articolo scientifico
Cellular automata; Cryptographic properties; Heuristics; S-box;
Cellular Automata, S-box, Cryptographic properties, Heuristics
English
2019
11
1
41
62
reserved
Mariot, L., Picek, S., Leporati, A., Jakobovic, D. (2019). Cellular automata based S-boxes. CRYPTOGRAPHY AND COMMUNICATIONS, 11(1), 41-62 [10.1007/s12095-018-0311-8].
File in questo prodotto:
File Dimensione Formato  
Cellular automata based S-boxes (CC 2019).pdf

Solo gestori archivio

Tipologia di allegato: Publisher’s Version (Version of Record, VoR)
Dimensione 803.86 kB
Formato Adobe PDF
803.86 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10281/197902
Citazioni
  • Scopus 53
  • ???jsp.display-item.citation.isi??? 31
Social impact