Growing Random Strings in CA

M. Andrecut

arxiv: 2211.07626 · v2 · submitted 2022-11-14 · 💻 cs.CR

Growing Random Strings in CA

M. Andrecut This is my paper

Pith reviewed 2026-05-24 10:28 UTC · model grok-4.3

classification 💻 cs.CR

keywords cellular automatapseudo-random stringsdiffusionconfusioncryptographyFourier transformentropy estimationcompression

0 comments

The pith

Cellular automata can produce long pseudo-random strings from short seeds using diffusion and confusion.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper tries to establish that a class of cellular automata can expand short seed strings into long sequences that behave as pseudo-random. It does so by adapting the cryptographic ideas of diffusion and confusion to the local update rules of the automata. Numerical checks via Fourier transform, entropy estimation, and compression are used to support the claim that the outputs lack obvious structure. A sympathetic reader would care because the method offers a deterministic, rule-based route to long random-like strings that might simplify certain cryptographic tasks.

Core claim

We discuss a class of cellular automata able to produce long random strings, starting from short seed strings. The approach uses two principles borrowed from cryptography: diffusion and confusion. We show numerically that the strings are pseudo-random using three approaches based on: Fourier transform, entropy estimation, and compression. An application to cryptography is also included with the corresponding Python code.

What carries the argument

Cellular automata rules that apply diffusion and confusion to short seed strings to generate longer sequences.

If this is right

The outputs pass the Fourier, entropy, and compression checks for pseudo-random behavior.
Short seeds can be deterministically expanded into long strings via the automata rules.
The method supplies a concrete cryptographic application with accompanying Python code.
The strings are positioned as usable in cryptographic contexts on the basis of the numerical evidence.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Hardware circuits built from the same local rules could generate the strings at high speed.
The same expansion technique might be tested on other cellular automaton neighborhoods or lattice dimensions.
Links to other deterministic systems that produce apparent randomness from simple rules could be examined.

Load-bearing premise

The chosen cellular automaton rules and the three numerical tests suffice to establish that the strings behave as pseudo-random for cryptographic purposes.

What would settle it

A demonstration that the generated strings fail an additional standard randomness test or admit a successful cryptanalytic attack not covered by the three tests used.

Figures

Figures reproduced from arXiv: 2211.07626 by M. Andrecut.

**Figure 2.** Figure 2: The the probability distribution of states, for [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗

**Figure 3.** Figure 3: The Fourier analysis for L = T = 215: (top) amplitude coefficients; (middle) amplitude coefficients distribution; (bottom) phase angle distribution. C.append(sum(C) % 256) Q[J,0:J+1] = C return 255-Q def entropy(C): p, lns = Counter(C), float(len(C)) return -sum(count/lns * math.log(count/lns, 256) for count in p.values()) if __name__== "__main__": C = "abcdefghijklmnop" C = runCA(C,32768) 5 [PITH_FULL_IM… view at source ↗

**Figure 4.** Figure 4: The symmetric encryption protocol. Let us denote by X , K, Y the sets of all messages, keys and respectively ciphertexts. We also assume that E(k, x) = y and D(k, y) = x, are the encryption and respectively decryption functions, with x ∈ X , k ∈ K, and respectively y ∈ Y. In order to define a cipher, the E and D functions must satisfy the following correctness property D(k, E(k, x)) = x, ∀x ∈ X , which mea… view at source ↗

read the original abstract

We discuss a class of cellular automata (CA) able to produce long random strings, starting from short "seed" strings. The approach uses two principles borrowed from cryptography: diffusion and confusion. We show numerically that the strings are pseudo-random using three approaches based on: Fourier transform, entropy estimation, and compression. An application to cryptography is also included with the corresponding Python code.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

CA method grows seed strings and passes three basic statistical checks but the evidence does not support a cryptographic pseudo-random claim.

read the letter

This paper sets up cellular automata rules to expand short seed strings into longer ones by applying the crypto notions of diffusion and confusion. It reports numerical results from Fourier transforms, entropy estimation, and compression tests to argue the outputs are pseudo-random, and supplies Python code for a cryptography application. The implementation detail and the direct numerical checks are the parts that stand out. The code makes the experiments easy to rerun, and the three tests give a basic indication that the generated strings lack obvious structure under those measures. The work is coherent and avoids any circular fitting; the claims rest on the reported experiments rather than self-referential definitions. The central limitation is that the randomness evidence remains weak for the intended cryptographic use. Fourier, entropy, and compression tests are a narrow set; they leave out standard checks such as runs, serial correlation, and linear complexity, and the paper offers no formal security reduction. A sequence can pass these three yet still be distinguishable under other analyses. The abstract also gives little detail on the exact rules or seed choices, which limits how far the result can be generalized. The contribution is an application of known CA and crypto ideas rather than a new theoretical result. Readers already working on cellular automata for random generation might find the code and the simple construction useful. Anyone seeking a strong randomness guarantee or a reorganization of the area will not find it here. The paper shows clear engagement with the practical side of the problem. I would not bring this to a general reading group. I would not cite it. It could go to peer review in a specialized CA or applied crypto venue if the full text adds more tests and rule details, but the current central claim needs that support.

Referee Report

2 major / 2 minor

Summary. The manuscript introduces a class of cellular automata that generate long strings from short seeds by applying diffusion and confusion. It claims these strings are pseudo-random on the basis of numerical evidence from Fourier transform, entropy estimation, and compression tests, and presents a cryptographic application together with Python code.

Significance. If the central numerical claim can be placed on firmer ground, the construction would supply a lightweight, rule-based mechanism for expanding short seeds into long strings while inheriting two standard cryptographic design principles. The provision of executable code is a clear strength for reproducibility.

major comments (2)

[§4] §4 (Numerical validation): the central claim that the generated strings are pseudo-random for cryptographic use rests on only the three listed tests. These tests omit standard components of cryptographic randomness batteries (linear-complexity, serial, runs, and approximate-entropy tests) and supply no justification for their sufficiency or controls for false-positive rates; the abstract and main text give no sequence lengths, trial counts, or rule-parameter details.
[§5] §5 (Cryptographic application): the security argument assumes that passing the three tests implies suitability for cryptographic use, yet no formal security reduction or indistinguishability argument is provided; the claim is therefore load-bearing and unsupported by the evidence presented.

minor comments (2)

[§3] The precise definition of the cellular-automaton update rules and the mapping from diffusion/confusion principles to the local function are stated only informally; explicit pseudocode or a small example table would improve clarity.
Figure captions and axis labels in the Fourier and entropy plots do not indicate the number of independent runs or the exact string lengths used, hindering direct comparison with other generators.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive comments. We address each major comment below and indicate the revisions we will make.

read point-by-point responses

Referee: [§4] §4 (Numerical validation): the central claim that the generated strings are pseudo-random for cryptographic use rests on only the three listed tests. These tests omit standard components of cryptographic randomness batteries (linear-complexity, serial, runs, and approximate-entropy tests) and supply no justification for their sufficiency or controls for false-positive rates; the abstract and main text give no sequence lengths, trial counts, or rule-parameter details.

Authors: We agree that explicit values for sequence lengths, trial counts, and rule parameters are required for reproducibility and will add them to §4 and the abstract in the revision. The three tests were selected to directly probe the diffusion (Fourier) and confusion (entropy, compression) properties that the construction inherits from cryptographic design principles. We will insert a short justification for this choice and a limitations paragraph noting that these tests do not constitute a full NIST-style battery. Because the manuscript is primarily a numerical demonstration rather than a comprehensive statistical study, we will not add the full set of omitted tests but will make the existing evidence more transparent. revision: partial
Referee: [§5] §5 (Cryptographic application): the security argument assumes that passing the three tests implies suitability for cryptographic use, yet no formal security reduction or indistinguishability argument is provided; the claim is therefore load-bearing and unsupported by the evidence presented.

Authors: We accept that the manuscript does not contain a formal security reduction or indistinguishability argument. The cryptographic application is offered only as an illustrative example that re-uses the diffusion and confusion mechanisms already validated numerically. We will revise §5 and the abstract to state explicitly that the construction provides a lightweight, rule-based expander whose empirical randomness properties are supported by the reported tests, while making clear that formal cryptographic security remains an open question requiring separate analysis. revision: yes

Circularity Check

0 steps flagged

No circularity: empirical validation via direct numerical tests

full rationale

The paper generates strings via CA evolution under diffusion/confusion rules and validates pseudo-randomness through independent numerical tests (Fourier transform, entropy, compression). No derivation chain exists that reduces predictions or results to inputs by construction, no fitted parameters are relabeled as predictions, and no self-citations or uniqueness theorems are invoked as load-bearing. The results are outputs of explicit simulation, not tautological redefinitions.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract-only review yields no explicit free parameters, axioms, or invented entities; the approach implicitly assumes that diffusion and confusion suffice to produce pseudo-randomness under the chosen update rules.

pith-pipeline@v0.9.0 · 5564 in / 1026 out tokens · 18078 ms · 2026-05-24T10:28:59.162197+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

9 extracted references · 9 canonical work pages

[1]

Wolfram,A New Kind of Science , Wolfram Media (2002)

S. Wolfram,A New Kind of Science , Wolfram Media (2002)

work page 2002
[2]

Wolfram, Random sequence generation by cellular automata , Advances in applied mathematics, 7(2):123-169 (1986)

S. Wolfram, Random sequence generation by cellular automata , Advances in applied mathematics, 7(2):123-169 (1986)

work page 1986
[3]

Serra, T

M. Serra, T. Slater, J. Muzio, D.M.Miller, The Analysis of One-dimensional Linear Cellular Automata and Their Aliasing Properties , IEEE Transactions on Computer- Aided Design of Integrated Circuits and Systems 9(7), 767-778 (1990)

work page 1990
[4]

Golomb, Shift-Register Sequences (revised edition), Aegean Press (1982)

S. Golomb, Shift-Register Sequences (revised edition), Aegean Press (1982)

work page 1982
[5]

Fuster-Sabater, P

A. Fuster-Sabater, P. Caballero-Gil,On the Use of Cellular Automata in Symmetric Cryptography, Acta Appl. Math 93, 215-236 (2006)

work page 2006
[6]

R., Cryptography Theory and Practice , 3rd ed., CRC Press, Boca Raton, 2006

Stinson D. R., Cryptography Theory and Practice , 3rd ed., CRC Press, Boca Raton, 2006

work page 2006
[7]

Katz J., Lindell Y., Introduction to modern cryptography , CRC Press, Boca Raton, 2008

work page 2008
[8]

C.Shannon, Communication Theory of Secrecy Systems, BellSystemTechnicalJournal, 28(4), 656 (1949)

work page 1949
[9]

https://docs.python.org/3/library/bz2.html 9

work page

[1] [1]

Wolfram,A New Kind of Science , Wolfram Media (2002)

S. Wolfram,A New Kind of Science , Wolfram Media (2002)

work page 2002

[2] [2]

Wolfram, Random sequence generation by cellular automata , Advances in applied mathematics, 7(2):123-169 (1986)

S. Wolfram, Random sequence generation by cellular automata , Advances in applied mathematics, 7(2):123-169 (1986)

work page 1986

[3] [3]

Serra, T

M. Serra, T. Slater, J. Muzio, D.M.Miller, The Analysis of One-dimensional Linear Cellular Automata and Their Aliasing Properties , IEEE Transactions on Computer- Aided Design of Integrated Circuits and Systems 9(7), 767-778 (1990)

work page 1990

[4] [4]

Golomb, Shift-Register Sequences (revised edition), Aegean Press (1982)

S. Golomb, Shift-Register Sequences (revised edition), Aegean Press (1982)

work page 1982

[5] [5]

Fuster-Sabater, P

A. Fuster-Sabater, P. Caballero-Gil,On the Use of Cellular Automata in Symmetric Cryptography, Acta Appl. Math 93, 215-236 (2006)

work page 2006

[6] [6]

R., Cryptography Theory and Practice , 3rd ed., CRC Press, Boca Raton, 2006

Stinson D. R., Cryptography Theory and Practice , 3rd ed., CRC Press, Boca Raton, 2006

work page 2006

[7] [7]

Katz J., Lindell Y., Introduction to modern cryptography , CRC Press, Boca Raton, 2008

work page 2008

[8] [8]

C.Shannon, Communication Theory of Secrecy Systems, BellSystemTechnicalJournal, 28(4), 656 (1949)

work page 1949

[9] [9]

https://docs.python.org/3/library/bz2.html 9

work page