On the Leakage of Massey Secret Sharing Schemes under Linear Computations Nadja Aoutouf1,2,3 and Daniel Augot1,2,3 1
INRIA École Polytechnique 3 LIX, CNRS UMR 7161
arXiv:2609.19929v1 [cs.CR] 17 Sep 2026
2
Abstract. Leakage attacks on secret sharing schemes exploit partial information about individual shares to recover the underlying secret. In coding theory, linear exact repair schemes (LERSs) enable the recovery of one codeword symbol from a small amount of information obtained from the remaining symbols, provided that the code has sufficiently low rate. This can be interpreted as recovering the secret from partial information, namely subfield symbols, of the shares. Recently, a randomized construction based on subfield subcodes was proposed for constructing LERS-derived leakage attacks against Massey secret sharing schemes based on general linear codes. We extend this framework to multiple shared secrets whose corresponding shares are related through linear computations, with leakage also allowed on the computation outcomes. More precisely, we consider N secrets, of which K < N are linearly independent input values and the remaining N − K secrets are determined by linear computations on these inputs. We analyse the existence of LERS-derived leakage that exploits this structure. We first study the case of addition and then generalize our construction to arbitrary linear computations. Our analysis applies to general linear codes of length n+1 and dimension k over Fqm with k ≤ N n/(Km), and supports arbitrary linear computations, whereas the previous subfield subcode construction only applies to k ≤ n/m − 1. Consequently, exploiting the linear relations enables LERS based leakage which extend the range of code parameters vulnerable to such attacks. Finally, identical leakage functions can arise for certain linear relations, making this a more realistic yet still potentially powerful attack model. Finally, simulations indicate that identical leakage functions can be used for certain linear relations, yielding a more realistic attack model. Keywords: Leakage Function, Linear Repair Scheme, Side-Channel Attack, Massey Secret Sharing Scheme, Linear Operations, MPC
1
Introduction
Surprisingly, linear secret sharing schemes can themselves be subject to leakage attacks. In the leakage model for such attacks, each share is associated with 1
a leakage function, such that the adversary obtains partial information about each share rather than the entire share. For example, an attacker may physically place a wire on an embedded device to measure a value of interest [AK96]. Such attacks pose a serious threat to cryptographic implementations which use secret sharing (masking) to protect sensitive data. These concerns initiated a line of work, beginning with [Ben+18] and culminating in [Kas24; Ngu25], with the goal of studying the leakage resilience threshold of Shamir’s secret sharing scheme. In these works, the interplay between various parameters, such as the threshold, the amount of information provided by the leakage, and the extension degree, is studied. The authors determine ranges of these parameters that guarantee resilience against arbitrary leakage from each share, regardless of the specific leakage functions chosen by the adversary. From a constructive coding-theoretic perspective, viewed as an attack in cryptanalysis, Guruswami and Wootters [GW16] construct a linear exact repair scheme for full-support Reed–Solomon codes, which directly yields leakage functions for Shamir’s secret sharing scheme. More precisely, consider a Reed– Solomon code of length n + 1 over Fqm with evaluation points α0 , . . . , αn , such that the secret is identified with the first codeword symbol c0 , while the adversary obtains, from each share cj , j ∈ [n], the leakage TrF/B (cj /αj ) ∈ Fq . In [GW16] it is shown that these leaked subsymbols are sufficient to reconstruct c0 for Reed–Solomon codes of dimension less than (n + 1)(1 − 1/q). In particular, when q = 2, the secret can be recovered from one bit of leakage from each share. The construction of explicit leakage functions beyond the Reed–Solomon setting is considerably less understood. A recent approach based on subfield subcodes [AA26] provides a general method for constructing leakage functions for secret sharing schemes induced by arbitrary linear codes. Given a linear code ⊥ C ⊆ Fn+1 q m and its dual C , this approach gives a randomized construction of leakage functions that enable secret recovery whenever the dimension of C is less than or equal to n/m − 1. We refer to this result as the base case. 1.1
Motivation
Massey’s secret sharing scheme generalizes Shamir’s secret sharing scheme by replacing Reed–Solomon codes with general codes [Mas93]. In cryptography, for instance in secure multiparty computation or in masking for protecting implementations, secrets can be processed through computations on their shares. For example, in threshold signature schemes, secret keys are distributed among several parties [BPR22]. LERS-derived leakage resilience of secret sharing schemes has been mainly studied with respect to the recovery of a single secret from partial information leaked from its shares. The analysis of such leakage when some computations involve shared secrets has received significantly less attention. This raises the question: can an adversary exploit this additional computational structure to recover the original secrets? In this work, we investigate this question for Massey’s secret sharing schemes based on linear codes, considering, as a first step, linear computations. 2
1.2
Contribution
Massey’s secret sharing schemes induced by a linear code C ⊆ Fn+1 q m naturally preserve linear computations on secrets. For example, if secrets u, v, w ∈ Fqm satisfy the additive relation u+v = w, then the corresponding maskings cu , cv , cw ∈ C of the secrets, such that u = cu,0 , v = cv,0 , and w = cw,0 , satisfy cu + cv = cw . In this paper, we study the LERS based leakage in such settings. Our main contributions are as follows. – Leakage attacks for additive relation. We show that a single additive relation w = u + v for secrets u, v and w enables leakage attacks beyond the base case of [AA26]: for k ≤ 3n/(2m), there exist, with high probability, leakage functions that recover the secret from only 3n subsymbols over Fq , while the base case (without computation) is restricted to k ≤ n/m − 1. – Experimental validation. We validate our theoretical findings through simulations for the case of addition. – Generalization to linear computations For arbitrary linear computations with N secrets, of which K are linearly independent, and the remaining N − K secrets are obtained by linear computations, we derive the bound k ≤ N n/(Km). – Use of identical leakage functions. We prove that the simple additive relation cannot be exploited when the same leakage functions are reused. More precisely, any such repair scheme reduces to a repair scheme for the corresponding base code, yielding no improvement over the base case. However, simulations indicate that for a general linear relation µu u + µv v = w with µu ̸= µv ∈ F\{0, 1}, the same leakage functions can be reused while still exploiting the linear relation, making this a more realistic leakage attack.
2
Preliminaries
For a positive integer n, we use the notation [n]0 := {0, 1, . . . , n} and [n] := {1, . . . , n}. We denote by B = Fq the finite field of size q and by F an extension field of B of degree m. We consider linear codes over F of length n+1. A [n+1, k]F code (we omit the minimum distance d, as it will not be needed in the following) is a k-dimensional F-linear subspace of Fn+1 . Whenever convenient, we also write k(C) (resp. n(C)) for the dimension (resp. length) of C. Furthermore, we denote the redundancy of C by r(C) = n(C) − k(C) and the dual of C by D. 2.1
Puncturing and Shortening
Let C be a [n + 1, k]F code and let I ⊆ [n]0 be an index set. The puncturing of C at I, denoted by C I , is the code of length n + 1 − |I| obtained by deleting the coordinates indexed by I, i.e., C I := (cj )j∈[n]0 \I (c0 , . . . , cn ) ∈ C . The shortening of C at I, denoted by C I , is the code obtained by restricting to codewords that vanish on the coordinates in I and subsequently deleting these coordinates, i.e., C I := (cj )j∈[n]0 \I (c0 , . . . , cn ) ∈ C, ci = 0 for all i ∈ I . It 3
is well known that (C ⊥ )I = (C I )⊥ . Moreover, if H is a parity-check matrix of C, then a parity-check matrix of C I is obtained by deleting from H the columns indexed by I. For readability, we will often omit the index set I and simply write C and C. 2.2
Massey Secret Sharing Schemes
We use the well-established connection between linear codes and secret sharing schemes [Mas93], and follow the terminology of [Dor+26]. We refer to a [n0 + 1, k0 ]F code C0 as the base code, which we assume admits a generator matrix G0 of the form −1 ϕ , (1) G0 = 0 G0 where ϕ ∈ Fn0 is nonzero and G0 is a generator matrix of the shortening of C0 at the first coordinate. Every h ∈ D0 admits a unique extension (h0 , h) ∈ D0 , where h0 = ϕ · hT . We refer to the B-linear map ϕD0 : D0 −→ F h 7−→ ϕ · hT
(2)
as the extension map associated with D0 . Note that the assumption ϕ ̸= 0n0 ensures that ϕD0 is nontrivial. Let s ∈ F be a secret. The dealer samples a random codeword c = (c0 , . . . , cn0 ) ∈ C0 with the constraint c0 = s. The corresponding shares are c1 , . . . , cn0 . 2.3
Subfield Subcodes
Let C ⊆ Fn+1 be a linear code. Its subfield subcode with respect to B is defined as CB := C ∩ Bn+1 . Let ζ = (ζ1 , . . . , ζm ) be a basis of F over B. For a matrix M ∈ Fu×v , we denote by MB ∈ Bum×v the matrix obtained by expanding each entry of M with respect to ζ, column-wise. More precisely, the rows of MB are indexed by pairs (i, ℓ), and (MB )(i,ℓ),j = (Mij )ℓ , where (Mij )ℓ denotes the ℓ-th coordinate of Mij with respect to ζ. Similarly, we denote by M B ∈ Bu×vm the row-wise expansion of M . If H ∈ F(n+1)×(n+1−k) is a parity-check matrix of C, then HB is a (not necessarily full rank) parity-check matrix of CB . This gives dimB (CB ) ≥ n + 1 − m(n + 1 − k). 2.4
(3)
Linear Exact Repair Scheme by Guruswami and Wootters
In a linear exact repair scheme (LERS), an erased codeword symbol is recovered from partial information obtained from the remaining symbols, rather than by downloading the full symbols. In [GW16], Guruswami and Wootters showed that this approach can be used to repair an erased symbol of a Reed–Solomon codeword. The determination of a secret from leakage in a Massey secret sharing scheme can be viewed as a linear exact repair problem: the secret coordinate c0 is recovered from partial information obtained from the remaining code symbols. A simplified version of a LERS is formalized as follows. 4
Definition 1. A linear exact repair scheme (LERS) for a [n+1, k]F code C with respect to a subfield B ⊆ F consists of – B-linear maps gj : F → B for j ∈ [n], – a B-linear reconstruction map R : Bn → F, such that, for every c = (c0 , . . . , cn ) ∈ C, we have c0 = R g1 (c1 ), . . . , gn (cn ) . The main result of Guruswami and Wootters shows that full-length Reed–Solomon codes over F admit a LERS over B when their dimension is sufficiently small. Theorem 1 ([GW16]). Let [F : B] = m, n + 1 = q m , and k ≤ (1 − 1q )(n + 1). Then the Reed–Solomon code RS[α, k] of length n + 1, with support equal to the whole field F, admits a LERS over B. More generally, [GW16] gives a criterion for the existence of a LERS. Theorem 2 ([GW16]). Let C0 be a base [n0 + 1, k0 ]F code. If there exist m dual codewords h(1) , . . . , h(m) ∈ D0 satisfying (1) (m) dimB spanB {h0 , . . . , h0 } = m, (4) (1) (m) dimB spanB {hj , . . . , hj } ≤ 1, ∀ j ∈ [n0 ], (5) then there exists a LERS requiring at most n0 B-symbols. Proof. Let ζ1 , . . . , ζm be a basis of F over B. By condition (4), there exist dual (i) codewords h(1) , . . . , h(m) ∈ D0 such that h0 = ζi for i ∈ [m]. By condition (5), (i) (i) (i) there exist β1 , . . . , βn0 ∈ F and coefficients λj ∈ B such that hj = λj βj for each i ∈ [m] and j ∈ [n0 ]. For every c = (c0 , . . . , cn0 ) ∈ C0 and i ∈ [m] we have X X (i) (i) (i) 0 = c0 · h0 + cj · hj = c0 · ζi + cj · λ j · β j . j∈[n0 ]
j∈[n0 ]
Therefore, − TrF/B (c0 · ζi ) =
X
(i)
λj · TrF/B (cj · βj ).
j∈[n0 ]
Thus, from a single query TrF/B (cj ·βj ) ∈ B for each cj , we can compute TrF/B (c0 · ζi ) for i ∈ [m]. Since {ζ1 , . . . , ζm } is a basis of F over B, the maps x 7→ TrF/B (c0 ·x) are linearly independent, so the values TrF/B (c0 · ζi ) determine c0 . ⊓ ⊔ 2.5
Linear Exact Repair Scheme via Subfield Subcodes
We recall the analysis of [AA26]. First, punctured dual codewords h(1) , . . . , h(m) ∈ D0 satisfying condition (5) are studied and then extended to the first coordinate so that they satisfy condition (4). For this, let β1 , . . . , βn0 ∈ F \ {0} be given, and consider punctured dual codewords whose j-th coordinates belong to the line generated by βj : D0 β := h = (h1 , . . . , hn0 ) ∈ D0 hj ∈ spanB (βj ), ∀j ∈ [n0 ] . 5
Note that D0 β is a B-linear code over the alphabet F. For every h ∈ D0 β , there exist λ1 , . . . , λn0 ∈ B such that hj = λj βj for j ∈ [n0 ]. Therefore, define n o Λβ := (λ1 , . . . , λn0 ) ∈ Bn0 ∃ h ∈ D0 β with hj = λj βj , ∀j ∈ [n0 ] , which is a B-linear code over B. More precisely, Λβ = D0 β Mβ −1 ∩ Bn0 , where ). Consider the extension map ϕD0 defined in (2). Mβ −1 = Diag(β1−1 , . . . , βn−1 0 Condition (4) requires the existence of m punctured dual codewords whose ϕD0 extensions are B-linearly independent. Consequently, a necessary condition is dimB (Λβ ) ≥ m. Using the dimension bound for subfield subcodes, we obtain dimB (Λβ ) ≥ n0 − mk0 . This bound suggests that the condition k0 ≤ n0 /m − 1 might be sufficient to guarantee the existence of a LERS. However, this dimension bound alone does not guarantee that the images of the corresponding ϕD0 -extensions have dimension m. Necessary and Sufficient Condition. Consider the B-linear map ψ:
. Λβ −→ F P (λ1 , . . . , λn0 ) 7−→ i∈[n0 ] ϕi βi λi
(6)
Then β1 , . . . , βn0 will give a LERS if dimB (Im(ψ)) = m. In the following, a matrix characterization of this condition is derived. A parity-check matrix of D0 is given by G0 from (1). Moreover, ϕ G0 is a parity-check matrix of D0 ∩ ker(ϕD0 ). For h ∈ D0 β , let h = λMβ , where Mβ = Diag(β1 , . . . , βn0 ) and λ ∈ Λβ . Since h ∈ D0 , we have 0 = G0 hT = G0 (λMβ )T = (G0 Mβ )λT . Consequently, a (not necessarily full-rank) paritycheck matrix of Λβ is given by (G0 Mβ )B ∈ Bm(k0 −1)×n0 . Similarly, ker(ψ) is the right kernel of the matrix (ϕMβ )B . Kβ = (G0 Mβ )B
(7)
Hence, the condition dimB (Im(ψ)) = m is equivalent to requiring that the rank of Kβ is exactly m larger than the rank of a parity-check matrix of Λβ , i.e., rankB (Kβ ) = rankB (G0 Mβ )B + m. (8) Therefore, any choice of β1 , . . . , βn0 satisfying (8) gives a linear exact repair scheme. 6
Randomized Method. The rank characterization reduces the construction of a LERS to finding β1 , . . . , βn0 ∈ F \ {0} satisfying (8). However, analyzing this rank is difficult, since it requires controlling the dimension of subfield subcodes, which is not known in general. For k0 ≤ n0 /m − 1, condition (8) is satisfied with overwhelming probability when β1 , . . . , βn0 are sampled independently and uniformly from F \ {0}. For the parameter choice q = 2 and m = 5, and for a variety of parameter pairs (n, k) (see [AA26]), the condition was satisfied in all 10 000 trials.
3
Analysis of Massey Scheme for the Addition
3.1
Setup for the Addition
Let C0 be a code with generator matrix G0 as in (1), and let H0 be a paritycheck matrix of C0 . Consider three secret values u, v, w ∈ F, which are masked by codewords cu , cv , cw ∈ C0 , respectively, such that cu,0 = u, cv,0 = v, and cw,0 = w. We focus on the addition operation w = u + v. The matrix 101 Gcomp = 011 captures the relation between the inputs u, v and the output w, with (u, v, w) = (u, v) · Gcomp . The code Ccomp generated by Gcomp is referred to as the computational code. Equivalently, it can be described by the parity-check matrix Hcomp = 1 1 −1 , which describes the addition. Since the addition is a linear operation, the associated codewords (maskings) satisfy cw = cu + cv . Therefore, 1 0 1 (cu , cv , cw ) = (cu , cv ) n0 +1 n0 +1 n0 +1 , 0n0 +1 1n0 +1 1n0 +1 where 1n0 +1 and 0n0 +1 denote the identity and zero matrices. The induced code C = (cu , cv , cw ) ∈ C03 ; cw = cu + cv , is a [3(n0 + 1), 2k0 ]F code with generator matrix G0 0 G0 G= . 0 G0 G0 Actually G can be expressed as the Kronecker product G = Gcomp ⊗ G0 , and C = Ccomp ⊗ C0 is the product code induced by Ccomp and C0 . The dual code of C, denoted by D, is a [3(n0 +1), 3(n0 +1)−2k0 ]F code. A redundant parity-check matrix for C (equivalently, a generator matrix of D) is given by H0 0 0 0 H0 0 . 0 0 H0 1n0 +1 1n0 +1 −1n0 +1 7
By removing redundant rows, we obtain a full-rank parity-check matrix H0 0 0 H0 0 , H= 0 1n0 +1 1n0 +1 −1n0 +1
(9)
whose rank is exactly 3(n0 + 1) − 2k0 . We write cu = (u, cu ) for cu ∈ Fn0 , and analogously for cv and cw . Similarly, a dual codeword h ∈ D is denoted by h = (hu , hv , hw ) = (hu,0 , hu ), (hv,0 , hv ), (hw,0 , hw ) . Thus, for c = (u, cu ), (v, cv ), (w, cw ) ∈ C and h ∈ D, we have hu,0 · u + hu · cu T + hv,0 · v + hv · cv T + hw,0 · w + hw · cw T = 0.
(10)
We abuse notation and write h = (hu , hv , hw ), where hu = (hu,1 , . . . , hu,n0 ), hv = (hv,1 , . . . , hv,n0 ), and hw = (hw,1 , . . . , hw,n0 ). Define the coordinate sets I0 = {0, n0 +1, 2n0 +2} and J = {0, . . . , 3(n0 +1)−1}\I0 . We write h = (hi )i∈J , where the coordinates are indexed by the coordinate set J obtained by puncturing at I0 . More precisely, letting J = Ju ⊔ Jv ⊔ Jw denote the corresponding partition of J, we also use the notation h = (hi )i∈Ju , (hi )i∈Jv , (hi )i∈Jw . 3.2
Repair Problem for the Addition
In this setting, the repair problem consists of recovering (u, v, w) from (cu , cv , cw ). The linear exact repair problem can be reformulated in terms of parity equations. We will show that the missing symbols can be recovered if there exists a matrix H2m consisting of 2m codewords h(1) , . . . , h(2m) ∈ D of the form (1) (1) (1) (1) (1) (1) hu,0 · · · hu,n0 hv,0 · · · hv,n0 hw,0 · · · hw,n0 h(1) (2) (2) (2) (2) (2) (2) h(2) hu,0 · · · hu,n0 hv,0 · · · hv,n0 hw,0 · · · hw,n0 H2m = . = . .. . .. . . . .. . . . , .. . .. . .. . .. .. . . (2m) (2m) (2m) (2m) (2m) (2m) h(2m) hu,0 · · · hu,n0 hv,0 · · · hv,n0 hw,0 · · · hw,n0
such that the matrix
(1) (1) (1) (1) hu,0 + hw,0 hv,0 + hw,0 .. .. A= . . (2m) (2m) (2m) (2m) hu,0 + hw,0 hv,0 + hw,0
(11)
rankB AB = 2m,
(12)
satisfies
8
where AB ∈ B2m×2m is obtained by expanding each entry of A as a row vector of its coordinates in B. In addition, for each j ∈ [n0 ], we require n o (1) (2m) = 1, dimB spanB hu,j , . . . , hu,j n o (1) (2m) = 1, dimB spanB hv,j , . . . , hv,j n o (1) (2m) = 1. dimB spanB hw,j , . . . , hw,j
(13) (14) (15)
Theorem 3. Let C be the [3(n0 +1), 2k0 ]F product code induced by C0 and Ccomp as described above. If there exists a matrix H2m satisfying (12) and (13)–(15), then there exists an equally distributed LERS for C. Proof. Let H2m be a matrix satisfying (12). Since rankB (AB ) = 2m, elementary B-linear row operations transform AB into 1m 0 , 0 1m where 1m denotes the m × m identity matrix. Thus, there exist dual codewords h(1) , . . . , h(2m) ∈ D such that (i)
(i)
hu,0 + hw,0 = ζi , 1 ≤ i ≤ m, (i) (i) hu,0 + hw,0 = 0, m + 1 ≤ i ≤ 2m, (i) (i) hv,0 + hw,0 = 0, 1 ≤ i ≤ m, (i) (i) hv,0 + hw,0 = ζi , m + 1 ≤ i ≤ 2m. Furthermore, for each i ∈ [2m], conditions (13)–(15) imply that, for every j ∈ (i) (i) (i) (i) [n0 ], there exist λu,j , λv,j , λw,j ∈ B and βu,j , βv,j , βw,j ∈ F such that hu,j = (i)
(i)
(i)
(i)
(i)
λu,j βu,j , hv,j = λv,j βv,j , and hw,j = λw,j βw,j . For each i ∈ [m], Eq (10) gives (i)
(i)
(i)
−cu,0 hu,0 − cv,0 hv,0 − cw,0 hw,0 =
n0 X (i) (i) (i) cu,j hu,j + cv,j hv,j + cw,j hw,j j=1
n0 X (i) (i) (i) (i) (i) (i) cu,j λu,j βu,j + cv,j λv,j βv,j −cu,0 hu,0 + hw,0 − cv,0 hv,0 + hw,0 = j=1
(i) + cw,j λw,j βw,j . Hence, −cu,0 ζi =
n0 X
(i) (i) (i) cu,j λu,j βu,j + cv,j λv,j βv,j + cw,j λw,j βw,j .
j=1
9
Applying the trace operator TrF/B to the preceding equation, we obtain − TrF/B (cu,0 ζi ) =
n0 X
(i)
λu,j TrF/B (cu,j βu,j )
j=1 n0 X
+
(i)
λv,j TrF/B (cv,j βv,j ) +
j=1
n0 X
(i)
λw,j TrF/B (cw,j βw,j ) .
j=1
Thus, after querying the 3n0 subsymbols TrF/B (cu,j βu,j ) ,
TrF/B (cv,j βv,j ) ,
TrF/B (cw,j βw,j ) ,
j ∈ [n0 ],
we can, by varying i ∈ [m] (and hence ζi ), compute the m linear functions TrF/B (cu,0 ζi ) for i ∈ [m]. Indeed, each of these values is determined by the (i)
(i)
(i)
queried subsymbols and the fixed, known coefficients λu,j , λv,j , λw,j ∈ B. Since {ζ1 , . . . , ζm } is a basis over B of F, these m linear functions determine cu,0 . Similarly, using the remaining dual codewords h(m+1) , . . . , h(2m) ∈ D, for i ∈ [m], we can determine the m trace values TrF/B (cv,0 ζi ) using the analog queries as above, which uniquely determine cv,0 . ⊓ ⊔ 3.3
Subfield Subcode Analysis
First, we construct a matrix H2m satisfying (13)–(15). Let D denote the puncturing of the dual code D at the coordinates in I0 , with coordinate set J. The following matrix is a generator matrix of C = Ccomp ⊗ C0 and, consequently, a parity-check matrix of D: −1 ϕ 0 0 −1 ϕ 0 G0 0 0 0 G0 G= 0 0 −1 ϕ −1 ϕ . 0 0 0 G0 0 G0 Moreover, G0 0 G0 G= , 0 G0 G0
(16)
is a generator matrix for C, where C is the dual code of the punctured code D. Puncturing the parity-check matrix of C at I0 yields 0 H0 0 0 H0 0 0 0 0 1n0 1n0 −1n0 and the dimension of the punctured code D is dimB (D) = 3(n0 + 1) − 2k0 − 1. For each j ∈ J, let βj ∈ F \ {0} be such that the j-th column of H2m is contained in spanB (βj ). Let Dβ be defined by Dβ := {h ∈ D | hj ∈ spanB (βj ) for all j ∈ J} , 10
which is a B-linear code of length 3n0 over the alphabet F. We define Λβ := λ ∈ B3n0 ∃ h ∈ Dβ such that hj = λj βj for all j ∈ J , which is a B-linear code of length 3n0 over the alphabet B. With the diagonal matrix Mβ −1 := Diag βj−1 j∈J ∈ F3n0 ×3n0 , we have, similarly to the base case, that Λβ = D · Mβ −1 ∩ B3n0 , is a subfield subcode. The redundancy of Dβ is r(Dβ ) = n(Dβ )−k(Dβ ) = 2k0 −2. Using the lower bound on the dimension dimB (Λβ ) ≥ n(Dβ ) − m · r(Dβ ), we obtain dimB (Λβ ) ≥ 3n0 − 2m(k0 − 1). To ensure that dimB (Λβ ) ≥ 2m, it suffices to have k0 ≤
3n0 . 2m
Hence, there exist 2m linearly independent elements of Λβ satisfying the conditions (13)–(15). Once we have h = (hu , hv , hw ) ∈ Dβ , we seek to extend h to codewords hu , hv , hw satisfying the full-rank condition (12). From 11, we are concerned with the values hu,0 + hw,0 and hv,0 + hw,0 . Definition 2 (Add extension map). Let G0 be a generator matrix as in (1), whose first row is (−1, ϕ). We define the add extension map ϕD by ϕD :
2 D −→ F
(17)
(hu , hv , hw ) 7−→ ϕ · hTu + ϕ · hTw , ϕ · hTv + ϕ · hTw . Applying this map to h ∈ Dβ , and writing hu,j = λu,j βu,j , hv,j = λv,j βv,j , hw,j = λw,j βw,j for j ∈ [n0 ] with λ ∈ Λβ , gives the B-linear map 2 ψΛβ : Λβ → FP Pn0 n0 λ 7→ ( j=1 ϕj λu,j βu,j + λw,j βw,j , j=1 ϕj λv,j βv,j + λw,j βw,j ). (18) It remains to ensure that (19) dimB Im(ψΛβ ) = 2m.
Previously, we have shown that k0 ≤ 3n0 /(2m) is sufficient to ensure that dimB (Λβ ) ≥ 2m. However, this does not imply that dimB Im(ψΛβ ) ≥ 2m. Let us first make the condition in (19) explicit. Recall that the matrix in (16) is a parity-check matrix for D. Define M3β = Diag Mu,β , Mv,β , Mw,β , where Mu,β = Diag (βj )j∈Ju , Mv,β = Diag (βj )j∈Jv , Mw,β = Diag (βj )j∈Jw . Since T 0 = G h T = G (λM3β ) = GM3β λ T , 11
a (not necessarily full-rank) parity-check matrix for Λβ is given, after expanding the columns over B, by (G0 Mu,β )B 0 (G0 Mw,β )B (20) HΛβ = ∈ Bm·2(k0 −1)×3n0 0 (G0 Mv,β )B (G0 Mw,β )B and the matrix
(ϕMu,β )B 0 (ϕMw,β )B (G0 Mu,β )B 0 (G0 Mw,β )B HΛ0 β = 0 (ϕMv,β )B (ϕMw,β )B 0 (G0 Mv,β )B (G0 Mw,β )B is a parity-check matrix for ker(ψΛβ ). Consequently, dimB (Λβ ) = 3n0 − rankB HΛβ .
(21)
(22)
Furthermore, the rank-nullity theorem implies dimB (ker(ψΛβ )) = 3n0 − rankB HΛ0 β . By (22) and (23), the condition dimB Im(ψΛβ ) = 2m is equivalent to rankB HΛ0 β − rankB HΛβ = 2m.
(23)
(24)
Thus, any choice of βj ∈ F\{0}, j ∈ J, satisfying (24) gives a linear exact repair scheme. Again, a theoretical analysis of condition (24) is not known. We therefore resort to a random search. 3.4
Simulations
We implemented the randomized method in MAGMA and performed simulations for various parameter choices. The results for fixed q = 2 and m = 5 are shown in Figure 1 for both Reed–Solomon codes and randomly generated codes. Following the randomized method, for each pair (n0 , k0 ), 106 independent trials were performed. In each trial, the elements βu,j , βv,j , βw,j ∈ F \ {0} are chosen independently and uniformly at random. Then the matrices in (20) and (21) are constructed, and it is verified whether the rank condition (24) holds. As expected, this condition is satisfied with high probability when k0 ≤ 3k0 /(2m) is met (highlighted in green). This demonstrates that the upper bound for k0 allows leakage for more Massey secret sharing schemes. In other words, the secrets of the corresponding Massey secret sharing schemes for the addition are vulnerable to leakage. Furthermore, note that the success probability of finding suitable β values increases as k0 decreases. For comparison, the yellow line in the figures represents the upper bound of the construction of [AA26]. The gap between these two bounds illustrates the improvement achieved by our construction. 12
Parameters: q=2, m=5
11
100
Reed-Solomon Code Random Code
10
80
Percentage of success
9 8 7
60
5
40
k 6 4 3
20
2 10
11
12
13
14
15
16
17
18
19
20
21
n
22
23
24
25
26
27
28
29
30
31
32
0
Fig. 1. Percentage of success for the addition (based on 106 trials for each pair (n0 , k0 )) for q = 2 and m = 5. Here, success means that (24) holds. The upper bound k0 ≤ 3n0 /2m is indicated in green, while the bound for the base case is indicated in yellow.
4
Generalization to Linear Computations
4.1
Masking of General Linear Computations
The computation proceeds as follows. Given F-linearly independent input values u1 , . . . , uK ∈ F and intermediate or output values w1 , . . . , wN −K ∈ F, the computation of the values w1 , . . . , wN −K from the inputs u1 , . . . , uK can be described by a matrix Hcomp ∈ F(N −K)×N of the form u
···
u
w
···
w
··· w
1 1 i K N −K g1,1 · · · g1,K −1 ··· 0 ··· 0 .. .. .. .. .. .. . . . . . . gi gi,K+1 · · · −1 ··· 0 . gi,1 · · · gi,K Hcomp = gi+1 gi+1,1 · · · gi+1,K gi+1,K+1 · · · gi+1,K+i · · · 0 .. .. .. .. .. .. . . . . . . gN −K gN −K,1 · · · gN −K,K gN −K,K+1 · · · gN −K,K+i · · · −1
g1
Each row gi describes a step of a linear operation, that expresses the value wi as a linear combination of the input values and the previously computed intermediate values. We define the associated [N, K]F code by Ccomp = {c ∈ FN : Hcomp · cT = 0}, which we again call the computation code. Let Gcomp be the systematic generating matrix of Ccomp , whose first K columns form the identity matrix. Then (u1 , . . . , uK , w1 , . . . , wN −K ) = (u1 , . . . , uK ) · Gcomp . 13
Masking is done using the base code C0 , such that each ui (respectively wi ) has an associated cui ∈ C0 (respectively cwi ∈ C0 ). Then, each computation is applied in parallel to each coordinate of the cui ’s and the cwi ’s i.e., at step gi , we have cwi = gi,1 cu1 + · · · + gi,K cuK + gi,K+1 cw1 + · · · + gi,K+i−1 cwi−1 . Then the codeword c = (cu1 , . . . , cuK , cw1 , . . . , cwN −K ) belongs to the [N (n0 + 1), Kk0 ]F product code C = Ccomp ⊗ C0 . For simplicity, we index c as follows c = (cu1 , . . . , cuK , cw1 , . . . , cwN −K ) = (c1 , . . . , cN ), where ci ∈ C0 . We denote the j-th coordinate of ci by ci,j , so that ci = (ci,0 , . . . , ci,n0 ). Furthermore, masking is such that (c1,0 , . . . , cK,0 , cK+1,0 , . . . , cN,0 ) = (u1 , . . . , uK , w1 , . . . , wN −K ). The dual code of C, denoted by D, is a [N (n0 +1), N (n0 +1)−Kk0 ]F code. Using the above indexing, we also denote a dual codeword by h = (h1 , . . . , hN ) ∈ C ⊥ . When puncturing D at the set I0 = {0, n0 + 1, . . . , (K − 1)(n0 + 1)}, we again abuse the underline notation and write h = (h1 , . . . , hN ), where hi = (hi,1 , . . . , hi,n0 ) ∈ Fn0 for i ∈ [N ] is the puncturing of hi at position 0. Whenever convenient, we write h = (hi )i∈J , with J = [N (n0 +1)−1]0 \I0 . Let J = J1 ⊔ . . . ⊔ JN be the corresponding partition of J, we also use the notation h = (hi )i∈J1 , . . . , (hi )i∈JN . Example: Summation of an Array. Let (u1 , . . . , uK ) ∈ FK be an array of input values. Using registers ru , rw ∈ F, the computation of u1 + · · · + uK can be implemented by initializing rw = 0 and, for each i ∈ [K], performing the operations ru ← ui (memory load) and rw ← rw + ru (addition). We consider leakage from the successive values of ru (the ui ’s) and the successive values of rw (the partial sums, denoted by wi ). The associated computation code for K = 4 has parity-check matrix Hcomp and generator matrix Gcomp as follows: u1 u2 u3 u4 w1 w2 w3 w4 1 0 0 0 −1 0 0 0 0 1 0 0 1 −1 0 0 Hcomp = 0 0 1 0 0 1 −1 0 , 0 0 0 1 0 0 1 −1
u1 u2 u3 u4 w1 w2 w3 w4 1 0 0 0 1 1 1 1 0 1 0 0 0 1 1 1 Gcomp = 0 0 1 0 0 0 1 1 . 0 0 0 1 0 0 0 1
Thus, the full vector that is leaked is (u1 , u2 , u3 , u4 , w1 , w2 , w3 , w4 ) ∈ F8 , where (u1 , u2 , u3 , u4 , w1 , w2 , w3 , w4 ) = (u1 , u2 , u3 , u4 ) · Gcomp . When masking is applied and the computation is performed in parallel on the shares, we obtain cw1 = cu1 and cwi = cwi−1 +cui . The associated [8(n0 +1), 4k0 ]F product code is C = Ccomp ⊗ C0 . 14
Example: Linear Feedback Shift Register. Let s ∈ F be a secret and let α ∈ F be a fixed constant. A register rw is initialized with rw = s and updated by rw = αrw for i = 1, . . . , N − 1. Let w0 = s, w1 , . . . , wN −1 be the successive values of the register rw . The associated [N, 1]F computation code for N = 5 has the following parity-check and generator matrices s w
w
w
w
1 2 3 4 α −1 0 · · · 0 . 0 α −1 . . . .. , Hcomp = . . . . .. . . . . . . 0 0 · · · 0 α −1
Gcomp =
s w1 w22 w3 wS4 1 α α ··· α .
Given a base code C0 , the induced [N n0 , k0 ]F product code C = Ccomp ⊗ C0 has codewords cwi such that cw0 = cs and cwi = αcwi−1 , i = 1, . . . , N − 1. 4.2
Repair Problem for General Linear Computations
For a codeword c = (c1 , . . . , cN ) ∈ C, the repair problem is to recover the independent input values c1,0 , . . . , cK,0 . In the context of secret sharing, this corresponds to recovering secret data. In this setting, we need to find dual codewords with suitable properties. Namely, we look for a matrix HKm ∈ FKm×N (n0 +1) consisting of Km dual codewords h(1) , . . . , h(Km) ∈ D: (1) h (1) (1) (1) (1) · · · h · · · h h · · · h 1,0 1,n N,0 N,n (2) 0 0 h .. .. .. .. HKm = . = . . . . . .. (Km) (Km) (Km) (Km) h1,0 · · · h1,n0 · · · hN,0 · · · hN,n0 h(Km) We first give the full-rank condition. The matrix AHkm ∈ FKm×K defined by (1) (1) (1) h1,0 h2,0 · · · hN,0 . .. .. T (25) AHkm = . . · Gcomp .. (Km) (Km) (Km) h1,0 h2,0 · · · hN,0 must satisfy (after row expansion): rankB(ABHkm ) = K · m.
(26)
The second condition (one dimension columns) is, for each pair (i, j) ∈ [N ]×[n0 ]: (1) (K·m) dimB spanB hi,j , . . . , hi,j = 1. (27) Theorem 4. Let C = Ccomp ⊗ C0 be the product code of C0 and Ccomp as above. Then the existence of a matrix HKm that satisfies (26) and (27) implies the existence of an equally distributed LERS for C. 15
Proof. For c ∈ C and h = (h1 , . . . , hN ) ∈ D, it holds that N X cj,0 hj,0 + cj hTj = 0. j=1
With (c1,0 , . . . , cN,0 ) = (c1,0 , . . . , cK,0 ) · Gcomp , we obtain N X
T
cj,0 hj,0 = (c1,0 , . . . , cN,0 ) · (h1,0 , . . . , hN,0 )
j=1 T
= (c1,0 , . . . , cK,0 ) · Gcomp · (h1,0 , . . . , hN,0 )
= (c1,0 , . . . , cK,0 ) · (h1,0 , . . . , hN,0 ) · GTcomp
T
.
From condition (26), the matrix ABHKm can be reduced with B-linear row operations to 1Km×Km , i.e. AHKm can be reduced to u1 ... uK
ζ1 .. . ζm . .. .. . . .. . ζ1 .. .
ζm (i)
(i)
Thus, for a given j0 ∈ [K] and i ∈ [m], there is h(i) = (h1 , . . . , hN ) ∈ D such that j0 -th block
z
}|
{
(i) (i) (h1,0 , . . . , hN,0 ) · GTcomp = (01×m , . . . , 01×m , 0, . . . , ζi , . . . , 0, . . . , 01×m ).
Hence, T (i) (i) = cj0 ,0 ζi . (c1,0 , . . . , cK,0 ) · (h1,0 , . . . , hN,0 )GTcomp (i)
From (27), for i ∈ [m], and (j, ℓ) ∈ [N ] × [n0 ], there exists βj,ℓ ∈ F and λj,ℓ ∈ B (i)
(i)
such that hj,ℓ = λj,ℓ βj,ℓ . Using this decomposition and applying the trace gives −cj0 ,0 ζi =
n0 N X X
(i)
cj,ℓ λj,ℓ βj,ℓ ,
j=1 ℓ=1
− TrF/B (cj0 ,0 ζi ) =
n0 N X X j=1 ℓ=1
16
(i)
λj,ℓ TrF/B (cj,ℓ βj,ℓ ).
The N × n0 leakage functions cj,ℓ 7→ TrF/B (cj,ℓ βj,ℓ ) are independent of i. Varying i, the m values TrF/B (cj0 ,0 ζi ) can be determined as linear combinations of (i)
these leakage functions, with coefficients λj,ℓ . Since (ζ1 , . . . , ζm ) is a basis of F, these m values determine cj0 ,0 . ⊔ ⊓ 4.3
Subfield Subcode Analysis
We again study how to construct a matrix HKm that satisfies the full-rank condition (26) and the one-dimensional column-span conditions (27). Due to Theorem 4, it will give an equally distributed LERS for the product code C. We first focus on one-dimensional column-span conditions (27). We use the same approach as in the previous section. Analogously to the add case, consider the puncturing of the dual code D at the set of coordinates I0 , and denote it D. Given the generator matrix G0 of C0 as in (1), we obtain the following generator matrix for the product code C: −1 ϕ G = Gcomp ⊗ G0 = Gcomp ⊗ , 0 G0 which is a parity-check matrix of D. One can see that the parity-check matrix of the punctured code D is given by G = Gcomp ⊗ G0 . Furthermore, we have that the dimension of the punctured code D is dimF (D) = N n0 − K(k0 − 1).
(28)
The proof of (28) can be found in Appendix A. We start by analyzing which punctured dual codewords h(1) , . . . , h(Km) ∈ D satisfy the one-dimensional columnspan conditions (27). For each j ∈ J, let βj ∈ F be non-zero such that the j-th column of HKm is contained in the B-span of βj . Consider Dβ := {h ∈ D : hj ∈ spanB (βj ) for all j ∈ J} , which is a B-linear code of length N n0 over the alphabet F. Since βj ̸= 0 for all j ∈ J, there exists for each codeword h ∈ Dβ a unique vector λ ∈ BN n0 such that hj = λj βj , for all j ∈ J. This observation motivates the definition n o Λβ := λ ∈ BN n0 ∃ h ∈ Dβ such that hj = βj λj for all j ∈ J . Then Λβ ⊆ BN n0 is a B-linear code over the alphabet B. Let the diagonal matrix of size N n0 × N n0 be given by Mβ −1 := Diag(βj−1 )j∈J . We can write Dβ = Λβ Mβ . Then Λβ is a subfield subcode of Dβ Mβ −1 (see the proof in Appendix B). To prove the existence of punctured dual codewords in D satisfying the one-dimensional constraints described in (27), it suffices to show that the subfield subcode Λβ has dimension at least Km. We obtain a lower bound 17
on its dimension by applying the bound for subfield subcodes: dimB (Λβ ) ≥ n(Dβ ) − m r(Dβ ) = N n0 − mK(k0 − 1), where we used (28). In particular, a sufficient condition for dimB (Λβ ) ≥ Km is k0 ≤
N n0 . Km
(29)
Hence, if the upper bound (29) for the dimension is satisfied, then there exist punctured dual codewords in D satisfying conditions (27). Fulfilling the Full-Rank Condition. Given h = (h1 , . . . , hN ) ∈ Dβ ⊆ D, we now address the full-rank condition (26). In particular, for ϕ in G0 as in (1), we require the following K values (ϕ · (hT1 , . . . , hTN )) ⊗ Gcomp [1, ·], .. . (ϕ · (hT1 , . . . , hTN )) ⊗ Gcomp [K, ·] to be linearly independent, where Gcomp [i, ·] denotes the ith row of Gcomp . Definition 3 (Generalized extension map). For the dual D of the product code Ccomp ⊗ C0 , we define the associated extension map as ϕD :
K D −→ F
(h1 , . . . , hN ) 7−→ (ϕ · (hT1 , . . . , hTN )) ⊗ Gcomp [i, ·]
. i∈[K]
Applying this map to h ∈ Dβ , and writing, for j ∈ [n0 ], h1,j = λ1,j β1,j , . . . , hN,j = λN,j βN,j , with λ = (λ1 , . . . , λN ) ∈ Λβ , leads to the following B-linear map K ψΛβ : Λβ −→ F
T λ 7−→ (ϕ · (λT1 ⊙ β1T , . . . , λTN ⊙ βN )) ⊗ Gcomp [i, ·]
i∈[K]
where the ⊙-operation denotes the componentwise multiplication. If dimB (Im(ψΛβ )) = Km, then there exist h(1) , . . . , h(Km) ∈ Λβ such that their images under ψΛβ form a basis of FK over B. This requires dimB (Λβ ) ≥ Km, which is ensured by con dition (29). However, this does not imply that dimB Im(ψΛβ ) = Km. Again, determining this dimension amounts to computing the dimension of a subfield subcode, which is difficult in general. We therefore only state a rank criterion. Let Mi,β = Diag (βj )j∈Ji for i ∈ [N ]. Then dimB Im(ψΛβ ) = Km is equivalent to rankB HΛ0 β − rankB HΛβ = Km, (30) 18
where HΛβ = (Gcomp ⊗ G0 ) Diag(M1,β , . . . , MN,β ) B ∈ BmK(k0 −1)×N n0 is a parity-check matrix for Λβ , and ϕ 0 Gcomp ⊗ HΛβ = Diag(M1,β , . . . , MN,β ) G0 B is a parity-check matrix for ker(ψΛβ ). Criterion (30) allows to verify that the vectors βi , . . . , βN ∈ FN ×n0 provide dual codewords in D satisfying (26). 4.4
Numerical Examples
Example: Summation of an Array. Recall the summation of an array from Example 4.1. Then, the base code C0 can have dimension at most k0 ≤ 2n0 /m. Example: Linear Feedback Shift Register. Using the parameters from Example 4.1, the upper bound on the dimension k0 of the base code yields k0 ≤ N · n0 /m. With N = m, we can have k0 = n0 . We explain this as follows. For a general code, let s = c0 denote the secret, and let c1 , . . . , cn0 be the shares of c0 . Consider using the same leakage map for every share: x 7−→ TrF/B (x). For each j ∈ [n0 ], the leakage of cj after m − 1 iterations is TrF/B (cj ), TrF/B (αcj ) . . . , TrF/B (αm−1 cj ). If α is chosen as generator of F, then these trace values uniquely determine cj . Hence every share cj can be recovered, and consequently c0 = s. We remark that this argument applies to additive secret sharing, where the shares sum up to the secret s.
5
Use of Identical Leakage Functions
In general, there are N sets of βj ’s defining the leakage functions TrF/B (βj · cj ): for each i ∈ [N ], the j-th symbol of ci is associated with βi,j . Our randomized method found, with overwhelming probability, values β1,j , . . . , βN,j satisfying (30), thereby yielding a linear repair scheme. Recall, however, that these values are chosen independently and uniformly at random. A more realistic attack model requires the leakage functions to coincide across all i ∈ [N ], i.e., β1,j = . . . = βN,j = βj for j ∈ [n0 ]. Imposing this restriction on the simple addition computation (introduced in 3), i.e., setting βu,j = βv,j = βw,j = βj for all j ∈ [n0 ], our simulations never found a set of βj ’s satisfying (24) under the improved dimension bound. This outcome can be explained as follows. Suppose, for contradiction, that (24) holds when βu,j = βv,j = βw,j for all j ∈ [n0 ]. Then the matrix in (21) has B-rank 2m greater than that of the matrix in (20); explicitly, (ϕMu,β )B 0 (ϕMw,β )B (G0 Mu,β )B 0 (G0 Mw,β )B has B-rank m greater than that of (G0 Mu,β )B 0 (G0 Mw,β )B . 19
Since Mu,β = Mw,β = Mβ , it follows that (ϕMβ )B (G0 Mβ )B has B-rank m greater than that of (G0 Mβ )B . This is precisely the rank condition (8) required for the base code C0 . Hence, any repair scheme for the product code C that uses identical leakage functions induces a repair scheme for C0 itself; consequently, no improvement over the base code is possible, and the upper bound on k0 cannot be improved by exploiting the additive relation alone. The same argument applies to the Guruswami–Wootters [GW16] algebraic LERS for Reed–Solomon codes: under the simple addition, any scheme using identical βj ’s for all three codewords reduces to a LERS for the base Reed– Solomon code. In cryptographic terms, for Shamir secret sharing, this means that exploiting the simple additive relation requires leakage functions other than those of [GW16], if such functions exist. This observation also seems to extend directly to the array summation example 4.1. However, for the linear relation µu u + µv v = w with µu ̸= µv ∈ F \ {0, 1}, our simulation finds, with overwhelming probability, a set of βj ’s satisfying (30) under the improved dimension bound. It seems that the same holds for the sum µ1 u1 + · · · + µK uK for K coefficients µi ∈ F \ {0, 1}. Finally, also for the LFSR example 4.1, identical leakage functions can be reused at every step of the computation.
6
Conclusion
Our main contribution is the construction of leakage functions, based on linear exact repair schemes, for Massey secret sharing schemes when linear computations are performed. More precisely, we consider the product code C = Ccomp ⊗ C0 , where the [n0 , k0 ]F base code C0 induces the underlying Massey secret sharing scheme, and the [N, K]F computation code Ccomp represents linear computations among the N secrets, of which K are linearly independent (the inputs). Our construction yields leakage functions for C with high probability whenever k0 ≤ N n0 /(Km), which improves the upper bound k0 ≤ n0 /m − 1 of the base case of [AA26]. It is somewhat intriguing that the (standard share-wise) addition, which has strong security properties (Strong Non-Interfering, SNI, [Bar+16]) in the probing model, presents a weakness in the LERS-based leakage model. We also point out that, in cryptography, our results do not hold when the shares are refreshed, since any redundancy introduced by the computation code is then lost. Moreover, while identical leakage functions cannot exploit simple addition, they can exploit more general linear relations, yielding a more realistic leakage attack and potentially leading to a security weakness of Massey secret sharing schemes. Future work includes investigating multiplication. Such an analysis would rely on the Schur product of codes [Cas+09]. 20
References [AA26]
Nadja Aoutouf and Daniel Augot. “A Subfield Subcode Construction of a Linear Exact Repair Scheme”. In: Workshop on Coding and Cryptography (WCC 2026). 2026. url: https://wcc2026.inria. fr/assets/final_versions/WCC2026_paper_33.pdf. [AK96] R. Anderson and M. Kuhn. Tamper Resistance - a Cautionary Note. USENIX, 1996, pp. 1–11. [Bar+16] Gilles Barthe et al. “Strong Non-Interference and Type-Directed Higher-Order Masking”. In: ACM CCS 2016. Ed. by Edgar R. Weippl et al. ACM Press, Oct. 2016, pp. 116–129. doi: 10.1145/2976749. 2978427. [Ben+18] Fabrice Benhamouda et al. “On the Local Leakage Resilience of Linear Secret Sharing Schemes”. In: CRYPTO 2018, Part I. Ed. by Hovav Shacham and Alexandra Boldyreva. Vol. 10991. LNCS. Springer, Cham, Aug. 2018, pp. 531–561. doi: 10.1007/978-3-319-968841_18. [BPR22] Dan Boneh, Aditi Partap, and Lior Rotem. “Accountable Threshold Signatures with Proactive Refresh”. In: IACR Cryptol. ePrint Arch. 2022 (2022), p. 1656. url: https://eprint.iacr.org/2022/1656. [Cas+09] Ignacio Cascudo et al. “Asymptotically Good Ideal Linear Secret Sharing with Strong Multiplication over Any Fixed Finite Field”. In: CRYPTO 2009. Ed. by Shai Halevi. Vol. 5677. LNCS. Springer, Berlin, Heidelberg, Aug. 2009, pp. 466–486. doi: 10.1007/978-3642-03356-8_28. [Dor+26] Dean Doron et al. Discrepancy for Random Linear Codes. 2026. arXiv: 2606.24471 [cs.IT]. url: https://arxiv.org/abs/2606. 24471. [GW16] Venkatesan Guruswami and Mary Wootters. “Repairing Reed-solomon codes”. In: 48th ACM STOC. Ed. by Daniel Wichs and Yishay Mansour. ACM Press, June 2016, pp. 216–226. doi: 10.1145/2897518. 2897525. [Kas24] Dustin Kasser. “An Improvement Upon the Bounds for the Local Leakage Resilience of Shamir’s Secret Sharing Scheme”. In: TCC 2024, Part IV. Ed. by Elette Boyle and Mohammad Mahmoody. Vol. 15367. LNCS. Springer, Cham, Dec. 2024, pp. 395–422. doi: 10.1007/9783-031-78023-3_13. [Mas93] J.L Massey. “Some Applications of Coding Theory in Cryptography”. In: Codes and Cyphers: Cryptography and Coding IV. Ed. by P.G.) Farrell. 1993, pp. 33–47. [Ngu25] Hai H. Nguyen. “Physical-Bit Leakage Resilience of Linear CodeBased Secret Sharing”. In: EUROCRYPT 2025, Part VIII. Ed. by Serge Fehr and Pierre-Alain Fouque. Vol. 15608. LNCS. Springer, Cham, May 2025, pp. 64–93. doi: 10.1007/978-3-031-91101-9_3. [Roz25] Wouter Rozendaal. “Study of Quantum LDPC Codes and their Decoding”. Theses. Université de Bordeaux, Dec. 2025. doi: 10.70675/ 21
f66f43cez8153z479czbfb6z0657c45fd040. url: https://theses. hal.science/tel-05493654.
A
Proof of Eq. 28
A.1
Matrix-based Proof
A redundant parity-check matrix of C (equivalently, a generator matrix of D) is given by # " 1N ⊗ H0 , Hcomp ⊗ 1n0 +1 which contains (2N − K)(n0 + 1) − N k0 rows and N (n0 + 1) columns. Since the submatrix formed by the last N − K columns of Hcomp is lower triangular, redundant rows can be removed, such that we obtain the following equivalent full row rank parity-check matrix: 1K H0 0K×(N −K) ⋆ 0 ··· 0 .. . . . . .. , . . H= . . ⋆ .. . . . 0 . ⋆ ··· ··· ⋆ which contains only N (n0 +1)−Kk0 rows. Finally, puncturing H on all positions in I0 gives 1K 0K×(N −K) 0(N −K)×K 0(N −K)×(N −K) ⋆ 0 ··· 0 .. . . . . .. , . . . . ⋆ .. .. . 0 . ⋆ ··· ··· ⋆ which contains (N − K) zero rows. Removing these redundant rows yields the parity-check matrix H, which contains N n0 − K(k0 − 1) rows. Consequently, the dimension of the punctured code D is dimF (D) = N n0 − K(k0 − 1).
(31)
Thus, puncturing the code at the positions I0 reduces its dimension by N − K. Furthermore, this observation is consistent with the behavior of the addition. A.2
Proof via the Abstract Duals of a Tensor Product Code
The dual of the tensor-product code Ccomp ⊗ C0 is given by ⊥ D = Ccomp ⊗ Fn0 +1 + FN ⊗ C0⊥ .
22
A proof can be found in [Roz25, Lemma 4.1.2]. Note that this is not a direct sum. Hence, we can recover the dimension with ⊥ ⊥ dimF (D) = dimF Ccomp ⊗ Fn0 +1 + dimF FN ⊗ C0⊥ − dimF Ccomp ⊗ C0⊥ = (n0 + 1)(N − K) + (n0 + 1 − k0 )N − (n0 + 1 − k0 )(N − K) = (n0 + 1)N − k0 K. Puncturing at the positions in I0 gives ⊥ D = Ccomp ⊗ Fn0 +1 + FN ⊗ C0⊥ . Again, the sum is not direct. Therefore, ⊥ ⊥ dimF (D) = dimF Ccomp ⊗ Fn0 + dimF FN ⊗ C0⊥ − dimF Ccomp ⊗ C0⊥ = n0 (N − K) + (n0 + 1 − k0 )N − (n0 + 1 − k0 )(N − K) = n0 N − k0 K + K.
B
Proof of Subfield Subcode Property
Lemma 1. The code Λβ is the B-subfield subcode of Dβ Mβ −1 , i.e., Λβ = Dβ Mβ −1 ∩ BN n0 . Proof. Observe that Dβ ⊆ FN n0 is F-linear, whereas Λβ ⊆ BN n0 is B-linear. Let λ ∈ Λβ ; then there exists h ∈ Dβ such that hj = λj βj for all j ∈ J. Since βj ̸= 0 −1 for all j ∈ J, the diagonal matrix Mβ −1 = Diag(β1−1 , . . . , βN ) is well-defined and invertible. Hence, for each i ∈ [N ], hi,1 hi,n0 = hi · Diag(βi−1 ), λi = (λi,1 , . . . , λi,n0 ) = ,..., βi,1 βi,n0 where hi is viewed as a row vector, and right multiplication by Diag(βi−1 ) cor−1 responds to componentwise multiplication by the scalars βi,j . Therefore, λ = h · Mβ −1 ∈ Dβ Mβ −1 , which implies λ ∈ Dβ Mβ −1 ∩ BN n0 . For the reverse inclusion, let g ∈ Dβ Mβ −1 ∩ BN n0 . Then there exists h ∈ Dβ such that g = (h1 , . . . , hN ) Mβ −1 , and hence −1 g = (h1 , . . . , hN ) Diag(β1−1 , . . . , βN ) = (λ1 , . . . , λN ) ∈ Λβ .
We conclude that Λβ is precisely the B-subfield subcode of the F-linear code Dβ Mβ −1 . ⊓ ⊔
23