We consider the problem of enumerating pairs of bipermutive cellular automata (CA) which generate orthogonal Latin squares. Since the problem has already been settled for bipermutive CA with linear local rules, we address the general case of nonlinear rules, which could be interesting for cryptographic applications such as the design of cheater-immune secret sharing schemes. We first prove that two bipermutive CA generating orthogonal Latin squares must have pairwise balanced local rules. Then, we count the number of pairwise balanced bipermutive Boolean functions and enumerate those which generate orthogonal Latin squares up to n=6 variables, classifying them with respect to their nonlinearity values.

Mariot, L., Formenti, E., Leporati, A. (2017). Enumerating orthogonal Latin squares generated by bipermutive cellular automata. In Cellular Automata and Discrete Complex Systems. 23rd IFIP WG 1.5 International Workshop, AUTOMATA 2017, Milan, Italy, June 7-9, 2017, Proceedings (pp.151-164). Springer Verlag [10.1007/978-3-319-58631-1_12].

Enumerating orthogonal Latin squares generated by bipermutive cellular automata

MARIOT, LUCA
Primo
;
FORMENTI, ENRICO
Secondo
;
LEPORATI, ALBERTO OTTAVIO
Ultimo
2017

Abstract

We consider the problem of enumerating pairs of bipermutive cellular automata (CA) which generate orthogonal Latin squares. Since the problem has already been settled for bipermutive CA with linear local rules, we address the general case of nonlinear rules, which could be interesting for cryptographic applications such as the design of cheater-immune secret sharing schemes. We first prove that two bipermutive CA generating orthogonal Latin squares must have pairwise balanced local rules. Then, we count the number of pairwise balanced bipermutive Boolean functions and enumerate those which generate orthogonal Latin squares up to n=6 variables, classifying them with respect to their nonlinearity values.
paper
Bipermutivity; Cellular automata; Latin squares; Pairwise balancedness; Theoretical Computer Science; Computer Science (all)
English
23rd IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems, AUTOMATA 2017
2017
Dennunzio, A; Formenti, E; Manzoni, L; Porreca, AE
Cellular Automata and Discrete Complex Systems. 23rd IFIP WG 1.5 International Workshop, AUTOMATA 2017, Milan, Italy, June 7-9, 2017, Proceedings
9783319586304
2017
10248
151
164
http://springerlink.com/content/0302-9743/copyright/2005/
none
Mariot, L., Formenti, E., Leporati, A. (2017). Enumerating orthogonal Latin squares generated by bipermutive cellular automata. In Cellular Automata and Discrete Complex Systems. 23rd IFIP WG 1.5 International Workshop, AUTOMATA 2017, Milan, Italy, June 7-9, 2017, Proceedings (pp.151-164). Springer Verlag [10.1007/978-3-319-58631-1_12].
File in questo prodotto:
Non ci sono file associati a questo prodotto.

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/163725
Citazioni
  • Scopus 6
  • ???jsp.display-item.citation.isi??? 7
Social impact