CS Paper Radar

On the Leakage of Massey Secret Sharing Schemes under Linear Computations

Nadja Aoutouf, Daniel Augot

cs.CR ·submitted 2026-09-17 09:08 UTC · v1
hot direction

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 $\le$ 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 F\_{q^m} with k $\le$ N n/(Km), and supports arbitrary linear computations, whereas the previous subfield subcode construction only applies to k $\le$ 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.

Closest papers

Nearest neighbours by meaning across the whole index.

Systematic Derivation of Leakage in Massey Secret Sharing Schemes

cs.CR ·2026-11-02 ·Nadja Aoutouf, Daniel Augot
similarity 0.90
Abstract

Leakage attacks on secret sharing schemes can be based on the exploitation of partial information about individual shares to recover the underlying secret. In coding theory, linear exact repair schemes (LERSs) allow the recovery of a codeword symbol from limited information obtained from the remaining symbols. When applied to code-based secret sharing schemes, such repair schemes can be interpreted as recovering the secret from partial information about the shares, expressed in terms of subfield symbols. Guruswami and Wootters introduced the first explicit constructions of LERSs for low-rate Reed--Solomon codes that is optimal in terms of bandwidth. In this work, we first investigate the construction and algebraic properties of LERSs, building on the Guruswami-Wootters construction. We derive new explicit repair schemes from their construction and establish structural properties of the resulting schemes. Second, we further develop a systematic computational approach based on a Gr{ö}bner bases approach to identify leakage functions associated with LERSs for arbitrary linear codes. This approach enables us to investigate the existence and structural properties of LERSs across different code families and parameter ranges. We first applied our method to Reed-Solomon codes, which gave as further insights into the algebraic structure of LERSs. Moreover, by applying our method to generalized Reed-Muller and Tamo-Barg codes, we identify several LERSs that, to the best of our knowledge, have not previously been described in the literature.

0.03

SEC: One-Share Everywhere-Short Secret Sharing from Lossless Expanders

cs.CR cs.IT ·2026-11-12 ·Muhammad Arzaki, Muhammed F. Esgin, Amin Sakzad, Ron Steinfeld
theory similarity 0.70
Abstract · 84 pages, 3 figures. Also available as Cryptology ePrint Archive, Paper 2026/2841: https://eprint.iacr.org/2026/2841

We introduce SEC, an expander-code-based ramp secret sharing scheme over $\mathbb{Z}$-modules, particularly suitable for lattice-based distributed cryptography. It is everywhere-short: bounded secret coefficients yield bounded share coefficients, and the integer reconstruction vectors have bounded entries. Moreover, each participant receives exactly one share, regardless of the number of parties and the privacy and reconstruction thresholds. This improves on prior schemes with bounded share coefficients and bounded entries in the integer reconstruction vectors, in which the number of sub-shares or shares per participant grows either with the number of parties and the threshold or with the security parameter. The construction rests on a coding-theoretic observation: in the bi-adjacency matrix of a lossless bipartite expander, unique-neighbor peeling completes every sufficiently small set of columns to a square unimodular submatrix. We prove correctness, everywhere-shortness, and linearity, and give a publicly computable entrywise bound on the reconstruction vector our algorithm returns for each authorized set. For privacy, we introduce hard-core local leakage resilience, which strengthens the leakage-resilience notion of Nielsen and Simkin (EUROCRYPT 2020) to protect a hard-core function of the secret, and we prove that SEC satisfies it against correlated multi-query local leakage under the MatrixHint-MLWE problem, which admits a reduction from the standard MLWE problem. For $n=60$ participants and security parameter $κ=128$, SEC achieves privacy threshold 6 against $2^{64}$ leakage queries and empirical reconstruction threshold 46. The ideal entropy-coded secret and share sizes are about 3.5 KiB and 6.4 KiB, respectively.

0.31

Construction of Ternary Minimal Linear Codes with Dimension $n+r$ Via Index Codes and The Access Structures of Their Dual Codes

cs.IT ·2026-11-18 ·Haibo Liu, Qunying Liao
similarity 0.69
Abstract

Recently, minimal linear codes have been extensively studied due to their applications in secret sharing schemes, secure two-party computations, and so on. Constructing minimal linear codes violating the Ashikhmin-Barg condition and then determining their weight distributions have been interesting in coding theory and cryptography. In this paper, we present a general construction of ternary linear codes of dimension $n+r$, where $n$ and $r$ are positive integers, and derive a necessary and sufficient condition for the resulting codes to be minimal. We first specialize the construction using index codes arising from spreads, with three classes of index codes satisfying the minimality condition, we obtain the parameters and weight enumerators of the corresponding minimal codes, and determine the access structures type of the secret-sharing schemes based on their dual codes. By the index codes from Krawtchouk polynomials, we then give a second specialization of the construction, with a class of index codes satisfying the minimality condition, we obtain the parameters of the resulting minimal codes, and determine the access-structure type of the secret-sharing scheme based on each dual code. Several constructed families of minimal codes violate the Ashikhmin-Barg condition.

0.17

Leakage-Resilient Computation via Matrix Refreshing

cs.CR ·2026-11-03 ·Stefan Dziembowski, Sebastian Faust
theory similarity 0.67
Abstract

Leakage-resilient cryptography protects secrets against side-channel attacks, in which a physical implementation reveals partial information about its internal state. A fundamental primitive in this area is a leakage-resilient storage, which allows a secret to be stored in a way that remains secure even if an adversary learns some information about the storage's internal state. A popular approach represents a secret as the inner product of two $n$-bit vectors, called shares. The shares are stored and processed separately by two parts of the implementation, called the left and right parties. Because leakage accumulates over time, the shares must be refreshed repeatedly. We prove that a simple refresh, in which the left party multiplies its share by a uniform invertible matrix $M$ and the right party multiplies its share by $M^{-1}$, is secure under continual local leakage. After $T$ refreshes, each allowing at most $λ$ bits of leakage per party, the transcripts for two stored secrets are at statistical distance at most $C\cdot T\cdot 2^{6λ-n/9}$ for an absolute constant $C$. We also obtain a Boolean-circuit compiler with statistical privacy error at most $C\cdot S\cdot 2^{18λ-n/27}$ for $S$ operations and at most $λ$ bits of local leakage per party per operation. The guarantee covers repeated stateful evaluations with adaptively chosen public inputs, with $S$ counting all operations across invocations. Thus, for polynomial-size circuits, a constant leakage fraction is tolerated with share length depending only on the security parameter. We formalize the refreshing bound, the composition and compiler guarantees, and the expected-work bounds in Lean 4. Our results also provide efficient simulation: the leakage can be reproduced from the public inputs and the circuit outputs alone, with expected polynomial overhead.

0.20

Big Secrets Small Shares: Revisiting Secure Multi-Party Computation

cs.CR cs.IT ·2026-10-20 ·Wilton Kim, Van Long Phuoc Pham, Stanislav Kruglik, Han Mao Kiah
similarity 0.65
Abstract

At CRYPTO 2007, Damgård and Nielsen introduced a preprocessing approach to multi-party computation (MPC) to achieve linear communication complexity. Another approach to reduce communication complexity was proposed by Cramer, Damgård, and de Haan at EUROCRYPT 2007, which involved using ramp-secret sharing schemes to jointly share base-field components of secrets from the extension field. In this paper, we combine these two ideas to achieve a non-asymptotic reduction of communication cost in a multi-phase MPC setup. We introduce a new modification of the ramp secret sharing scheme, called compact sharing, and tailor the MPC protocol to accommodate this modification. Compact sharing masks the polynomial coefficients that would otherwise leak during degree reduction. The protocol provides perfect security against static semi-honest adversaries under an explicit tradeoff between the corruption threshold and the extension degree. When the extension degree scales linearly with the number of parties, the gate-evaluation core achieves constant communication overhead relative to an extension-field element, amortized over full preprocessing batches; input and output communication is counted separately.

0.22

An Explicit Below Half Threshold Bound for the Local Leakage Resilience of Shamir's Secret Sharing Scheme

cs.CR cs.IT ·2026-11-09 ·Cheng Zhang, Xin Wang, Xiangliang Kong
similarity 0.63
Abstract

As a fundamental cryptographic primitive, secret sharing distributes a secret among multiple parties and allows certain authorized parties to recover the secret while preventing unauthorized parties from knowing the secret. However, local leakage from each party member allows an adversary to learn partial information from each share, which is not guaranteed by traditional security. In this paper, we study bounds on the reconstruction threshold of Shamir's secret sharing scheme over prime fields against arbitrary 1-bit local leakage. We show that, for all sufficiently large $n$ and every prime $p>n$, the $(n,t)$-Shamir's scheme is $\exp(-Ω(n))$-resilient whenever $t/n\geq 0.489$, for any choice of distinct nonzero evaluation points. Our proof refines the dual-code list recovery analysis and combines complementary Fourier estimates according to the support sizes and biases of the leakage functions, yielding an improved explicit reconstruction threshold bound.

0.17

A Generalized Half-Singleton Bound for List Decoding of Insertion/Deletion Errors

cs.IT math.CO ·2026-10-16 ·Neehar Verma, Camilla Hollanti, Razane Tajeddine
theory similarity 0.61
Abstract

We derive an upper bound on the rate of a linear code capable of list decoding from insertion and deletion errors. Subsequently, we show that a linear code can list decode from at most $n - \frac{L}{L+1}k + 1$ insdel errors with fixed list size $L$, and that this bound is strict when the code does not contain the all-ones vector. We also provide a simple construction of codes achieving the optimal rate for any given list size capable of correcting a single insdel error. All the results hold for linear codes over finite fields of size $q \geq 3$.

0.07

On systematicity of linear function-correcting codes

cs.IT ·2026-08-29 ·Duy Ho
theory similarity 0.60
Abstract

The standard formulation of function-correcting codes uses systematic encodings. We study the redundancy cost of this constraint when both the prescribed function and the encoding are linear. We introduce the function-separation distance and show that several classical unequal error protection parameters are special cases. For linear functions and encodings, this distance is the first relative generalized Hamming weight of the code relative to the encoded kernel. We formulate free and systematic linear separation problems. We prove that the optimal free redundancy depends only on the rank of the function, and determine the optimal systematic redundancy for prescribed separations $d\leq3$.

0.50