Cryptographic properties of Boolean functions defining elementary cellular automata

Abstract

In this work, the algebraic properties of the local transition functions of elementary cellular automata (ECA) were analysed. Specifically, a classification of such cellular automata was done according to their algebraic degree, the balancedness, the resiliency, nonlinearity, the propagation criterion and the existence of non-zero linear structures. It is shown that there is not any ECA satisfying all properties at the same time.

Keywords:

• cellular automata
• Boolean functions
• cryptographic properties

2000 AMS Subject Classifications :

• 68Q80
• 94C10
• 94A60

ACM Computing Classification System Codes:

• D.4.6
• F.1.1

Acknowledgements

We wish to thank the referees for their valuable comments. This work has been supported by Ministerio de Ciencia e Innovación (Spain) under grant MTM2008-02773.