💻 computer science

Quantum Leakage Resilience of Shamir Secret Sharing

This paper establishes that unmodified Shamir secret sharing over prime fields remains secure against quantum local leakage when the threshold rate exceeds approximately 0.73339, provided that leakage devices have limited or no entanglement, while demonstrating that arbitrary entanglement among devices can completely break security even with classical leakage.

Original authors: Rishabh Batra, Fuyuki Kitagawa, Ryo Nishimaki, Takashi Yamakawa

Published 2026-09-30

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Rishabh Batra, Fuyuki Kitagawa, Ryo Nishimaki, Takashi Yamakawa

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the digital age, protecting a secret often means splitting it into pieces and handing those pieces to different people. This method, known as secret sharing, ensures that no single person holds the entire key to a vault, a password, or a private code. Instead, a specific number of people must come together to reconstruct the original information. This approach is a cornerstone of modern cryptography, used to manage encryption keys and secure communications. For decades, researchers have studied how to make these systems robust against a specific type of threat: an attacker who cannot steal the entire pieces but can peek at tiny fragments of them. This is called leakage. If an attacker can read even a single bit of information from every person's piece, they might be able to piece together the whole secret. The question has always been: how much can an attacker learn before the system breaks?

Now, as technology moves from classical computers to quantum machines, the nature of these tiny fragments changes. Instead of just bits of information, an attacker might be able to extract a quantum bit, or qubit, which can exist in a complex state of multiple possibilities at once. A new study by researchers at EPFL and NTT Social Informatics Laboratories investigates whether the standard, widely used method of secret sharing can survive this new kind of quantum peeking. They found that the system remains secure, but only if the number of people required to unlock the secret is high enough. Specifically, if the group needs more than about seventy-three percent of the total participants to reconstruct the secret, the scheme holds up even when an attacker tries to extract a quantum bit from every single participant's share. This security holds true even if the attacker measures all the leaked quantum bits together at once.

The researchers also explored a more complex scenario where the devices holding the secret pieces might share a special quantum connection called entanglement with each other, or even with the attacker. Entanglement is a phenomenon where particles become linked so that the state of one instantly influences the other, regardless of distance. The study shows that the system can still withstand this threat, provided the number of devices sharing these connections remains relatively small compared to the total group size. However, the researchers also discovered a hard limit. If the number of devices sharing entanglement grows too large, the system becomes vulnerable. They demonstrated a specific attack where a group of devices, using a shared quantum state known as a GHZ state, could leak just one classical bit each and still reveal the secret. This attack works even if the devices have no entanglement with the attacker, proving that the size of the entangled group is the critical factor.

The work relies on a mathematical approach that treats the secret sharing process like a pattern of waves. By analyzing how these waves interact, the researchers could prove that as long as the threshold for reconstruction is high enough, the information leaked by the quantum bits is too scrambled to be useful. They showed that for a group of participants, if the required number to unlock the secret is roughly seventy-three percent of the total, the chance of an attacker guessing the secret correctly is so small it is effectively zero. This result is significant because it applies to the unmodified version of the secret sharing scheme that is already in use today, meaning no changes to existing protocols are needed to gain this level of quantum security.

The study also clarifies the boundary between safety and danger. While a small number of devices sharing entanglement is safe, the researchers proved that if a large enough group shares these connections, the security collapses. They found that even with classical bits, if enough devices are entangled, they can coordinate their leaks to reveal the secret. This suggests that in a world with quantum capabilities, the security of secret sharing depends not just on how much information is leaked, but on how the devices holding that information are connected. The findings provide a clear map for where these systems are safe and where they are not, offering a guide for building secure systems in a future where quantum computers are a reality.

The researchers did not stop at proving security; they also identified the precise point where it fails. They calculated that for a system to remain secure against a linear number of entangled devices, the threshold rate must be sufficiently high. If the threshold is too low, the system is insecure. This balance between the number of participants needed to unlock the secret and the amount of entanglement allowed is the key takeaway. The study confirms that while quantum leakage is a serious concern, it is manageable with the right parameters. The results offer a reassuring conclusion for those relying on these cryptographic tools: the familiar methods of secret sharing are resilient, provided the rules for reconstruction are set high enough to keep the quantum threats at bay.

Technical Summary: Quantum Leakage Resilience of Shamir Secret Sharing

Problem Statement

The paper investigates the quantum leakage resilience of the standard, unmodified Shamir secret sharing scheme over prime fields $\mathbb{F}_p$ . While Shamir's scheme is widely used in threshold cryptography and secure multiparty computation, its security guarantees traditionally assume that unauthorized sets learn nothing about the secret. In practice, however, partial information (leakage) may be exposed through side channels.

The authors extend the study of local leakage resilience from the classical setting (where an adversary obtains a short classical output, e.g., one bit, from each share) to the quantum setting. In this model, each party's device receives a classical share and outputs a single qubit (or a small number of qubits) to an adversary who may perform joint measurements. The study further explores how pre-shared entanglement among leakage devices, or between devices and the adversary, impacts security.

Methodology

The paper employs a combination of finite-field Fourier analysis and properties of Maximum Distance Separable (MDS) codes to bound the distinguishing advantage between two secret states.

Pauli-Fourier Reduction:
- The leakage from each share is modeled as a density matrix $\rho_i(y_i)$ . The authors expand this in the Pauli basis: $\rho_i(y) = \frac{1}{2}(I + r_{i,X}(y)X + r_{i,Y}(y)Y + r_{i,Z}(y)Z)$ .
- They define a "Fourier budget" $W_i(a)$ based on the squared magnitudes of the Fourier coefficients of the Pauli coefficient functions.
- Using Parseval's identity and the orthogonality of Pauli operators, the distinguishing advantage is bounded by a sum over the dual Shamir code $C^\perp_0$ :
  $\text{Adv} \leq \sum_{a \in C^\perp_0 \setminus \{0\}} \prod_{i=1}^n \sqrt{W_i(a_i)}$
- This reduces the quantum security problem to controlling a weighted sum over the dual code, similar to classical leakage proofs but complicated by the matrix-valued nature of the coefficients.
Handling Entanglement and Blocks:
- Disjoint Blocks: For devices sharing entanglement within disjoint blocks (but not between blocks or with the adversary), the authors apply a block MDS Brascamp-Lieb inequality. This allows them to bound the sum of products of trace norms of Fourier coefficients for block outputs.
- Entanglement with Adversary: For a set of devices $E$ sharing arbitrary entanglement with the adversary, the authors use a reduction argument. They show that if the adversary learns the classical shares of $E$ , the security of the remaining system reduces to an unentangled Shamir scheme with $n-r$ parties and threshold $t-r$ .
Negative Results (Attacks):
- The paper constructs a specific attack using a GHZ state shared among $t$ devices. By applying phase shifts dependent on their shares and measuring in the Pauli-X basis, the devices can distinguish between secrets with high advantage, even if they only output one classical bit each.

Key Contributions and Results

1. Unentangled Quantum Leakage

The authors prove that Shamir secret sharing is secure against unentangled local one-qubit leakage provided the threshold rate $\tau = t/n$ exceeds a specific constant $\tau^\star \approx 0.73339$ .

Result: If $\tau > \tau^\star + \eta$ (for fixed $\eta > 0$ ), the distinguishing advantage is exponentially small ( $2^{-\Omega(n)}$ ).
Technique: This is derived using the block MDS Brascamp-Lieb inequality with block size $b=1$ .

2. Disjoint Entangled Blocks

Security is extended to scenarios where devices are partitioned into disjoint blocks of fixed maximum size $b$ , where devices within a block may share entanglement and perform joint computations, but blocks are independent of each other and the adversary.

Result: Security holds for sufficiently high threshold rates $\tau > \tau^\star(b)$ , where $\tau^\star(b) < 1$ . As the block size $b$ increases, the required threshold rate approaches 1.
Specifics: Table 1 in the paper lists sufficient thresholds for equal block sizes (e.g., for $b=2$ , $\tau \approx 0.933$ ; for $b=3$ , $\tau \approx 0.987$ ).

3. Leakage with Adversary Entanglement

The paper analyzes the case where a linear number of devices ( $r = \delta n$ ) share arbitrary entanglement with each other and the adversary.

Result: Security holds if the "residual" rate satisfies:
$\frac{\tau - \delta}{1 - \delta} > \tau^\star$
This implies that for a fixed threshold rate $\tau > \tau^\star$ , security is maintained even if a linear fraction of devices ( $\delta < \frac{\tau - \tau^\star}{1 - \tau^\star}$ ) share entanglement with the adversary.

4. Negative Result: GHZ Attack

The authors demonstrate that if $t$ devices share a GHZ state, the scheme becomes insecure even under classical single-bit leakage.

Mechanism: $t$ devices share a GHZ state. Each applies a phase based on their share and measures in the X-basis. The product of the outcomes reveals the secret with advantage $\cos^2(\pi/(2p)) \approx 1 - O(p^{-2})$ .
Implication: This attack requires no entanglement with the adversary, only among the $t$ leakage devices. It establishes that the maximum number of devices that can share arbitrary entanglement while preserving security is linear in $n$ (up to constant factors), but the optimal fraction remains an open question.

Significance and Claims

The paper claims to initiate the study of quantum leakage resilience for the widely used, unmodified Shamir secret sharing scheme.

Robustness of Standard Schemes: The results show that the standard Shamir scheme retains strong security guarantees against quantum leakage without requiring new sharing algorithms or protocol changes, provided the threshold rate is sufficiently high (above $\approx 0.733$ ).
Role of Entanglement: The work highlights a critical distinction: while unentangled quantum leakage is manageable with high thresholds, the presence of arbitrary entanglement among leakage devices (specifically a GHZ state among $t$ devices) can break security even for classical outputs.
Optimality: The authors are modest regarding the optimality of their bounds. They note that the sufficient threshold $\tau^\star \approx 0.733$ is higher than the known classical bound ( $\approx 0.668$ ) and pose the question of whether this gap can be closed. Similarly, the exact optimal fraction of entangled devices compatible with security is left as an open problem.

The paper concludes that quantum leakage resilience depends fundamentally on both the size of the leaked outputs and the entanglement structure available to the leakage devices.