How to reconstruct (anonymously) a secret cellular automaton
arXiv:2604.11362v1 [cs.CR] 13 Apr 2026
Luca Mariot1 , Federico Mazzone1 , Luca Manzoni2 , and Alberto Leporati3 1 Semantics, Cybersecurity and Services Group, University of Twente, Drienerlolaan 5,
7511GG Enschede, The Netherlands {l.mariot, f.mazzone}@utwente.nl 2 Department of Mathematics, Informatics and Geosciences, University of Trieste, Via Valerio 12/1, 34127 Trieste, Italy [email protected] 3 Department of Informatics, Systems and Communication, University of Milano-Bicocca, Viale Sarca 336/14, 20126 Milano, Italy [email protected]
April 14, 2026 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.
Keywords cellular automata · anonymous secret sharing schemes · mutually orthogonal Latin squares · parallel classes · bipermutivity · de Bruijn graphs
1
Introduction
Secret Sharing Schemes (SSS) are a fundamental cryptographic primitive underlying several key management and secure multiparty computation protocols [10, 21]. Informally, a SSS enables a dealer to share a secret value S among a set of n participants (or players), by distributing to them so-called shares of S. The sharing is done in such a way that only certain authorized subsets of players can uniquely determine the secret by pooling together their shares. 1
Historically, SSS have been introduced by Shamir [22] and Blakley [2] in the setting of (t, n) threshold access structures, meaning that the authorized subsets are all those of cardinality at least t ≤ n. When t = 2 (i.e., only two players are required to reconstruct the secret), threshold SSS have a nice characterization in terms of combinatorial designs. In fact, one can show that (2, n) perfect schemes are equivalent to sets of n Mutually Orthogonal Latin Squares (MOLS) [23]. The idea of adopting Cellular Automata (CA) to design threshold secret sharing schemes dates back at least two decades. However, early works in this research thread [5, 16] came up with threshold SSS with an additional adjacency constraint on the access structure, meaning that the shares must be contiguous CA configurations to recover the secret. Moreover, as shown by [11], such schemes cannot be perfect, unless in very trivial cases (i.e. when t = 1 or t = n). On the other hand, Mariot et al. [15] studied how to construct families of MOLS using Linear Bipermutive CA (LBCA), thereby yielding a perfect SSS with a full (2, n) threshold access structure. In this paper, we investigate the design of anonymous secret sharing schemes based on CA. To this end, we start from the construction of MOLS introduced in [15], observing that the (2, n)-threshold scheme of [17] derived from this construction requires the players to disclose both their shares and associated CA rules. Then, we observe that by redefining the set of possible secrets from the row space of the Latin squares to the family of MOLS itself allows one to partition the secrets into parallel classes, enabling anonymous reconstruction. From a practical standpoint, this entails that the players are given shares of a secret CA local rule, and the task of any two players is to reconstruct the rule without revealing to one another their respective shares. We then describe the resulting anonymous (2, n)-scheme protocol, which include both preimage computation and forward evolution of the underlying CA. Finally, we remark that the efficiency of this scheme is characterized by a trade-off between the number of secrets that can be shared and the computational complexity of the recovery phase. The remainder of this paper is organized as follows. Section 2 covers preliminary definitions about cellular automata, (anonymous) secret sharing schemes and orthogonal Latin squares used in the paper. Section 3 recalls the basic (2, n) threshold scheme introduced in [17], showing why it cannot be anonymous and describes the new scheme, proving its correctness and security properties. Finally, section 4 discusses the trade-off between the number of secrets and the computational complexity of the recovery phase, and describes some interesting open problems for further research on the subject.
2
Background
In this section, we cover the basic definitions and results needed in the later sections of the paper. We start by introducing cellular automata as algebraic systems, and continue with a brief description of secret sharing schemes and their connection to orthogonal Latin squares.
2
2.1
Cellular Automata
Cellular Automata (CA) are usually described as a particular type of discrete dynamical systems, characterized by a regular lattice of cells whose global state is updated by applying the same local rule in a shift-invariant manner to each cell. Typical questions investigated in this setting revolve around the long-term dynamics induced by the repeated application of the CA global rule over multiple time steps, for example the characterization of its fixed points and limit cycles. On the other hand, in this work we consider CA under the perspective of algebraic systems, since we are interested only in a single application of the CA global rule [14]. In particular, we formally define a no boundary CA (NBCA) as follows: Definition 1. Let Σ be a finite set of size q ∈ N, and let d, n ∈ N such that d ≤ n. Further, let f : Σd → Σ be a d-variable mapping over Σ. Then, a no-boundary CA over the alphabet Σ with n input cells and local rule f of diameter d is a mapping F : Σn → Σn−d+1 defined for all x ∈ Σn as: F(x1 , . . . , xn ) = ( f (x1 , . . . , xd ), f (x2 , . . . , xd+1 ), . . . , f (xn−d+1 , . . . , xn )) .
(1)
In other words, a NBCA is a particular type of vectorial function where each output coordinate i ∈ {1, · · · , n} is defined as the application of the CA local rule f to the neighborhood composed of the i-th input cell and the d − 1 cells to its right. Notice that the global rule of a NBCA cannot be iterated for an indefinite number of steps, since the size of the cellular array “shrinks” by d − 1 cells at each iteration. Other models, such as periodic boundary CA [19], retain the whole cellular array from one iteration to the next, turning effectively a CA into a discrete dynamical system. However, as remarked earlier, we will be interested only in NBCA seen as algebraic systems, with a single application of the CA global rule F. The most natural way to represent the local rule f : Σd → Σ is by means of a lookup table of qd rows, which defines the next state f (x) of a cell for each configuration x ∈ Σd of its neighborhood. When Σ = F2 = {0, 1}, the lookup table is a Boolean function of d variables. In this case, the decimal encoding of the truth table’s output column is also called the Wolfram code of the rule [26]. Another useful way to encode the local rule f of a CA is the de Bruijn graph G f = (V, E), where V = Σd−1 and given u, v ∈ V the pair (u, v) is connected by a directed edge if and only if they overlap respectively on the rightmost and leftmost d − 2 coordinates. A local rule f : Σd → Σ can then be represented as a labeling function l f : E → F2 on the edges of G f , where for each (u, v) ∈ E, one defines l(u, v) = f (u ⊙ v), with u ⊙ v ∈ Fd2 denoting the fusion operator of u and v as defined in [25]. Intuitively, u ⊙ v is the vector of d variables defined by adding the rightmost coordinate of v to u. The output of a CA equipped with rule f corresponds to a path on the edges of G f . As an example, Figure 1 depicts the de Bruijn graph of rule f : F32 → F2 defined as f (x1 , x2 , x3 ) = x1 ⊕ x2 ⊕ x3 , whose Wolfram code is 150, along with its truth table.
3
0 00 1
1 0
10
01 1 0
0 11
u→v 00 → 00 10 → 00 01 → 10 11 → 10 00 → 01 10 → 01 01 → 11 11 → 11
x = u⊙v 000 100 010 110 001 101 011 111
f (x) = l f (u, v) 0 1 1 0 1 0 0 1
1
Figure 1: Example of orthogonal labelings for the de Bruijn graph G2,2 induced by the CA local rules 90 and 150 of diameter d = 3. A local rule f : Σd → Σ is called leftmost (respectively, rightmost) permutive if, by fixing all input coordinates x2 , . . . , xd (respectively, x1 , . . . , xd−1 ) to any constant value, the restriction of f on the remaining variable is a permutation over Σ. Accordingly, a local rule is called bipermutive if it is both leftmost and rightmost permutive. For the binary case, this means that a bipermutive rule f : Fd2 → F2 can be written as f (x1 , . . . , xd ) = x1 ⊕ g(x2 , . . . , xd−1 ) ⊕ xd , where g : Fd−2 → F2 is the 2 generating function of f [13]). Bipermutive CA are surjective, since the labels of the outgoing (respectively, ingoing) edges of any vertex v ∈ V of the de Bruijn graph induce a permutation of the alphabet (therefore, one the edges can be traversed in both directions). Beside binary CA, we consider the case of CA defined over the finite field alphabet Fq , with its size q being a power of a prime number. A local rule f : Fdq → Fq is called linear if it is defined as a linear combination of the input variables, that is f (x1 , . . . , xd ) = a1 x1 + . . . + ad xd for all x = (x1 , . . . , xd ) ∈ Fdq , where a1 , . . . ad ∈ Fq and the sum and multiplication correspond to the field operations. A NBCA F : Fnq → Fn−d+1 defined by a linear local rule can then be expressed as a linear q map F(x) = MF · x⊤ , where MF is a (n − d + 1) × n transition matrix defined by successive shifts of the coefficients a1 , . . . , ad . One can also associate to a linear local rule f the polynomial p f (X) = a1 + a2 X + . . . + ad X d−1 . Under the lens of error-correcting codes, MF and p f are respectively the generator matrix and the generator polynomial of a cyclic code [17]. Clearly, any linear rule is bipermutive if and only if both a1 and ad are not null. In this case, the CA is called a Linear Bipermutive CA (LBCA).
2.2
Secret Sharing Schemes
Informally, a secret sharing scheme is a protocol where a dealer wishes to share a secret S (such as a private key to sign documents) with a set of n participants or players P = {P1 , P2 , · · · , Pn }. During the setup phase of the scheme, the dealer 4
computes n shares of S, denoted as B1 , . . . , Bn , and distribute them respectively to the players P1 , . . . Pn . At a later stage, any authorized subset A ⊆ P can recover the secret S by pooling together the shares of the corresponding players. The access structure Γ ⊆ 2P lists all authorized subsets of the scheme, and it is defined as the union-closure of its basis Γ0 , which specifies all minimal authorized subsets. In (t, n) threshold schemes (such as those introduced by Shamir [22] and Blakley [2]), every subset of at least t players is authorized; therefore, the basis of the access structure is defined as Γ0 = {A ⊆ P : |A| = t}. The security of a secret sharing scheme is characterized by the information that unauthorized subsets can gain on the value of the secret. In particular, a scheme is called perfect if it does not leak any information about S by knowing the shares of any unauthorized subset. More formally, if the secret S is drawn from S according to a probability distribution Pr(S), then for any unauthorized subset U ∈ / Γ it holds Pr(S|U) = Pr(S). Assuming that a suitable notion of size on the secret and the shares (e.g., the number of bits required to encode them), a perfect secret sharing scheme is called ideal if for all S ∈ S the size of the shares induced by any secret S equals the size of S. Most of the constructions for threshold schemes assumes that the identities of the players in an authorized subset are known. This usually requires a separate identification protocol during the reconstruction phase. Anonymous secret sharing schemes, initially introduced by Stinson and Vanstone [24], circumvent this problem by recovering the secret only as a function of the shares value, without associating them to the players’ identities. Phillips and Phillips [20] analyzed the conditions under which an anonymous secret sharing scheme can be ideal, showing that this property is met only in the (1, n) and (n, n) access structures. Later, Blundo and Stinson [3] proved lower bounds on the size of the share sets in any (t, n) anonymous secret sharing scheme. More recently, other works [6, 1, 4] studied anonymous secret sharing with additional properties, such as unlinkability of shares from different unauthorized subsets. We do not consider such schemes in the scope of this work, referring the reader to [4] for more information about them.
2.3
Latin Squares
We recall only the basic definitions about Latin squares that are relevant for the characterization of (2, n) threshold schemes. A thorough treatment of this subject can be found in [12]. Given n ∈ N, we denote by [N] = {1, . . . , N} the set of the first N integer positive numbers. A Latin square of order N ∈ N is an N × N matrix L with entries from [N] such that for all i, j, k ∈ [N] with j ̸= k, one has that L(i, j) ̸= L(i, k) and L( j, i) ̸= L(k, i). Equivalently, every row and column of a Latin square is a permutation of [N]. Two Latin squares L1 , L2 of order N ∈ N orthogonal if for all distinct pairs of coordinates (i, j), (i′ , j′ ) ∈ [N] × [N] it holds that (L1 (i, j), L2 (i, j)) ̸= (L1 (i′ , j′ ), L2 (i′ , j′ )). In other words, the superposition of two orthogonal Latin squares is a permutation of the Cartesian product [N] × [N]. A 5
family of n Mutually Orthogonal Latin Squares (also denoted as n-MOLS) is a set of n Latin squares that are pairwise orthogonal As shown for example in [23], families of n-MOLS can be used to construct (2, n) threshold secret sharing schemes. In particular, suppose that L1 , . . . Ln are Latin squares of order N such that Li and L j are orthogonal for each i ̸= j. We assume that this family is public, hence known to any participant in the scheme (and possibly also to adversaries). Then, one can define the secret and the share spaces as S = B = [N]. The dealer encodes S ∈ [N] as a row of the squares, and selects a random column R ∈ [N]. The shares to be distributed to the players are then the entries L1 (S, R), . . . , Ln (S, R). Later, if any two players i, j combine their shares, then since Li and L j are orthogonal they know that the pair (Li (S, R), L j (S, R)) occurs exactly once the superposed squares, allowing to retrieve uniquely the row and column coordinates, and thus the secret row S. On the other hand, if a single player i tries to reconstruct S on their own, the value Li (S, R) occurs N times on the Latin square Li . Therefore, if the dealer selected the random column R with uniform probability, every value of the secret is equally likely. Thus, the scheme is perfect and also ideal, since the secret and share sets coincide. On the other hand, the scheme is not anonymous, since each player must know their associated Latin square to allow reconstruction. Mariot et al. [15] investigated families of MOLS generated by CA, motivated by the application to (2, n) threshold schemes. The first step of is to define the Cayley table induced by a NBCA. To this end, assume that a total order is defined on Σd−1 and that φ : Σd−1 → [N] is a monotone bijective mapping between Σd−1 and [N], with the latter having the usual order of natural numbers. The inverse mapping of φ is denoted by ψ = φ−1 . Then, Cayley table associated to the NBCA F : Σn → Σn−d+1 is the N × N matrix CF with entries from [N] such that CF (i, j) = φ(F(ψ(i)||ψ( j))) for all 1 ≤ i, j ≤ N, where || denotes concatenation. Thus, the output of the CA corresponds to the entry of the Cayley table at the row and column coordinates represented by the left and the right half of the CA input configuration, respectively. Next, the authors of [15] showed that the Cayley table associated to any NBCA F : Σ2(d−1) → Σd−1 equipped with a bipermutive local rule f : Σd → Σ is a Latin square of order N = qd−11 Then, they proved the following characterization of LBCA pairs whose associated Latin squares are orthogonal: 2(d−1)
Theorem 1 ([15]). Let F, G : Fq → Fd−1 be two linear bipermutive CA, and q let p f , pg ∈ Fq [X] be the respective associated polynomials. Then, the corresponding Latin squares CF and CG of order N = qd−1 are orthogonal if and only if gcd(p f , pg ) = 1, i.e. if and only if p f and pg are relatively prime. Hence, one can construct a family of n-MOLS (or equivalently, a (2, n) scheme) based on LBCA by finding a set of n polynomials of degree k = d − 1 and with a nonzero constant term that are pairwise coprime. The authors of [15] further proved that the size of a maximal family of Mutually Orthogonal Latin Squares based on 1 The same result was independently observed much earlier under a different guise by Eloranta [7].
6
linear CA (also called linear MOCA) equals: ⌊n/2⌋
Nk = Ik + ∑ I j ,
(2)
j=1
where Ir denotes for r ∈ N the number of irreducible polynomials of degree r over Fq , computed using Gauss’s formula [9].
3
Anonymous Secret Sharing with CA
3.1
Basic (2, n) Threshold Scheme based on MOCA
We start by first recalling how the basic (2, n) threshold scheme based on MOCA proposed in [17] works. Let Σ be an alphabet of q symbols, d ∈ N and assume that we have n players P1 , P2 , . . . , Pn . The secret and share spaces coincide with the set Σd−1 of configurations of d − 1 cells. Hence, we have |S | = |B | = qd−1 . The dealer publishes a set of n bipermutive local rules f1 , . . . fn : Σd → Σ, not necessarily linear, that give rise to a set of n-MOCA. Setup Phase.
The setup phase of the protocol works as follows:
1. The dealer selects the secret S ∈ Σd−1 to be shared, and concatenates it with a random block R ∈ Σd−1 , thus obtaining the input configuration x = S||R ∈ Σ2(d−1) . 2. For each i ∈ [n], the dealer computes the NBCA Fi : Σ2(d−1) → Σd−1 equipped with rule fi on the configuration x, obtaining Bi = Fi (x) ∈ Σd−1 3. For each i ∈ [n], the dealer sends Bi to the player Pi . Recovery Phase. Given two players Pi , Pj and their respective shares Bi , B j , the recovery phase unfolds in the following steps: 1. Pi and Pj fetch the CA local rules fi , f j published by the dealer, and construct the corresponding coupled de Bruijn graph Gi, j , which is simply the superposition of the de Bruijn graphs of fi and f j . Thus, each edge (u, v) of Gi, j is labeled with with the ordered pair ( fi (u ⊙ v), f j (u ⊙ v)). 2. Pi and Pj pool their shares Bi , B j and find the path W on the edges of Gi, j that is labelled as ((Bi,1 , B j,1 ), . . . , (Bi,d−1 , B j,d−1 )). Notice that there is a unique such path, since the Latin squares of fi and f j are orthogonal. 3. Determine the original input configuration x ∈ Σ2(d−1) by computing the fusion operator ⊙ on the vertices visited by the path W . The secret can then be returned as the left half of x.
7
In particular, the reconstruction of the unique path on the edges labelled by the two superposed shares can be performed with the I NVERT-OCA algorithm described in [17]. Although this scheme is perfect and ideal, as in any MOLS-based construction, it does not allow for anonymous reconstruction, since the players i and j need to know the corresponding local rules fi and f j that the dealer used to compute their shares.
3.2
Modified MOCA-based Anonymous Scheme
The scheme described above encodes the secret and the shares as blocks of d − 1 cells, respectively encoding the row and the entries of the Latin squares generated by the family of MOCA. Each MOCA, on the other hand, is assigned to a player. We now take a different approach: we encode the secret as one of the Latin squares, or equivalently one of the CA rules, i.e. S = { f1 , . . . , fn }. On the other hand, the space of the shares becomes B = Σ2(d−1) , that is, the set of all possible input configurations of the CA. Further, the number of players that can participate in the scheme now corresponds to the number of preimages that map to a specific output block y ∈ Σd−1 , which are qd−1 due to the balancedness property of surjective CA [18]. Setup Phase.
The setup phase of the modified scheme is as follows:
1. The dealer chooses the secret CA rule index S ∈ {1, . . . , n} and selects a random output block of d − 1 cells R ∈ Σd−1 2. The dealer computes the counterimage of S under the secret rule fS , that is the set FS−1 (R) = {x ∈ Σ2(d−1) : FS (x) = R}. This can be done by constructing the qd−1 paths on the edges of the de Bruijn graph G fS labelled with R, starting from each vertex v ∈ Σd−1 . 3. Denoting FS−1 (R) = {B1 , B2 , . . . , Bqd−1 }, the dealer distributes the share Bi to the player Pi , for all i ∈ [qd−1 ]. Thus, the setup phase entails selecting a single CA in the MOCA family as the secret, and then computing the set of preimages of a random output block of this CA, which constitute the shares distributed to the players. Recovery Phase. For the recovery, we assume that the dealer published all local rules f1 , . . . , fn . Suppose now that players Pi and Pj wish to reconstruct the secret. The recovery starts with a non-interactive step, where both players perform computations on their own without interacting with each other. We describe below the non-interactive step of Pi (the step of Pj is completely symmetrical, changing each i index to j): 1. For all k ∈ [n], player Pi evaluates the k-th CA over their share, i.e. Pi computes yi,k = Fk (Bi ). 8
2. For all k ∈ [n], Pi computes the counterimage of yi,k under rule fk , i.e. the set Ai,k = Fk−1 (yi,k ) = {x ∈ Σ2(d−1) : Fk (x) = yi,k }. At this point, Pi and Pj have constructed two families of counterimages, respectively Ai = {Ai,1 , . . . , Ai,n } and A j = {A j,1 , . . . , A j,n }. The interactive phase now works as follows: 1. Pi and Pj compute the intersection Ai ∩ A j . 2. The result of the intersection uniquely identifies the secret CA rule fS selected by the dealer during the setup phase.
3.3
Analysis of the Scheme
In what follows, we prove the correctness of the above scheme and analyze its security, showing that it is both perfect and anonymous. Lemma 1. The intersection computed by Pi and Pj during the last step of the protocol yields a single element, and this element is the counterimage AS = FS−1 (R) computed by the dealer in the setup phase, which uniquely identifies the secret CA rule fS . Proof. For any i ∈ [n], consider the CA Fi : Σ2(d−1) → Σd−1 equipped with rule fi : Σd → Σd . The counterimages Fi−1 (y) of the output blocks y ∈ Σd−1 of the CA partition the input space of Σ2(d−1) . In fact, fixing an output block y ∈ Σd−1 and determining its counterimage basically means to construct the set of coordinates that feature y as an entry on the Latin square of Fi . Due to the property of the Latin square, two different outputs y ̸= y′ cannot share the same row and column coordinates. In the terminology of combinatorial designs, the partition Πi = {Fi−1 (y) : y ∈ Σd−1 } is also called a 1-parallel class, since it is a set of subsets all of the same size (qd−1 , due to the balancedness property) where each x ∈ Σ2(d−1) appears exactly once. Consider now the set of all parallel classes Π1 , . . . , Πn induced by the n-MOCA f1 , . . . , fn . Then, any two subsets belonging to different classes Πi , Π j can intersect in at most one preimage. Indeed, suppose that Πi and Π j have two subsets of counterimages intersecting on more than one preimage: then, it means that the superposition of the Latin squares generated by fi , f j have a repeated pair of entries, contradicting the orthogonality property. Therefore, since the shares held by Pi and Pj have been taken from the same subset of preimages FS−1 (R) generated by the dealer in the setup phase, by construction Ai ∩ A j can intersect only in that subset. Once the two players have identified the unique parallel class ΠS to which the subset resulting from the intersection belongs to, they can easily determine what is the secret CA rule fS . The next result proves that the new scheme is also perfect, and moreover it allows anonymous reconstruction:
9
Lemma 2. The modified MOCA-based scheme is a perfect and anonymous (2, qd−1 ) threshold secret sharing scheme. Proof. Without loss of generality, suppose that the player Pi tries to reconstruct the secret CA rule starting from the share Bi . Then, what Pi can do is to follow the noninteractive step of the recovery phase, computing the output blocks yi,k = Fk (Bi for all CA fk with k ∈ [n], and then constructing the corresponding sets of counterimages Ai,k = Fk−1 (yi,k ). By construction, each counterimage belongs to a distinct parallel class Πk , and they all intersect on Bi . Thus, under the assumption that the dealer chose the random output block R ∈ Σd−1 with uniform probability during the setup phase, any of the counterimages generated by Pi is equally likely to be the one computed by the dealer. Therefore, Pi does not obtain any information on the correct parallel class ΠS , and thus on the secret CA rule fS . Concerning anonymity, remark that the intersection of Ai ∩ A j returns a subset of preimages, which contains the shares Bi and B j . However, the reconstruction phase does not require to identify Bi and B j as the shares held by Pi and Pj , since the subset is directly associated to the parallel class ΠS . Thus, the scheme also allows for anonymous reconstruction. Remark 1. There is an important caveat to consider in the anonymity proof of Lemma 2: namely, how to compute the intersection of Ai and A j , which are held respectively by Pi and Pj . The most straightforward solution is that both Pi and Pj disclose to each other their sets Ai and A j , and then compute the intersection together. However, this procedure would break anonymity. For example, suppose that Pi wants to find out the share held by Pj . Then, Pi can simply check what is the value that occur in every preimage set received from Pj . By construction, such value corresponds to B j . To solve this issue, the two players can resort to a Private Set Intersection (PSI) protocol, which allows two parties to compute the intersection of their private sets without disclosing them [8]. Example 1. We conclude this section by presenting a fully worked out example of the scheme described so far. Let q = 2 and d = 3, i.e. we work with binary elementary CA. In this case, there are only two orthogonal CA, namely those defined by the linear local rules f (x1 , x2 , x3 ) = x1 ⊕ x3 and g(x1 , x2 , x3 ) = x1 ⊕ x2 ⊕ x3 , i.e. rule 90 and 150. By Theorem 1 these rules form orthogonal Latin squares of order 23−1 = 4, because their associated polynomials p f (X) = 1 + X 2 and pg (X) = 1 + X + X 2 are coprime. Figure 2 displays the Latin squares associated to rule 90 and 150, and their partition in parallel classes. Remark that in the parallel classes we encode the row-column coordinates (i, j) ∈ [4] × [4] as single integer numbers from 1 to 16, using lexicographic ordering. The secret space is thus composed only of two rules, S = { f90 , f150 }. The share set coincides with the set F42 = {0, 1}4 of all 16 input configurations of 4 bits, and the scheme has 23−1 = 4 players, i.e. P = {P1 , P2 , P3 , P4 }. Suppose now that the dealer selects f90 as the secret rule, and samples 10 as a random output block configuration. Thus, the shares are calculated by computing the 4 preimages of 10 under rule 90. From the table of the parallel classes decomposition, this corresponds to the set {2, 5, 12, 15} and 10
1
2
3
4
1
4
3
2
2
1
4
3
2
3
4
1
3
4
1
2
4
1
2
3
4
3
2
1
3
2
1
4
(a) Rule 90
(b) Rule 150
y Π90 Π150 00 (1) {1, 6, 11, 16} {1, 8, 10, 15} 10 (2) {2, 5, 12, 15} {4, 5, 11, 14} 01 (3) {3, 8, 9, 14} {3, 6, 12, 13} 11 (4) {4, 7, 10, 13} {2, 7, 9, 16} (c) Parallel classes
Figure 2: Latin squares generated by rules 90 and 150, and related parallel classes. the shares therein are distributed to the four players: B1 = 2, B2 = 5, B3 = 12 and B4 = 15. Later, let us assume that P1 and P3 want to reconstruct the secret rule by combining their shares. Then, P1 and P3 evaluate the CA F90 , F150 : F42 → F22 respectively on their shares B1 and B3 as inputs, thus obtaining: y1,90 = F90 (2) = 10, y1,150 = F150 (2) = 11, y3,90 = F90 (12) = 10, and y3,150 = F150 (12) = 01. Next, P1 and P3 construct the preimage sets of the output blocks computed in the previous step, thus obtaining the sets:
A1 = {{2, 5, 12, 15}, {2, 7, 9, 16}} , A3 = {{2, 5, 12, 15}, {3, 6, 12, 13}} . Finally, the intersection A1 ∩ A3 yields the subset {2, 5, 12, 15}, which allows to uniquely identify the parallel class Π90 , thus recovering the secret rule f90 .
4
Discussion and Open Problems
While the scheme presented in the previous section is conceptually simple from an abstract point of view, some considerations on its computational complexity are in order. Both in the setup and the recovery phase, the most expensive operation is computing the set of preimages of an output block under the action of a bipermutive CA. In particular, the number of preimages is exponential in the size d − 1 of an output block, which is determined by the diameter of the CA. Moreover, while in the setup phase the dealer only constructs a single preimage set (the one corresponding to the random output block R under the action of the secret CA), recovery requires that both players construct a set of preimages for each CA rule. This adds a multiplicative factor of n, giving an overall complexity of O (nqd )2 for a player Pi to compute their set Ai . Consequently, the higher is the number of CA rules that can be possibly shared, the larger will be the time required for the players to reconstruct the secret. These remarks prompt us with two interesting open problems for future research. The first one is to find a more efficient algorithm to determine the common parallel class between two players, that does not require to compute the full preimage sets. 2 Of course, we are factoring out the complexity required to compute a single preimage.
11
An interesting approach here could be to explore secure multiparty computation techniques over the de Bruijn graph representation of the local rules, to check on the fly whether the preimage sets that is being computed by the two players is the same or not. The second problem is to investigate more in depth the information ratio of this scheme, i.e. the ratio between the size of the shares and the size of the secrets. Clearly, the scheme described in this paper is not ideal, as the number of shares (which correspond to blocks of size d − 1) is always higher than the number of secrets that can be shared, which correspond to the maximum number of MOCA that can be constructed for a given diameter. We also note that, while the construction for maximal MOCA families exhibited in [15] based on linear CA is the best known so far, it is not known whether one can construct even larger families of MOCA with nonlinear CA.
References [1] 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. [2] G. R. Blakley. Safeguarding cryptographic keys. In 1979 International Workshop on Managing Requirements Knowledge, MARK 1979, pages 313– 318. IEEE, 1979. [3] C. Blundo and D. R. Stinson. Anonymous secret sharing schemes. Discret. Appl. Math., 77(1):13–28, 1997. [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. [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. [6] H. Eldridge, G. Beck, M. Green, N. Heninger, and A. Jain. Abuse-resistant location tracking: Balancing privacy and safety in the offline finding ecosystem. In D. Balzarotti and W. Xu, editors, 33rd USENIX Security Symposium, USENIX Security 2024. USENIX Association, 2024. [7] K. Eloranta. Partially permutive cellular automata. Nonlinearity, 6(6):1009– 1023, 1993. [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
[9] C. F. Gauß. Disquisitiones arithmeticae. Humboldt-Universität zu Berlin, 1801. [10] 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. [11] J. Herranz and G. Sáez. (k, n)-consecutive access structures. Des. Codes Cryptogr., 93(9):3543–3563, 2025. [12] A. D. Keedwell and J. Dénes. Latin squares and their applications. Elsevier, 2015. [13] A. Leporati and L. Mariot. Cryptographic properties of bipermutive cellular automata rules. J. Cell. Autom., 9(5-6):437–475, 2014. [14] L. Manzoni, L. Mariot, and G. Menara. Combinatorial designs and cellular automata: A survey. Discret. Appl. Math., 379:656–674, 2026. [15] 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. [16] L. Mariot and A. Leporati. Sharing secrets by computing preimages of bipermutive 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 of Lecture Notes in Computer Science, pages 417–426. Springer, 2014. [17] L. Mariot and A. Leporati. A cryptographic and coding-theoretic perspective on the global rules of cellular automata. Nat. Comput., 17:487–498, 2018. [18] 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. [19] L. Mariot, S. Picek, A. Leporati, and D. Jakobovic. Cellular automata based s-boxes. Cryptogr. Commun., 11(1):41–62, 2019. [20] S. J. Phillips and N. C. Phillips. Strongly ideal secret sharing schemes. J. Cryptol., 5(3):185–191, 1992. [21] 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. [22] A. Shamir. How to share a secret. Commun. ACM, 22(11):612–613, 1979.
13
[23] D. R. Stinson. Combinatorial designs - constructions and analysis. Springer, 2004. [24] D. R. Stinson and S. A. Vanstone. A combinatorial approach to threshold schemes. SIAM J. Discret. Math., 1(2):230–236, 1988. [25] K. Sutner. De bruijn graphs and linear cellular automata. Complex Syst., 5(1), 1991. [26] S. Wolfram. Statistical mechanics of cellular automata. Reviews of modern physics, 55(3):601, 1983.
14