CRYPTOGRAPHIC HASH-FUNCTIONS BASED ON CELLULAR AUTOMATA AND KECCAK ARCHITECTURE

Abstract

This research presents a comprehensive study of cryptographic hash functions and the development of novel hashing algorithms based on elementary cellular automata (CA). Modern cybersecurity relies on cryptographic hashing to guarantee reliable authentication and data integrity. To achieve high security alongside computational efficiency, authors propose utilizing non-linear cellular automata as binary pseudorandom sequence generators within a SHA-3 sponge framework. The study examines elementary CA rules from the “Rule 30” equivalence class, specifically Rules 30, 86, 135, and 149, alongside the linear additive Rule 150.

The authors formalized an algebraic state space model over the Galois field F2. Linear diffusion properties are mathematically guaranteed by a symmetric tridiagonal circulant operator matrix M150, while non-linear confusion is introduced by Rule 86. Two distinct architectural approaches were developed and analyzed: a Keccak-like sponge analogue featuring a custom CA-driven round function (Approach A) and a lightweight direct rule interaction model (Approach B). The custom round function combines Rule 86, Rule 150, and cyclic 31-bit rotations across a 1600-bit state register.

Rigorous empirical evaluation was performed using the NIST STS v800-22 suite, confirming high randomness with pass rates P >= 0,96 across subtests. Strict Avalanche Criterion (SAC) analysis demonstrated near-ideal bit mixing. Approach A achieved a mean bit flip ratio of 49.87% and a low absolute SAC error of 0,0013. Performance benchmarking was executed in a Java 17 JVM environment. Approach A attained a processing throughput of 134,62 MB/s, outperforming standard Java SHA-3 by 29,4%. Approach B reached 206,10 MB/s, providing an ultra-fast lightweight alternative.

The findings prove that combining non-linear CA rules with linear matrix operators in sponge constructions significantly enhances diffusion speed, collision resistance, and execution performance, establishing CA as a highly promising foundation for modern cryptographic tools.