PaperlayerView exact revision on arXiv

Source-linked AI summary

Quantum Leakage Resilience of Shamir Secret Sharing

Rishabh Batra, Fuyuki Kitagawa, Ryo Nishimaki, Takashi Yamakawa

arXiv:2609.37276v1quant-phcs.CR

TL;DR

The paper asks whether unmodified Shamir secret sharing can withstand local quantum leakage, including when leakage devices share entanglement. It analyzes security across several entanglement models and gives a GHZ-based classical leakage attack. Security bounds and the attack show that resilience depends on leakage-output size and available entanglement.

  • Problem

    Classical local leakage resilience is well studied, but whether unmodified Shamir sharing resists quantum leakage, and how security depends on devices’ preshared entanglement, remains open.

    Source: §1 · p. 2

  • Method

    The paper uses matrix-valued Fourier analysis and code-based bounds to analyze local quantum leakage under several entanglement models, and constructs a GHZ-based classical leakage attack.

    Source: §1.2 · p. 5, §1.3 · p. 7

  • Results

    For unentangled one-qubit leakage, distinguishing advantage is exponentially small above τ⋆≈0.73339 by a fixed margin; fixed-size blocks and a sufficiently small linear entangled support are secure at sufficiently high threshold rates, while a t-device GHZ attack breaks one-bit leakage.

    Source: §1 · pp. 2–3

  • Takeaways & Limitations

    For fixed threshold rates above τ⋆, security is compatible with only a linear number of devices sharing arbitrary entanglement, up to constant factors.

    Source: §1 · p. 3

    The optimal fraction of devices that can share arbitrary entanglement while preserving security remains open.

    Source: §7 · p. 28

Abstract

from arXiv · show

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^{-\Omega(n)}$ when the threshold rate $t/n=\tau$ exceeds $\tau_\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 ($\alpha n$ for small $\alpha>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 $\tau_\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.

1 Introduction

The introduction asks whether unmodified Shamir sharing remains secure under local quantum leakage and varying entanglement among leakage devices. It presents security bounds for several entanglement models, a GHZ-based classical leakage attack, and the techniques and prior work framing those results.

1 Introduction

  • Ordinary threshold privacy does not cover partial leakage from hidden shares, motivating study of quantum leakage resilience for unmodified Shamir sharing.The basic model lets each device map its classical share to one qubit, which the adversary may measure jointly.Source: §1 · p. 2

1.1 Our results

  • For unentangled one-qubit leakage, distinguishing advantage is exponentially small when t/n exceeds τ⋆≈0.73339 by a fixed margin; fixed-size entangled blocks are secure above a sufficient threshold below one.The block guarantee assumes no entanglement between blocks or with the adversary, and allows a fixed bound on each block’s output qubits.Source: §1 · pp. 2–3, §1.1 · p. 3
  • Security also holds for sufficiently large threshold rates when αn devices share entanglement with each other and the adversary, while a GHZ state across t devices enables one-bit classical leakage to distinguish secrets.The attack’s advantage is at least cos2(π/(2p)) = 1 −O(p−2); the paper says the security threshold is not claimed optimal.Source: §1 · p. 3, §1.1 · p. 4
  • The combined model permits a linear-size adversarially entangled set alongside independent constant-size blocks when residual rate (t−r)/(n−r) exceeds the corresponding block threshold by a fixed margin.The results strengthen guarantees without changing Shamir’s sharing or reconstruction algorithms.Source: §1.1 · p. 4

1.2 Techniques

  • Matrix-valued Fourier analysis and Pauli orthogonality bound distinguishing advantage, while MDS-code estimates and a block MDS Brascamp-Lieb inequality control the resulting sums.For adversarially entangled devices, the analysis reveals their shares and reduces the remaining problem to a smaller Shamir scheme.Source: §1.2 · pp. 5–6
  • The GHZ attack encodes share-dependent phases and uses the parity of local Pauli-X measurement outcomes to distinguish secrets, despite each device emitting one bit.Rescaling local phases and adding a fixed phase lets the attack target any chosen pair of distinct secrets.Source: §1.2 · pp. 6–7

1.3 Related work

  • Prior work established classical leakage bounds and quantum-leakage-resistant schemes with different constructions; this paper analyzes the widely used unmodified Shamir scheme.Its analysis combines a block MDS Brascamp-Lieb inequality with Fourier estimates for matrix-valued functions.Source: §1.3 · p. 7

2 Preliminaries

This section sets up Shamir sharing and the code properties used to analyze its leakage. It defines the leakage models and the distinguishing-advantage security guarantee.

2.1 Codes and Shamir’s scheme

  • Shamir sharing samples a degree-less-than-t polynomial with constant term s and gives party i its evaluation at a distinct nonzero point; any t shares reconstruct s.The zero-secret sharing space is an MDS code, and every set of fewer than t shares is statistically independent of the secret.Source: §2.1 · p. 9
  • The dual Shamir code is an [n, n−t+1, t]p MDS code, so every nonzero codeword has weight at least t.MDS coordinate projections onto n−t+1 positions are bijective.Source: §2.1 · p. 9

2.2 Distinguishing advantage and leakage models

  • Leakage devices map shares to quantum outputs; models specify whether devices are independent, grouped into disjoint blocks, or entangled with one another and the adversary.The disjoint-block model allows joint dependence on shares within each block, while different blocks have product outputs conditioned on the shares.Source: §2.2 · p. 9, The adversary receives · p. 10

The adversary receives

  • Security bounds the trace distance between the adversary’s states for any two secrets, and shared classical randomness independent of the shares preserves those bounds.Exponential security means advantage at most 2^−cn for a constant c>0 and sufficiently large n.Source: The adversary receives · p. 11

3 The Pauli-Fourier analysis

The Pauli–Fourier analysis converts local qubit leakage into Fourier coefficients and uses their constraints to bound how much the adversary’s state depends on the secret. The sharper later analysis instead works directly with matrix-valued Fourier coefficients.

  • This section develops the Pauli–Fourier reduction used to prove the elementary 5/6 threshold in Section 4, whereas sharper Section 5 bounds use separate direct analysis of matrix-valued Fourier coefficients.Source: §3 · p. 11
  • Each leaked qubit is represented by three real Pauli coefficient functions whose squared values sum to at most one for every share.The identity coefficient is fixed at one, yielding a Fourier budget for each coordinate.Source: §3 · p. 12
  • Fourier inversion and averaging over the sharing cosets leave only dual-code frequencies, while the zero frequency cancels between secrets.The resulting operator difference is bounded using a Hilbert–Schmidt reduction to trace norm.Source: §3 · pp. 12–13

4 An elementary Cauchy-Schwarz bound

An elementary Cauchy–Schwarz proof gives exponential security against unentangled local one-qubit leakage at threshold rates above 5/6. The argument partitions coordinates to apply bounds on projections and nonzero codewords.

  • This proof is simpler and more intuitive than the Section 5 bound, but gives a weaker threshold.It uses only Cauchy–Schwarz and adapts a classical proof to quantum leakage.Source: §4 · p. 13
  • For every fixed η>0, unentangled local one-qubit leakage is exponentially secure when t>(5/6+η)n.The proposition gives the sufficient threshold t≥(2n+2)/3, and the proof states the stronger asymptotic 5/6 bound.Source: §4 · p. 14
  • The proof partitions the coordinates into three disjoint sets, using two sets of size n−t+1 and a remainder of size 2t−n−2.The condition t≥(2n+2)/3 ensures the sets can be formed.Source: §4 · p. 14
  • The argument combines bijective projections on the first two sets with the bound that a nonzero codeword has at most n−t zero coordinates.These properties feed the Cauchy–Schwarz analysis.Source: §4 · p. 14

5 The MDS Brascamp-Lieb bound for disjoint blocks

The section proves exponential security for disjoint entangled leakage blocks at sufficiently high threshold rates, then sharpens the threshold when blocks are equal-sized. Its analysis combines per-block Fourier bounds with a block MDS Brascamp–Lieb inequality.

5.1 Fourier bounds for one block

  • The per-block analysis bounds squared trace norms of Fourier coefficients and each nonzero coefficient’s trace norm to control higher-power sums.Input share count and output dimension are treated separately, allowing bounded output-qubit counts different from block sizes.Source: §5.1 · p. 15, §5 · p. 15

5.2 A block MDS inequality

  • A block MDS Brascamp–Lieb inequality for unequal block sizes supplies the inequality used to combine the per-block bounds.The inequality is stated under the condition k+m_j−1≤n for every block.Source: §5.2 · p. 16

5.3 Exponential security for disjoint blocks

  • For every fixed maximum block size b, a threshold τ_b<1 suffices for exponential security when the rate exceeds τ_b by a fixed margin.The theorem allows arbitrary joint computation within each block under the disjoint-block model.Source: §5.3 · p. 17

5.4 Threshold rates and the unentangled case

  • For equal blocks of fixed size b, exponential security holds when t/n≥τ_b+η, with τ_b defined by the unique threshold equation.Knowing the exact number of equal-sized blocks improves the bound over the general theorem’s use of M≤n.Source: §5.4 · p. 21
  • For every fixed η > 0, the distinguishing advantage for unentangled local one-qubit leakage is 2^−Ω(n) whenever t/n ≥ τ⋆ + η, where τ⋆ ≈ 0.7333927776.Source: §5.4 · p. 22

6 Pre-shared entanglement

The section reduces security against leakage devices entangled on a specified support to security of a smaller Shamir scheme, then establishes support-size security guarantees and a matching-order GHZ attack. The attack uses entangled devices that each emit one classical bit to distinguish secrets.

6.1 Shamir sharing with revealed shares

  • Security against leakage entangled on a support E follows from security of the smaller Shamir scheme with n−r parties and threshold t−r.Conditioning on the shares in E reduces the remaining shares to affine images of a smaller Shamir sharing.Source: §6.1 · pp. 23–24

6.2 Security threshold

  • For support size r, security is exponential when the stated rate conditions hold; in particular, this applies to r=o(n) when t/n exceeds τ⋆ by a fixed positive gap.The proof obtains a 2^-Ω(n) bound by applying the unentangled leakage result to the reduced scheme.Source: §6.2 · p. 25

6.3 A classical-leakage t-party GHZ attack

  • A GHZ attack using t devices makes classical one-bit leakage insecure, distinguishing any fixed pair of secrets with constant advantage and requiring no adversary-held reference.Each participating device emits one classical bit; the attack uses entangled leakage devices, unlike ordinary classical local leakage.Source: §6.3 · pp. 26–27
  • The section distinguishes the GHZ attack from ordinary classical local leakage: its one-bit outputs come from local measurements on a previously entangled state.The authors state that this distinction means the attack does not contradict security results for ordinary classical local leakage.Source: §6.3 · p. 27

6.2 Security threshold

  • For every fixed threshold rate τ>τ⋆, the certified secure support size is linear in n up to constant factors, while the attack uses t=Θ(n) devices; the optimal support fraction remains open.Security also holds for r=αn with sufficiently small constant α at sufficiently large threshold rates.Source: §6.3 · p. 27

7 Comparison and further questions

The paper compares its sufficient threshold for unentangled one-qubit leakage with a known classical one-bit leakage bound, then identifies open questions about improving the threshold and closing gaps in entangled-leakage security.

7 Comparison and further questions

  • The sufficient threshold for unentangled one-qubit leakage is τ⋆≈0.73339, compared with the approximately 0.668 bound known for worst-case classical one-bit leakage.Source: §7 · p. 28
  • The authors ask whether the quantum leakage threshold can be lowered to match or improve on the classical bound, noting that classical one-bit leakage is a special case of one-qubit leakage.Source: §7 · p. 28
  • The optimal secure entanglement-support fraction is unknown, and the authors ask whether analyzing the supported devices' actual structure can improve on revealing their shares completely.They also ask whether quantum polynomial secret sharing is resilient to local quantum leakage; the classical conditioning argument does not directly apply because its secret and shares are quantum states.Source: §7 · p. 28

Disclosure of AI assistance

The authors disclose that AI tools assisted with attack identification, analysis, numerical work, drafting, table creation, and editing.

Disclosure of AI assistance

  • ChatGPT assisted with identifying the GHZ leakage attack, analyzing and optimizing bounds, drafting, creating numerical tables, and editing; the authors verified and retain responsibility for the final arguments.Source: Disclosure of AI assistance · p. 28

A Proofs of the matrix facts

The appendix states a trace-norm variational identity and an upper bound on expectations of Hermitian matrices against density matrices.

A Proofs of the matrix facts

B Proof of the block Fourier budget

This appendix bounds the block Fourier budget by controlling nonzero Fourier coefficients and aggregating their squared mass.

C Proof of the block MDS inequality

The proof uses the MDS property to control projections onto cyclic intervals, then averages block contributions over interval starting positions to obtain the block inequality.

Loading 2609.37276v1…