Skip to content
Preprint

Leakage-Resilient Computation via Matrix Refreshing

Nov 2026 · 0 citations
Computer Science

TL;DR

It is proved 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.

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 $\lambda$ bits of leakage per party, the transcripts for two stored secrets are at statistical distance at most $C\cdot T\cdot 2^{6\lambda-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\lambda-n/27}$ for $S$ operations and at most $\lambda$ 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.

View source

Similar papers

Preprint Nov 2026

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

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

Chen Zhang, Xin Wang, Xiang-Liang Kong · 0 citations
Preprint Oct 2026

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

Assuming post-quantum one-way functions, this work constructs 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.

Rishabh Batra, Zhi-Li Chen, Rahul Jain et al. · 0 citations
Sep 2026

Quantum Leakage Resilience of Shamir Secret Sharing

The study of quantum leakage resilience of unmodified Shamir secret sharing over prime fields shows that 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 re...

Rishabh Batra, Fuyuki Kitagawa, Ryo Nishimaki et al. · 1 citation · ⚡1
Preprint Oct 2026

Secret Sharing Despite Non-Extractable Randomness

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

Divesh Aggarwal · 0 citations
Preprint Oct 2026

Big Secrets Small Shares: Revisiting Secure Multi-Party Computation

A new modification of the ramp secret sharing scheme, called compact sharing, is introduced, and the MPC protocol is tailored to accommodate this modification, which provides perfect security against static semi-honest adversaries under an explicit tradeoff between the corruption threshold and the extension degree.

Wilton Kim, Van Long Phuoc Pham, S. Kruglik et al. · 0 citations
Open access Sep 2026

Enhanced private set union from secret-shared private membership test

This work introduces a new PSU protocol that is simple, efficient, and secure against known during-execution leakage and hashing-related leakage without relying on Cuckoo Hashing, and achieves linear complexity.

Sang-Min Lee, Jiseung Kim, Yong-Ha Son · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.