Paper Info
Title
A cryptographic and coding-theoretic perspective on the global rules of cellular automata.
Abstract
Cellular Automata (CA) have widely been studied to design cryptographic primitives such as stream ciphers and pseudorandom number generators, focusing in particular on the properties of the underlying local rules. On the other hand, there have been comparatively fewer works concerning the applications of CA to the design of S-boxes and block ciphers, a task that calls for a study of CA global rules in terms of vectorial boolean functions. The aim of this paper is to analyze some of the most basic cryptographic criteria of the global rules of CA. We start by observing that the algebraic degree of a CA global rule equals the degree of its local rule. Then, we characterize the Walsh spectrum of CA induced by permutive local rules, from which we derive a formula for the nonlinearity of such CA. Additionally, we prove that the 1-resiliency property of bipermutive local rules transfers to the corresponding global rules. This result leads us to consider CA global rules from a coding-theoretic point of view: in particular, we show that linear CA are equivalent to linear cyclic codes, observing that the syndrome computation process corresponds to the application of the CA global rule, while the error-correction capability of the code is related to the resiliency order of the global rule.
Year
DOI
Venue
2018
10.1007/s11047-017-9635-0
Natural Computing
Keywords
Field
DocType
Cellular automata,Boolean functions,S-boxes,Nonlinearity,Resiliency,Cyclic codes,37B15,68Q80,94B15,94A55
Boolean function,Cellular automaton,Algebraic number,Cryptography,Computer science,Theoretical computer science,Artificial intelligence,Pseudorandom number generator,Discrete mathematics,Block cipher,Algorithm,Cryptographic primitive,Stream cipher,Machine learning
Journal
Volume
Issue
ISSN
17
3
1567-7818
Citations 
PageRank 
References 
0
0.34
6
Authors
2
Name
Order
Citations
PageRank
Luca Mariot14711.35
Alberto Leporati249451.97