Quantum resistant limits found for Shamir secret sharing leakage
Quantum Leakage Resilience of Shamir Secret Sharing
Cryptography and Security
Summary
The paper studies how safe Shamir secret sharing is when parts of the secret leaks quantum information instead of classical bits. The authors show that if the secret sharing uses a high enough threshold, it remains secure against certain quantum leakages with only limited entanglement. However, if many leakage devices share strong quantum entanglement, even small leaks can break security. Their results clarify when quantum attacks can and cannot compromise the scheme.
What this means in practice
- •For cryptographic engineers: Design quantum-resistant secret sharing protocols by selecting threshold parameters that limit quantum leakage risks.
- •For quantum security analysts: Assess the security of classical secret sharing schemes against adversaries equipped with limited quantum leakage capabilities.
A theory result. No direct application yet.
Authors
Rishabh Batra, Fuyuki Kitagawa, Ryo Nishimaki, Takashi Yamakawa
Abstract
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.