CS Paper Radar

Leakage-Resilient Computation via Matrix Refreshing

Stefan Dziembowski, Sebastian Faust

cs.CR ·submitted 2026-11-03 13:27 UTC · v1
theory

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Quantum Leakage Resilience of Shamir Secret Sharing

cs.CR quant-ph ·2026-09-29 ·Rishabh Batra, Fuyuki Kitagawa, Ryo Nishimaki, Takashi Yamakawa
similarity 0.70
Abstract · 38 pages, 2 tables

We initiate the study of quantum leakage resilience of unmodified Shamir secret sharing over prime fields. A well-studied leakage model for Shamir's secret sharing classically is single-bit local leakage from each share. We consider its quantum analogue where, for each party, a local leakage channel takes as input the party's share and outputs a leaked qubit. Without preshared entanglement, we show that the distinguishing advantage is $2^{-Ω(n)}$ when the threshold rate $t/n=τ$ exceeds $τ_\star\approx0.73339$ by a fixed positive margin. More generally, we allow disjoint entangled blocks of any fixed maximum size where there is no entanglement between different blocks or with the adversary, and each block emits at most a fixed number of qubits. Security holds when the threshold rate is high enough (sufficiently close to one). We then allow a specified set of devices to share entanglement with the adversary. We show that security holds even when a linear number of devices ($αn$ for small $α>0$) share entanglement with each other and with the adversary for a large enough threshold rate. As a complementary negative result, we also show that even classical single-bit leakage makes Shamir scheme insecure if we allow arbitrarily large entanglement between the leakage devices. A GHZ state shared by exactly $t$ leakage devices makes even classical one-bit leakage insecure, without any entanglement with the adversary. In this attack, each participating device emits only one classical bit, and their joint parity distinguishes any chosen pair of secrets with a constant advantage. Thus, for fixed threshold rates above $τ_\star$, the maximum number of devices that may share arbitrary entanglement with one another and with the adversary while preserving security is linear in $n$ up to constant factors, although the optimal support fraction remains open.

0.61

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

Local Leakage Resilience of Shamir Secret Sharing: Below Half Threshold Rate

cs.CR ·2026-10-13 ·Hai H. Nguyen
theory similarity 0.68
Abstract

We study the local leakage resilience of Shamir secret sharing, where an adversary leaks a bounded number of bits from every share. For $n$ parties and reconstruction threshold $k$ over a prime field $\mathbb{F}_p$ with $p>n$, we prove the following. (1) There is an absolute constant $c_{\mathrm{bh}}<1/2$ such that, for $k\ge c_{\mathrm{bh}}n$, Shamir sharing is resilient to arbitrary one-bit leakage from every share. The best previous threshold was $0.668n$. (2) For every fixed $0<δ<1/2$ and $k\ge(1/2+δ)n$, Shamir sharing is resilient to $\left\lfloor\fracδ{24}\log_2 n\right\rfloor$ bits of arbitrary local leakage per share. By a recent attack, this number of bits is optimal up to a constant factor depending on $δ$. (3) For every fixed threshold rate $c>0$ and $k\ge cn$, Shamir sharing is resilient to quadratic-residue leakage and to almost all local leakage functions of up to $η_c\log_2 p$ bits, for a constant $η_c>0$. All three results follow from one analytic framework, which we develop for generalized Reed--Solomon codes: local leakage from a uniform codeword is statistically close to the same leakage from independent uniform field elements. The framework expresses the leakage distance as the norm of a function on the leakage outputs. The Efron--Stein decomposition splits this function into orthogonal components indexed by supports of dual codewords. Two tools bound the components: list recovery of the dual code, which is ordinary list decoding for one-bit leakage, and a generalized von Neumann inequality for MDS systems of linear forms that retains linearly many Gowers norms. The first tool gives the result above half, the second gives the constant-rate result, and applying both to different ranges of supports in the same decomposition gives the result below half.

0.15

On the Leakage of Massey Secret Sharing Schemes under Linear Computations

cs.CR ·2026-09-17 ·Nadja Aoutouf, Daniel Augot
hot direction similarity 0.67
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.

0.37

Robust and leakage-resilient device-independent oblivious transfer in MiniQCrypt

cs.CR quant-ph ·2026-10-01 ·Rishabh Batra, Zhili Chen, Rahul Jain, YaoNan Zhang
theory similarity 0.66
Abstract · v3: Improved robustness and leakage tolerance, now allowing constant rates of noise and leakage

Assuming post-quantum one-way functions, we construct device-independent oblivious transfer and bit commitment that tolerate independent honest faults at a constant rate and adaptive, bidirectional quantum leakage between the laboratories at a constant rate. Honest parties use trusted classical computation to operate untrusted quantum devices, which may share arbitrary entanglement and perform joint measurements without assumptions of independence or identical distribution. Security is simulation-based against quantum polynomial-time adversaries and composes sequentially with efficient simulators. For security parameter $λ$ and a prescribed total leakage budget $\ell$, one complete one-bit oblivious transfer uses $Θ(\ell+\log^2λ)$ device coordinates in at most three single-use device windows, including preprocessing, and polynomial classical computation and communication. The leakage budget is shared across these windows. The commitment has efficient simulators against both parties and yields device-independent coin tossing with abort; each uses one window. Completeness of oblivious transfer gives device-independent secure computation with abort for every efficiently computable classical functionality on a fixed number of parties, against static corruption of any proper subset, provided each reached call to oblivious transfer satisfies the device and budget conditions. The construction combines short selectors with code-based choice masking, a global audit, and error correction across field symbols. The commitment extractor changes a classical code coset while leaving the device execution and its leakage unchanged. Sender security uses a global Fourier analysis and a selector-aware Magic Square repetition bound derived from the two-round threshold theorem of Kundu and Tan (2023).

0.25

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.65
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

SecDMP: Provably Secure Data Memory-Dependent Prefetching (Extended Version)

cs.CR ·2026-10-27 ·Jens Sprengers, Marton Bognar, Lesly-Ann Daniel, Frank Piessens
top venuecode/data similarity 0.64
Abstract · This is the extended version of our paper accepted at NDSS 2027 and consists of 32 pages

Data memory-dependent prefetchers (DMPs) are a microarchitectural optimization recently introduced in mainstream desktop and server CPUs. Although DMPs offer performance improvements, they have been shown to enable side-channel leakage of secrets, even from constant-time code that has been hardened against Spectre attacks. Unfortunately, existing defenses either incur significant performance overhead or, as we show, fail to prevent all DMP leakage. In this work, we address this gap by designing a defense that is both secure and efficient. First, we propose a classification of DMP leakage, categorize existing and novel attacks, and analyze which leakage classes are mitigated by existing defenses. We validate this analysis empirically by implementing the first open-source DMPs on a RISC-V processor, showing that the only existing defense that aims to preserve DMP performance fails to protect against entire leakage classes. Next, we propose SecDMP, a provably secure and efficient hardware-based defense. SecDMP requires secrets to be marked in memory and ensures that DMPs never encode these secrets in the microarchitecture---without compromising performance for public data. We formally prove that SecDMP introduces no leakage beyond a baseline semantics without DMPs. Notably, when combined with speculative-execution defenses, SecDMP restores complete microarchitectural security for constant-time code. Finally, our empirical evaluation shows that SecDMP prevents all DMP leakage while incurring minimal performance overhead and hardware cost.

0.51

Secret Sharing Despite Non-Extractable Randomness

cs.CR ·2026-10-14 ·Divesh Aggarwal
similarity 0.64
Abstract

Bosley and Dodis (TCC 2007) proved that a class of imperfect randomness sources that suffices for information-theoretic encryption of messages longer than the logarithm of the key length must admit deterministic extraction of nearly uniform bits, and asked whether the same is true of two-out-of-two secret sharing. Aggarwal, Chung, Obremski, and Ribeiro (TCC 2022) gave a positive answer for schemes that are in addition leakage-resilient or non-malleable; the original question remained open. We answer it in the negative. For every $b\ge2$ we construct a class of flat sources on $\{0,1\}^{b+2}$, each of min-entropy at least $b$, together with a perfectly correct and perfectly private two-out-of-two scheme that shares a $b$-bit secret into two $(b+1)$-bit shares using any source in the class, and we show that every deterministic map from $\{0,1\}^{b+2}$ to $\{0,1\}$ is at statistical distance at least $1/6$ from uniform on some source in the class. This implies that sharing a long enough secret does not require extractable randomness. The proof is a short parity argument. The idea of the construction extends to other thresholds: for two-out-of-$n$ and $r$-out-of-$r$ sharing we give perfect schemes with $(b+1)$-bit shares, private for classes of flat sources from which no single bit can be extracted with error below $1/(4n-2)$ and $1/(2(2^r-1))$, respectively.

0.23