We study leakage from Shamir secret sharing when each device uses its share to produce one qubit from an initial quantum resource independent of the secret and sharing randomness. We prove exponentially small trace distance between the leakage states of any two secrets, when reconstruction requires a sufficiently large fraction of the shares, for fixed stationary chains satisfying an upper operator mixing condition and for resources generated by fixed finite quantum memories with primitive transfer channels. These guarantees permit arbitrary extensions of the device marginal as adversary side information and hold uniformly over prime fields larger than the number of shares. For independent device--reference pairs, which provide the quantitative input to the argument, we determine the optimal exponential base when reconstruction requires all shares: $2\sqrt2/π$ for a qubit and $2/π$ for a classical bit, in both cases allowing arbitrary finite references. A comparison of selected marginals with product states converts the bounds for independent device--reference pairs into security guarantees for the correlated resources.
AI Summary
The paper studies quantum leakage from prime-field Shamir secret sharing: each device applies a share-dependent local channel to a share-independent quantum resource and releases one qubit. The adversary receives all outputs and arbitrary finite-dimensional quantum side information; devices cannot communicate during leakage.
For independent device–reference pairs, leakage is exponentially small when the reconstruction rate $t/n$ exceeds $0.9197212757$ by a fixed margin. Classical-bit outputs have sufficient rate $0.7172542188$. At full threshold $t=n$, the optimal exponential bases are $2\sqrt{2}/\pi$ for an entanglement-assisted qubit and $2/\pi$ for a classical bit. More generally, output dimension $d$ and pairwise Schmidt number at most $r\le d$ give base $(dr/\pi)\sin(\pi/(dr))$, with matching bounds up to constant prefactors.
For correlated resources, exponential security near full threshold holds for fixed stationary chains satisfying an upper operator mixing condition, fixed finite quantum memories with primitive transfer channels, and corresponding open-boundary matrix product states. Further applications cover source networks, graph states, and Haar-typical resources. Constant-advantage attacks require preparation depth $\Omega(\log n)$ in a bounded-arity, complete-device-group circuit model; GHZ preparation supplies a matching order upper bound.
The proofs combine reference-dimension-independent Fourier estimates, Shamir’s dual MDS code, exact conditioning on revealed shares, and a reference filter transferring product-resource bounds through marginal operator domination. The optimal security threshold below $t=n$ remains open. Memory guarantees require fixed processes or uniform mixing: size-dependent primitive memories can retain constant leakage. The depth bound does not cover unrestricted parallel gates on individual registers.
No sign of AI-generated textStrong assumptions
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
We study leakage from Shamir secret sharing when each device uses its share to produce one qubit from an initial quantum resource independent of the secret and sharing randomness. We prove exponentially small trace distance between the leakage states of any two secrets, when reconstruction requires a sufficiently large fraction of the shares, for fixed stationary chains satisfying an upper operator mixing condition and for resources generated by fixed finite quantum memories with primitive transfer channels. These guarantees permit arbitrary extensions of the device marginal as adversary side information and hold uniformly over prime fields larger than the number of shares. For independent device--reference pairs, which provide the quantitative input to the argument, we determine the optimal exponential base when reconstruction requires all shares: 22/π for a qubit and 2/π for a classical bit, in both cases allowing arbitrary finite references. A comparison of selected marginals with product states converts the bounds for independent device--reference pairs into security guarantees for the correlated resources.
The paper studies quantum leakage from prime-field Shamir secret sharing: each device applies a share-dependent local channel to a share-independent quantum resource and releases one qubit. The adversary receives all outputs and arbitrary finite-dimensional quantum side information; devices cannot communicate during leakage.
For independent device–reference pairs, leakage is exponentially small when the reconstruction rate t/n exceeds 0.9197212757 by a fixed margin. Classical-bit outputs have sufficient rate 0.7172542188. At full threshold t=n, the optimal exponential bases are 22/π for an entanglement-assisted qubit and 2/π for a classical bit. More generally, output dimension d and pairwise Schmidt number at most r≤d give base (dr/π)sin(π/(dr)), with matching bounds up to constant prefactors.
For correlated resources, exponential security near full threshold holds for fixed stationary chains satisfying an upper operator mixing condition, fixed finite quantum memories with primitive transfer channels, and corresponding open-boundary matrix product states. Further applications cover source networks, graph states, and Haar-typical resources. Constant-advantage attacks require preparation depth Ω(logn) in a bounded-arity, complete-device-group circuit model; GHZ preparation supplies a matching order upper bound.
The proofs combine reference-dimension-independent Fourier estimates, Shamir’s dual MDS code, exact conditioning on revealed shares, and a reference filter transferring product-resource bounds through marginal operator domination. The optimal security threshold below t=n remains open. Memory guarantees require fixed processes or uniform mixing: size-dependent primitive memories can retain constant leakage. The depth bound does not cover unrestricted parallel gates on individual registers.
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 τ⋆≈0.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 τ⋆, 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.
Secret sharing is an instrumental tool for sharing secret keys in distributed systems. In a classical threshold setting, this involves a dealer who has a secret/key, a set of parties/users to which shares of the secret are sent, and a threshold on the number of users whose presence is needed in order to recover the secret. In secret sharing, secure links with no leakage are often assumed between the involved parties. However, when the users are nodes in a communication network and all the links are physical links, e.g., wireless, such assumptions are not valid anymore. In order to study this critical problem, we propose a statistical leakage model of secret sharing, where some noisy versions of all the secret shares might be independently leaked to an adversary. We then study the resilience of the seminal Shamir's secret sharing scheme with statistical leakage, and bound certain measures of security (i.e., semantic security, mutual information security), given other parameters of the system including the amount of leakage from each secret share. We show that for an extreme scenario of Shamir's scheme, in particular when the underlying field characteristic is 2, the security of each bit of the secret against leakage improves exponentially with the number of users. To the best of our knowledge, this is the first attempt towards understanding secret sharing under general statistical noisy leakage.
Leakage from a known encoding subspace can be detected by projection. However, the corresponding projector is unavailable when the encoding subspace is not classically specified. Here we show how independent quantum references prepared by the same encoder enable leakage detection without a classical description of the encoding. A coherent measurement on the references and a single message leaves every state within the two-dimensional encoding subspace, including its entanglement with a remote system, exactly unchanged. We derive the exact detection law for M ideal references and prove optimality among tests with zero false alarm for every encoding. For orthogonal leakage, the miss probability is asymptotic to 4/M, independent of the ambient dimension d. Measuring all references first, even collectively, gives zero detection at every finite budget under the same zero-false-alarm requirement. For a fixed detection target between zero and one, the optimal measurement-first cost is Θ(d/ε) at sufficiently small tolerance ε on normal false alarm and conditional disturbance; a dimension-independent coherent budget suffices. For one logical qubit encoded in three physical qubits, seven coherent references achieve at least 50% orthogonal-leakage detection, whereas any measurement-first receiver needs at least 588 under the same 1% normal tolerances. Quantum references thus support leakage checks without classical reconstruction, with a sample advantage exponential in the number of physical qubits.
Cryptographic hash functions are fundamental primitives widely used in practice. For such a function f:{0,1}n→{0,1}m, it is nearly impossible for an adversary to produce the hash f(x) without knowing the secret message x∈{0,1}n. Unfortunately, all hash functions are vulnerable under the side-channel attack, which is a grave concern for information security in practice. This is because typically m≪n and an adversary needs only m bits of information to pass the verification test. In sharp contrast, we show that when quantum states are used, the leakage allowed can be almost the entire secret. More precisely, we call a function that maps n bits to m qubits a quantum cryptographic function if the maximum fidelity between two distinct hashes is negligible in n. We show that for any k=n−ω(logn), all quantum cryptographic hash functions remain cryptographically secure when leaking k bits of information. By the quantum fingerprinting constructions of Buhrman et al.~({\em Phys. Rev. Lett.} 87, 167902), for all m=ω(logn), there exist such quantum cryptographic hash functions. We also show that one only needs ω(log2n) qubits to verify a quantum cryptographic hash, rather than the whole classical information needed to generate one. Our result also shows that to approximately produce a small amount of quantum side information on a classical secret, it may require almost the full information of the secret. This large gap represents a significant barrier for proving quantum security of classical-proof extractors.
Side-channel attacks have repeatedly falsified the assumption that cryptosystems are black boxes. Leakage-resilient cryptography studies the robustness of cryptographic constructions when an unforeseen revelation of information occurs. In this context, recently, Benhamouda, Degwekar, Ishai, and Rabin (CRYPTO–2018) motivated the study of the local leakage resilience of secret-sharing schemes against an adversary who obtains independent leakage from each secret share.Motivated by applications in secure computation, Benhamouda et al. (CRYPTO–2018) initiated the study of the local leakage resilience of Shamir’s secret-sharing scheme, an essential primitive for nearly all threshold cryptography. The objective is to achieve local leakage resilience with as small a fractional reconstruction threshold as possible. Previously, Benhamouda et al. showed that the reconstruction threshold k being at least 0.907 times the number of parties n is sufficient for Shamir’s secretsharing scheme to be resilient against arbitrary single-bit local leakage from each secret share. After that, Maji et al. (CRYPTO–2021) and Benhamouda et al. (Journal of Cryptology–2021) independently lowered this threshold to k/n ⩾ 0.8675 and k/n ⩾0.85, respectively.This paper contributes to this line of research and proves that k/n ⩾ 0.78 is sufficient. Next, motivated by applications in GMW-style leakage-resilient secure computation, our work extends this bound to a more general adversary who corrupts some parties (obtaining their entire secret shares) and obtains leakage from the remaining honest parties’ secret shares.Our technical analysis proceeds by Fourier analysis and accurately estimates an exponential sum arising in this analysis.
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 ℓ, one complete one-bit oblivious transfer uses Θ(ℓ+log2λ) 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).