Mutually Orthogonal Cellular Automata (MOCA) are sets of bipermutive CA which can be used to construct pairwise orthogonal Latin squares. In this work, we consider the inversion problem of pairs of configurations in MOCA. In particular, we design an algorithm based on coupled de Bruijn graphs which solves this problem for generic MOCA, without assuming any linearity on the underlying bipermutive rules. Next, we analyze the computational complexity of this algorithm, remarking that it runs in exponential time with respect to the diameter of the CA rule, but that it can be straightforwardly parallelized to yield a linear time complexity. As a cryptographic application of this algorithm, we finally show how to design a (2, n) threshold Secret Sharing Scheme (SSS) based on MOCA where any combination of two players can reconstruct the secret by applying our inversion algorithm.

Mariot, L., Leporati, A. (2018). Inversion of Mutually Orthogonal Cellular Automata. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp.364-376). Springer Verlag [10.1007/978-3-319-99813-8_33].

Inversion of Mutually Orthogonal Cellular Automata

Mariot, Luca
;
Leporati, Alberto
2018

Abstract

Mutually Orthogonal Cellular Automata (MOCA) are sets of bipermutive CA which can be used to construct pairwise orthogonal Latin squares. In this work, we consider the inversion problem of pairs of configurations in MOCA. In particular, we design an algorithm based on coupled de Bruijn graphs which solves this problem for generic MOCA, without assuming any linearity on the underlying bipermutive rules. Next, we analyze the computational complexity of this algorithm, remarking that it runs in exponential time with respect to the diameter of the CA rule, but that it can be straightforwardly parallelized to yield a linear time complexity. As a cryptographic application of this algorithm, we finally show how to design a (2, n) threshold Secret Sharing Scheme (SSS) based on MOCA where any combination of two players can reconstruct the secret by applying our inversion algorithm.
No
slide + paper
Cellular automata; de Bruijn graph; Latin squares; Secret sharing schemes; Theoretical Computer Science; Computer Science (all)
English
13th International Conference on Cellular Automata for Research and Industry, ACRI 2018
9783319998121
2018
https://www.springer.com/series/558
Mariot, L., Leporati, A. (2018). Inversion of Mutually Orthogonal Cellular Automata. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp.364-376). Springer Verlag [10.1007/978-3-319-99813-8_33].
Mariot, L; Leporati, A
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/213964
Citazioni
  • Scopus 4
  • ???jsp.display-item.citation.isi??? 5
Social impact