New classes of reversible cellular automata
math.CO, cs.CR, cs.DM, cs.IT, math.DS, math.IT
Submitted: 2024-11-01
Updated: 2026-11-01
Comments: 15 pages; now proves completeness of the diameter-six classification; also adds nonlinearity results, and updates discussion and references
DOI: 10.1007/s10623-026-01869-z
License: http://creativecommons.org/licenses/by/4.0/
The gist: Cellular automata find applications in cryptography, error correction, theoretical computer science, and the simulation of physical and biological processes.
Terminology
Abstract
Cellular automata find applications in cryptography, error correction, theoretical computer science, and the simulation of physical and biological processes. We say that a Boolean function is a proper lifting if its induced cellular automaton is reversible. This paper introduces new classes of proper liftings, constructed through compositions of landscape functions, and explores their cryptographic potential by computing indicators relevant to differential and linear cryptanalysis. We combine theoretical and computational methods to obtain a complete classification of proper liftings for diameters up to 6. Several open problems and conjectures are posed along the way.
Related papers
- Three-ends Furstenberg estimates and approximate rectangles
- Multicolor Ramsey numbers of ordered matchings
- Exponential random graph models with soft clique constraints
- A Full-Sequence Quantitative Gap Between the Chromatic and Cochromatic Numbers of a Random Graph
- Ehrhart positivity for paving positroids
- Nonlinear lower-tail large deviations at criticality