pith. machine review for the scientific record. sign in

arxiv: 2604.11362 · v1 · submitted 2026-04-13 · 💻 cs.CR · math.CO

Recognition: unknown

How to reconstruct (anonymously) a secret cellular automaton

Luca Mariot , Federico Mazzone , Luca Manzoni , Alberto Leporati
Authors on Pith no claims yet

Pith reviewed 2026-05-10 15:48 UTC · model grok-4.3

classification 💻 cs.CR math.CO
keywords cellular automatasecret sharingthreshold schemesmutually orthogonal Latin squaresanonymous reconstructioncryptography
0
0 comments X

The pith

Redefining the secret space as the MOLS family enables (2,n) cellular automaton threshold schemes to reconstruct secret rules anonymously.

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

The paper reexamines threshold secret sharing schemes based on cellular automata that support anonymous reconstruction, where the secret is recovered solely from the shares without participant identities. It starts from the known characterization of (2,n) schemes in terms of mutually orthogonal Latin squares. By redefining the secret space itself to be the MOLS family, the scheme can now anonymously recover secret cellular automaton rules. The authors also examine the resulting trade-off between the number of sharable secret rules and the computational cost of recovery.

Core claim

Redefining the secret space as the family of mutually orthogonal Latin squares in existing (2,n) threshold schemes based on cellular automata enables the anonymous reconstruction of the secret CA rules while preserving the threshold property.

What carries the argument

The MOLS family, repurposed as the secret space within the cellular automaton threshold scheme to carry both the threshold access structure and the anonymity guarantee.

If this is right

  • The scheme supports sharing and recovering multiple secret CA rules from the same set of shares.
  • Reconstruction stays fully anonymous because it operates only on the collected shares.
  • Larger MOLS families increase the number of possible secret rules but raise recovery-phase complexity.
  • The original (2,n) threshold property remains intact under the redefinition.

Where Pith is reading between the lines

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

  • Small-n implementations could be run to measure the exact computational scaling of recovery in practice.
  • The same redefinition tactic might be tried on other combinatorial objects used in secret sharing to add anonymity.
  • The resulting schemes could suit protocols that require hidden participant identities during secret recovery.

Load-bearing premise

The existing MOLS characterization of (2,n) CA threshold schemes can be directly repurposed by setting the secret space to the MOLS family while preserving both the threshold property and the anonymity guarantee without additional constraints.

What would settle it

A concrete counterexample where setting the secret to the MOLS family either breaks the (2,n) threshold (requiring a different number of shares) or forces the recovery step to use participant identities.

Figures

Figures reproduced from arXiv: 2604.11362 by Alberto Leporati, Federico Mazzone, Luca Manzoni, Luca Mariot.

Figure 1
Figure 1. Figure 1: Example of orthogonal labelings for the de Bruijn graph [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Latin squares generated by rules 90 and 150, and related parallel classes. [PITH_FULL_IMAGE:figures/full_fig_p011_2.png] view at source ↗
read the original abstract

We consider threshold secret sharing schemes based on cellular automata (CA) that allows for anonymous reconstruction, meaning that the secret can be recovered only as a function of the shares, without knowing the participants' identities. To this end, we revisit the basic characterization of $(2,n)$ threshold schemes based on CA in terms of Mutually Orthogonal Latin Squares (MOLS), and redefine the secret space as the MOLS family itself, showing that the new resulting scheme enables anonymous reconstruction of secret CA rules. Finally, we discuss the trade-off between the number of secret CA that can be shared and the computational complexity of the recovery phase.

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.

Referee Report

2 major / 2 minor

Summary. The paper revisits the MOLS-based characterization of (2,n) threshold secret sharing schemes for cellular automata (CA). It redefines the secret space to consist of the MOLS family itself rather than a fixed CA rule, and claims that the resulting scheme permits anonymous reconstruction of the secret CA rule (i.e., recovery depends only on the collection of shares and not on participant identities). The manuscript concludes with a discussion of the trade-off between the number of shareable secret CA rules and the computational cost of the recovery phase.

Significance. If the construction and its security properties are rigorously established, the work would supply a concrete mechanism for anonymous reconstruction within the existing MOLS framework for CA threshold schemes. This could be relevant to privacy-preserving distributed protocols that employ cellular automata, and the trade-off analysis might inform parameter selection in such systems.

major comments (2)
  1. [Construction and proof of the new scheme] The central claim—that redefining the secret space as the MOLS family automatically yields a (2,n) threshold scheme with anonymous reconstruction—requires an explicit new sharing map and reconstruction algorithm together with a proof that any two shares recover the chosen MOLS (hence the CA rule) while a single share reveals nothing. The original MOLS characterization applies to a fixed secret CA rule; the manuscript must demonstrate that the threshold and anonymity invariants survive the redefinition without extra constraints on the MOLS family or neighborhood size.
  2. [Anonymity argument] Anonymity is defined as reconstruction operating solely on the unordered collection of share values with no dependence on participant labels. The paper must verify that the reconstruction procedure satisfies this property for the new secret space; the abstract and trade-off discussion do not substitute for this verification.
minor comments (2)
  1. [Abstract] The abstract states that the new scheme 'enables anonymous reconstruction' but supplies no illustrative example or high-level outline of the sharing/reconstruction maps; adding one would improve readability.
  2. [Trade-off section] The trade-off discussion between the number of secret CA rules and recovery complexity would benefit from concrete bounds or a small numerical example relating MOLS order to reconstruction time.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive and detailed comments. We agree that the manuscript requires more explicit treatment of the sharing map, reconstruction algorithm, and formal proofs to fully establish the claims. We address each major comment below and will revise the paper accordingly.

read point-by-point responses

  1. Referee: [Construction and proof of the new scheme] The central claim—that redefining the secret space as the MOLS family automatically yields a (2,n) threshold scheme with anonymous reconstruction—requires an explicit new sharing map and reconstruction algorithm together with a proof that any two shares recover the chosen MOLS (hence the CA rule) while a single share reveals nothing. The original MOLS characterization applies to a fixed secret CA rule; the manuscript must demonstrate that the threshold and anonymity invariants survive the redefinition without extra constraints on the MOLS family or neighborhood size.

    Authors: We agree that an explicit sharing map, reconstruction algorithm, and supporting proofs are necessary for rigor. In the revised manuscript we will define a concrete sharing map in which the secret is a family of MOLS and each participant is assigned a share consisting of a symbol-position pair drawn from the squares such that any two shares determine a unique completing MOLS via the orthogonality condition. The reconstruction algorithm will be stated as a procedure that, given any two shares, solves for the unique orthogonal mate(s) and thereby recovers the entire family (hence the CA rule). We will prove the (2,n) threshold property by showing that a single share is consistent with multiple possible MOLS families while two shares fix the family uniquely, and that these properties follow directly from the standard definition of MOLS without additional constraints on the family or on neighborhood size. The neighborhood size enters only in the subsequent CA evolution step and does not affect the combinatorial recovery of the MOLS itself. revision: yes

  2. Referee: [Anonymity argument] Anonymity is defined as reconstruction operating solely on the unordered collection of share values with no dependence on participant labels. The paper must verify that the reconstruction procedure satisfies this property for the new secret space; the abstract and trade-off discussion do not substitute for this verification.

    Authors: We will add an explicit verification of anonymity in the revised version. The reconstruction algorithm will be formulated to accept only the unordered multiset of share values (with no participant identifiers or ordering). Because recovery proceeds by solving the system of orthogonality equations on the received symbols alone, the output MOLS family is independent of any labeling of the participants. We will include a short lemma proving that if two different labelings produce the same multiset of shares, the recovered secret is identical, thereby confirming that anonymity holds for the redefined secret space. revision: yes

Circularity Check

0 steps flagged

Redefinition of secret space as MOLS family builds on revisited characterization without circular reduction

full rationale

The paper revisits the existing MOLS-based characterization of (2,n) CA threshold schemes and redefines the secret space as the MOLS family itself to enable anonymous reconstruction of secret CA rules. This is presented as a constructive extension rather than a derivation that reduces to its inputs by construction. No self-definitional steps, fitted parameters renamed as predictions, or load-bearing self-citations that render the central claim equivalent to prior unverified inputs appear in the abstract or described approach. The trade-off discussion on number of secrets versus recovery complexity is separate from any circularity. The result is self-contained against the base characterization, with only minor self-citation on the revisited MOLS setup that is not load-bearing for the new scheme.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The construction rests on the standard combinatorial properties of MOLS and the previously established link between MOLS and CA threshold schemes; no free parameters or new entities are introduced in the abstract.

axioms (1)
  • domain assumption The basic characterization of (2,n) threshold schemes based on CA in terms of MOLS holds and can be adapted by redefining the secret space.
    The paper explicitly states it revisits this characterization to enable the new scheme.

pith-pipeline@v0.9.0 · 5401 in / 1164 out tokens · 31595 ms · 2026-05-10T15:48:23.730482+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. HAGE: Harnessing Agentic Memory via RL-Driven Weighted Graph Evolution

    cs.AI 2026-05 unverdicted novelty 6.0

    HAGE proposes a trainable weighted graph memory framework with LLM intent classification, dynamic edge modulation, and RL optimization that improves long-horizon reasoning accuracy in agentic LLMs over static baselines.

Reference graph

Works this paper leans on

26 extracted references · cited by 1 Pith paper

  1. [1]

    Bishop, M

    A. Bishop, M. Green, Y . Ishai, A. Jain, and P. Lou. Fully anonymous secret sharing. In Y . T. Kalai and S. F. Kamara, editors,Advances in Cryptology - CRYPTO 2025, Proceedings, Part IV, LNCS, pages 356–389. Springer, 2025

    2025

  2. [2]

    G. R. Blakley. Safeguarding cryptographic keys. In1979 International Workshop on Managing Requirements Knowledge, MARK 1979, pages 313–

    1979

  3. [3]

    Blundo and D

    C. Blundo and D. R. Stinson. Anonymous secret sharing schemes.Discret. Appl. Math., 77(1):13–28, 1997

    1997

  4. [4]

    R. Con. Anonymous shamir’s secret-sharing via reed-solomon codes against permutations, insertions, and deletions.IEEE Trans. Inf. Theory, 71(12):9534– 9547, 2025

    2025

  5. [5]

    Á. M. del Rey, J. P. Mateus, and G. R. Sánchez. A secret sharing scheme based on cellular automata.Appl. Math. Comput., 170(2):1356–1364, 2005

    2005

  6. [6]

    Eldridge, G

    H. Eldridge, G. Beck, M. Green, N. Heninger, and A. Jain. Abuse-resistant location tracking: Balancing privacy and safety in the offline finding ecosys- tem. In D. Balzarotti and W. Xu, editors,33rd USENIX Security Symposium, USENIX Security 2024. USENIX Association, 2024

    2024

  7. [7]

    Eloranta

    K. Eloranta. Partially permutive cellular automata.Nonlinearity, 6(6):1009– 1023, 1993

    1993

  8. [8]

    M. J. Freedman, K. Nissim, and B. Pinkas. Efficient private matching and set intersection. In C. Cachin and J. Camenisch, editors,Advances in Cryptology - EUROCRYPT 2004, Proceedings, Lecture Notes in Computer Science, pages 1–19. Springer, 2004. 12

    2004

  9. [9]

    C. F. Gauß.Disquisitiones arithmeticae. Humboldt-Universität zu Berlin, 1801

  10. [10]

    Goldreich, S

    O. Goldreich, S. Micali, and A. Wigderson. How to play any mental game or A completeness theorem for protocols with honest majority. In A. V . Aho, editor,Proceedings of STOC 1987, pages 218–229. ACM, 1987

    1987

  11. [11]

    Herranz and G

    J. Herranz and G. Sáez. (k, n)-consecutive access structures.Des. Codes Cryptogr., 93(9):3543–3563, 2025

    2025

  12. [12]

    A. D. Keedwell and J. Dénes.Latin squares and their applications. Elsevier, 2015

    2015

  13. [13]

    Leporati and L

    A. Leporati and L. Mariot. Cryptographic properties of bipermutive cellular automata rules.J. Cell. Autom., 9(5-6):437–475, 2014

    2014

  14. [14]

    Manzoni, L

    L. Manzoni, L. Mariot, and G. Menara. Combinatorial designs and cellular automata: A survey.Discret. Appl. Math., 379:656–674, 2026

    2026

  15. [15]

    Mariot, M

    L. Mariot, M. Gadouleau, E. Formenti, and A. Leporati. Mutually orthogonal latin squares based on cellular automata.Des. Codes Cryptogr., 88(2):391–411, 2020

    2020

  16. [16]

    Mariot and A

    L. Mariot and A. Leporati. Sharing secrets by computing preimages of biper- mutive cellular automata. In J. Was, G. C. Sirakoulis, and S. Bandini, editors, Cellular Automata - 11th International Conference on Cellular Automata for Research and Industry, ACRI 2014. Proceedings, volume 8751 ofLecture Notes in Computer Science, pages 417–426. Springer, 2014

    2014

  17. [17]

    Mariot and A

    L. Mariot and A. Leporati. A cryptographic and coding-theoretic perspective on the global rules of cellular automata.Nat. Comput., 17:487–498, 2018

    2018

  18. [18]

    Mariot, A

    L. Mariot, A. Leporati, A. Dennunzio, and E. Formenti. Computing the periods of preimages in surjective cellular automata.Nat. Comput., 16(3):367–381, 2017

    2017

  19. [19]

    Mariot, S

    L. Mariot, S. Picek, A. Leporati, and D. Jakobovic. Cellular automata based s-boxes.Cryptogr. Commun., 11(1):41–62, 2019

    2019

  20. [20]

    S. J. Phillips and N. C. Phillips. Strongly ideal secret sharing schemes.J. Cryptol., 5(3):185–191, 1992

    1992

  21. [21]

    Sahai and B

    A. Sahai and B. Waters. Fuzzy identity-based encryption. In R. Cramer, editor, Advances in Cryptology - EUROCRYPT 2005, Proceedings, Lecture Notes in Computer Science, pages 457–473. Springer, 2005

    2005

  22. [22]

    A. Shamir. How to share a secret.Commun. ACM, 22(11):612–613, 1979. 13

    1979

  23. [23]

    D. R. Stinson.Combinatorial designs - constructions and analysis. Springer, 2004

    2004

  24. [24]

    D. R. Stinson and S. A. Vanstone. A combinatorial approach to threshold schemes.SIAM J. Discret. Math., 1(2):230–236, 1988

    1988

  25. [25]

    K. Sutner. De bruijn graphs and linear cellular automata.Complex Syst., 5(1), 1991

    1991

  26. [26]

    S. Wolfram. Statistical mechanics of cellular automata.Reviews of modern physics, 55(3):601, 1983. 14

    1983