Introduction
Quantum secret sharing (QSS) is a central primitive for protecting distributed quantum information and has broad relevance to multiparty quantum cryptography [1 ] , quantum networks [2 ] , and distributed quantum computation [3 ] . In a threshold secret sharing scheme, a dealer distributes a secret among n n n participants such that any authorized set of at least k k k parties can reconstruct it, whereas any unauthorized set of fewer than k k k parties learns nothing about the secret. Since the first QSS protocol based on Greenberger–Horne–Zeilinger states was introduced by Hillery et al. [4 ] , and threshold constructions based on quantum error-correcting codes (QECCs) were developed by Cleve et al. [5 ] , QSS has become a basic tool for secure distributed quantum information processing.
Existing QSS schemes are primarily designed to guarantee correctness and confidentiality: authorized sets can recover the secret, while unauthorized sets obtain no information about it. In realistic distributed settings, however, this is not always sufficient. Valid shares may be leaked, resold, or otherwise exposed by compromised participants, and malicious parties may interfere with reconstruction by submitting forged shares. In either case, conventional QSS provides no intrinsic mechanism to identify the source of compromise or to assign accountability. As a result, QSS remains a confidentiality-oriented primitive even in settings where attribution of leakage or misconduct is operationally essential.
This missing accountability layer is particularly significant in quantum settings. QSS is intended for scenarios in which quantum information is protected across multiple locations or parties, often in environments where trust is limited and failures may be adversarial rather than merely accidental. In such settings, one would like not only to preserve secrecy below threshold, but also to determine which participants are responsible when valid shares are leaked or when the reconstruction process is deliberately corrupted. This motivates the study of traceable QSS, in which attribution and accountability become explicit security objectives.
In the classical setting, this question has recently been formalized through traceable secret sharing (TSS). Goyal et al. [6 ] introduced the basic notion of TSS, aiming to enable provable attribution of leaked shares. Boneh et al. [7 ] subsequently refined the formal framework and identified stronger security requirements, and later work extended these definitions and constructions to more general access structures [8 ] . At a high level, TSS requires that if an unauthorized coalition aggregates its shares into a reconstruction box that reconstructs the secret when supplied with sufficiently many additional shares, then an efficient tracing procedure, given only black-box access to this box, can identify the parties responsible for constructing it. Beyond traceability, TSS also requires protections such as non-implicability, which prevents a malicious tracer from falsely implicating honest parties, and tracer secrecy, which requires that tracing itself not compromise secrecy; in particular, access to the tracing key should reveal no additional information about the secret.
Despite this progress, existing work on TSS has focused almost exclusively on classical secret sharing. Extending traceability to QSS is nontrivial. The shared objects may themselves be quantum states, reconstruction is governed by quantum operations, and accountability must be formulated in a way that is compatible with distributed quantum information processing. To the best of our knowledge, no existing QSS scheme in the literature provides a systematic notion of traceability together with publicly verifiable accountability. Consequently, tracing leaked quantum shares and identifying malicious participants during reconstruction remain open problems.
In this work, we establish a framework for traceable quantum secret sharing under two realistic threat models: one in which participants follow the protocol but leak or resell valid shares, and another in which malicious participants deviate during reconstruction by submitting forged shares. We make three main contributions: (i) we introduce leakage-verifiable and traceable quantum secret sharing, which attributes leaked shares through an explicit leakage-verification mechanism; (ii) we propose malicious-traceable and accountable quantum secret sharing, which identifies participants who submit forged shares during reconstruction and supports publicly verifiable accountability; and (iii) we formulate security definitions for both settings, prove that the proposed protocols achieve the corresponding security guarantees against the relevant adversaries, and perform numerical simulations under per-share depolarizing noise to evaluate their robustness. Our results extend QSS beyond confidentiality alone by incorporating accountability as a security objective, and provide a foundation for traceable quantum secret sharing and accountable multiparty quantum cryptographic primitives.
Threat-model overview
We consider two operational threat models for traceable quantum secret sharing.
Honest-but-leaky model. In the first setting, participants follow the protocol honestly, but an unauthorized coalition may leak or resell its valid quantum shares to a third party. These leaked shares can then be embedded into a reconstruction box that outputs the secret once it receives sufficiently many additional shares from outside the coalition. The tracing goal is to identify, using only black-box access to this box, the participants whose shares were used to construct it. We focus on coalitions smaller than the reconstruction threshold, since larger coalitions can reconstruct and leak the secret on their own without leaving a meaningful tracing target.
Malicious-but-accountable model. In the second setting, malicious participants actively deviate during reconstruction by submitting forged shares. Here the threat is not passive leakage but corruption of the reconstruction procedure itself. Because the submitted shares may be inconsistent with the prescribed protocol, we do not use the reconstruction-box abstraction in this case. Instead, tracing is performed directly from the auxiliary information generated during reconstruction. The objective is to identify the participants responsible for the forged shares while providing evidence that can be independently verified by other parties. As in the leakage setting, we restrict attention to adversarial sets smaller than the reconstruction threshold, since larger sets can reconstruct and leak the secret without requiring any additional honest shares.
Quantum secret sharing has developed along two main directions: constructions based on quantum error-correcting codes (QECCs) and protocols based on multipartite entanglement. In the QECC-based approach, a secret quantum state is encoded into distributed shares and recovered by authorized sets through decoding. Cleve et al. [5 ] gave the first general threshold construction, and Gottesman [9 ] later developed a broader theoretical framework for QSS. Subsequent work explored variants emphasizing coding efficiency, verifiability, and communication efficiency [10 , 11 , 12 , 13 , 14 ] . In parallel, entanglement-based schemes—beginning with the GHZ-state protocol of Hillery et al. [4 ] —use multipartite correlations rather than explicit QECC decoding, and have been extended to continuous-variable, measurement-device-independent, and networked settings [15 , 16 , 17 , 18 , 19 ] .
These works have substantially advanced the confidentiality, robustness, and efficiency of QSS. However, they do not address a different question that becomes important in realistic distributed settings: how to attribute responsibility when valid shares are leaked or when malicious participants submit forged shares during reconstruction. In most existing schemes, leakage is treated either as a generic failure event or as part of an adversarial model dominated by external eavesdropping, rather than as a source of ex post accountability. As a result, current QSS frameworks do not provide systematic notions of traceability, non-repudiation, or publicly verifiable attribution in the presence of leaked or forged shares.
Related ideas have recently been developed in the classical setting under the framework of traceable secret sharing [6 , 7 , 8 ] . To the best of our knowledge, however, no existing QSS scheme provides a corresponding framework for traceability together with publicly verifiable accountability under the threat models considered here. This gap motivates the present work.
Preliminaries
Notation
We consider a threshold setting with parameter k k k and m = 2 k − 1 m = 2k - 1 m = 2 k − 1 parties, indexed by [ m ] = { 0 , … , m − 1 } [m] = \{0,\ldots,m - 1\} [ m ] = { 0 , … , m − 1 } . The secret is a quantum state ∣ ψ ⟩ ∈ H λ |\psi\rangle\in\mathcal{H}_{\lambda} ∣ ψ ⟩ ∈ H λ , where H λ \mathcal{H}_{\lambda} H λ is a d d d -dimensional Hilbert space and λ \lambda λ is the security parameter. We work over the finite field F = Z q \mathbb{F} = \mathbb{Z}_q F = Z q , where q q q is a prime satisfying q ≥ max { m , d } q \ge\max\{m,d\} q ≥ max { m , d } .
We further assume a post-quantum symmetric-key encryption scheme Π S K E = ( E n c , D e c ) \Pi_{\mathrm{SKE}} = (\mathrm{Enc},\mathrm{Dec}) Π SKE = ( Enc , Dec ) with message space F \mathbb{F} F and ciphertext space C \mathcal{C} C , together with a quantum-secure collision-resistant and one-way hash function H : F → F H : \mathbb{F} \to\mathbb{F} H : F → F , as defined in Appendix A.
In this section, we briefly recall several standard notions from quantum information; for a comprehensive treatment, see Ref. [20 ] .
A quantum channel F \mathcal{F} F is a completely positive and trace-preserving (CPTP) map from register x x x to register y y y . That is, for any input density operator ρ x \rho_x ρ x , the channel F \mathcal{F} F outputs a state τ y \tau_y τ y on register y y y , namely F ( ρ x ) = τ y \mathcal{F}(\rho_x) = \tau_y F ( ρ x ) = τ y . When the input is part of a larger joint state ρ x z \rho_{xz} ρ x z , the channel F \mathcal{F} F acts nontrivially only on register x x x , producing an output on register y y y while leaving the other registers, such as z z z , unchanged.
A projector Π \Pi Π is a Hermitian operator satisfying Π 2 = Π \Pi^2 = \Pi Π 2 = Π . A projective measurement is specified by a collection of projectors { Π j } j \{\Pi_j\}_j { Π j } j such that ∑ j Π j = I d \sum_j \Pi_j = \mathop{\mathrm{Id}} ∑ j Π j = Id . Given a quantum state ρ \rho ρ , the probability of obtaining outcome j j j is p j = Tr ( Π j ρ ) p_j = \operatorname{Tr}(\Pi_j\rho) p j = Tr ( Π j ρ ) , and the corresponding post-measurement state is ρ j = Π j ρ Π j p j \rho_j = \frac{\Pi_j\rho\Pi_j}{p_j} ρ j = p j Π j ρ Π j . For registers x x x and y y y , the partial trace Tr y \operatorname{Tr}_y Tr y is the unique linear map satisfying Tr y ( A x ⊗ B y ) = Tr ( B y ) A x \operatorname{Tr}_y(A_x \otimes B_y) = \operatorname{Tr}(B_y)A_x Tr y ( A x ⊗ B y ) = Tr ( B y ) A x for all operators A x A_x A x and B y B_y B y . For any joint state ρ x y \rho_{xy} ρ x y , we write ρ x : = Tr y ( ρ x y ) \rho_x := \operatorname{Tr}_y(\rho_{xy}) ρ x := Tr y ( ρ x y ) .
The trace distance between two quantum states ρ \rho ρ and τ \tau τ , denoted by Td ( ρ , τ ) \operatorname{Td}(\rho,\tau) Td ( ρ , τ ) , is defined as
Td ( ρ , τ ) = 1 2 ∥ ρ − τ ∥ 1 = 1 2 Tr ( ( ρ − τ ) † ( ρ − τ ) ) . (1) \operatorname{Td}(\rho,\tau) = \frac{1}{2}\lVert\rho-\tau\rVert_1 = \frac{1}{2}\operatorname{Tr}\left(\sqrt{(\rho-\tau)^\dagger(\rho-\tau)}\right). \tag*{(1)} Td ( ρ , τ ) = 2 1 ∥ ρ − τ ∥ 1 = 2 1 Tr ( ( ρ − τ ) † ( ρ − τ ) ) . (1)
where ∥ ρ − τ ∥ 1 \lVert\rho-\tau\rVert_1 ∥ ρ − τ ∥ 1 is the trace norm, i.e., the sum of the singular values of ρ − τ \rho-\tau ρ − τ . The trace distance quantifies the operational distinguishability of two quantum states. In particular, the Helstrom theorem states that if ρ \rho ρ and τ \tau τ are given with equal prior probabilities, then the optimal success probability for distinguishing them is 1 2 ( 1 + Td ( ρ , τ ) ) \frac{1}{2}(1+\operatorname{Td}(\rho,\tau)) 2 1 ( 1 + Td ( ρ , τ )) . When τ \tau τ is pure, i.e., τ = ∣ Φ ⟩ ⟨ Φ ∣ \tau= \lvert\Phi\rangle\langle\Phi\rvert τ = ∣ Φ ⟩ ⟨ Φ ∣ , the Fuchs–van de Graaf inequalities imply
1 − ⟨ Φ ∣ ρ ∣ Φ ⟩ ≤ Td ( ρ , τ ) ≤ 1 − ∣ ⟨ Φ ∣ ρ ∣ Φ ⟩ ∣ 2 . (2) 1-\langle\Phi\lvert\rho\lvert\Phi\rangle\le\operatorname{Td}(\rho,\tau) \le\sqrt{1-\lvert\langle\Phi\lvert\rho\lvert\Phi\rangle\rvert^2}. \tag*{(2)} 1 − ⟨ Φ ∣ ρ ∣ Φ ⟩ ≤ Td ( ρ , τ ) ≤ 1 − ∣⟨ Φ ∣ ρ ∣ Φ ⟩ ∣ 2 . (2)
A nonuniform quantum polynomial-time (QPT) machine { A λ } λ ∈ N \{A_\lambda\}_{\lambda\in\mathbb{N}} { A λ } λ ∈ N is a family of polynomial-size quantum circuits, where each circuit A λ A_\lambda A λ is provided with a polynomial-size quantum advice state ∣ α λ ⟩ \lvert\alpha_\lambda\rangle ∣ α λ ⟩ . Each A λ A_\lambda A λ induces a CPTP map. More generally, an interactive quantum machine can be modeled as a sequence of quantum channels acting on designated input, output, and internal registers.
Two probability distributions X X X and Y Y Y are computationally indistinguishable if there exists a negligible function negl ( λ ) \operatorname{negl}(\lambda) negl ( λ ) such that, for every QPT algorithm A λ A_\lambda A λ , it holds that
∣ Pr [ 1 ← A λ ( x ) : x ← X ] − Pr [ 1 ← A λ ( y ) : y ← Y ] ∣ ≤ negl ( λ ) . (3) \left|\Pr[1 \leftarrow A_\lambda(x) : x \leftarrow X] - \Pr[1 \leftarrow A_\lambda(y) : y \leftarrow Y]\right| \le\operatorname{negl}(\lambda). \tag*{(3)} ∣ Pr [ 1 ← A λ ( x ) : x ← X ] − Pr [ 1 ← A λ ( y ) : y ← Y ] ∣ ≤ negl ( λ ) . (3)
If the same condition holds for all, possibly unbounded, quantum algorithms, then X X X and Y Y Y are said to be statistically indistinguishable.
Technical assumptions
Definition 1 (Sparse-hit property). Let Π S K E = ( E n c , D e c ) \Pi_{\mathrm{SKE}} = (\mathrm{Enc},\mathrm{Dec}) Π SKE = ( Enc , Dec ) be a symmetric-key encryption scheme with ciphertext space C \mathcal{C} C . We say that Π S K E \Pi_{\mathrm{SKE}} Π SKE satisfies the sparse-hit property with parameter α max ( λ ) \alpha_{\max}(\lambda) α m a x ( λ ) , if, for every security parameter λ \lambda λ , every key k ∈ { 0 , 1 } λ k \in\{0,1\}^{\lambda} k ∈ { 0 , 1 } λ , and every polynomial-size subset S ⊆ C S \subseteq\mathcal{C} S ⊆ C ,
Pr x [ D e c ( x , k ) ∈ S ] ≤ ∣ S ∣ α max ( λ ) , (4) \Pr_x[\mathrm{Dec}(x,k) \in S] \le\lvert S\rvert\alpha_{\max}(\lambda), \tag*{(4)} x Pr [ Dec ( x , k ) ∈ S ] ≤ ∣ S ∣ α m a x ( λ ) , (4)
where the probability is taken over a random variable x x x taking values in C \mathcal{C} C .
Results
Honest-but-leaky model
In our protocol, the secret quantum state ∣ ψ ⟩ \lvert\psi\rangle ∣ ψ ⟩ is encoded into m m m quantum shares { ∣ s h i ⟩ } i ∈ [ 0 , m − 1 ] \{\lvert\mathrm{sh}_i\rangle\}_{i\in[0,m-1]} {∣ sh i ⟩ } i ∈ [ 0 , m − 1 ] , each associated with a unique tag { t a g i } i ∈ [ 0 , m − 1 ] \{\mathrm{tag}_i\}_{i\in[0,m-1]} { tag i } i ∈ [ 0 , m − 1 ] . These tags, stored in the auxiliary registers, serve as identifiers for the shares and are critical for subsequent leakage tracing and evidence verification. A set of at least k k k shares is sufficient to reconstruct the original secret ∣ ψ ⟩ \lvert\psi\rangle ∣ ψ ⟩ .
The leakage tracing procedure proceeds as follows: Assume a reconstruction box R \mathcal{R} R that contains f f f leaked shares and, given an additional k − f k-f k − f shares, reconstructs the secret ∣ ψ ⟩ \lvert\psi\rangle ∣ ψ ⟩ along with the associated auxiliary registers. Let I i d x ⊆ [ m ] \mathcal{I}_{\mathrm{idx}} \subseteq[m] I idx ⊆ [ m ] denote the index set of the leaked shares, and let T : = { t a g i ∣ i ∈ I i d x } \mathcal{T} := \{\mathrm{tag}_i \mid i \in\mathcal{I}_{\mathrm{idx}}\} T := { tag i ∣ i ∈ I idx } be the corresponding tag set. The verifier invokes R \mathcal{R} R , then uses the tracing key to decrypt the auxiliary registers and recover the corresponding tags, obtaining an evidence set T ′ \mathcal{T}' T ′ .
Finally, the verifier checks whether T ′ \mathcal{T}' T ′ satisfies the protocol’s verification conditions. If successful, T ′ \mathcal{T}' T ′ is accepted as valid evidence of the leaked shares, identifying the participants responsible for the leakage based on the uniqueness of the tags.
Security definitions
We define an LVT-QSS scheme that allows for the secure sharing of a quantum state ∣ ψ ⟩ \lvert\psi\rangle ∣ ψ ⟩ among m m m partic- icipants. ipants. The scheme is required to support secret reconstruction from any authorized subset of at least k k k shares, as well as leakage tracing and evidence verification through auxiliary tag information.
Formally, we model an LVT-QSS scheme by five QPT algorithms, Setup, GenSecretShares, SecretRecover, SecretTrace, and SecretVerify. Whenever convenient, we use assignment notation for their execution, e.g., ( t k , T a g s ) ← S e t u p ( 1 λ , m ) (tk, Tags) \leftarrow Setup(1^{\lambda}, m) ( t k , T a g s ) ← S e t u p ( 1 λ , m ) .
GenSecretShares: Given a quantum state ∣ ψ ⟩ \lvert\psi\rangle ∣ ψ ⟩ , the number of parties m m m , a threshold k k k , a tag set T a g s Tags T a g s , and the tracing key t k tk t k , the dealer generates m m m quantum shares { ∣ s h i ⟩ } i = 0 m − 1 \{\lvert sh_i\rangle\}_{i=0}^{m-1} {∣ s h i ⟩ } i = 0 m − 1 and the corresponding verification keys { v k i } i = 0 m − 1 \{vk_i\}_{i=0}^{m-1} { v k i } i = 0 m − 1 .
SecretRecover: Given a set of shares { ∣ s h i ⟩ } i ∈ P \{\lvert sh_i\rangle\}_{i\in P} {∣ s h i ⟩ } i ∈ P with P ⊆ [ m ] P \subseteq[m] P ⊆ [ m ] , the algorithm attempts to reconstruct the secret state ∣ ψ ⟩ \lvert\psi\rangle ∣ ψ ⟩ . If reconstruction fails, it outputs ⊥ \bot ⊥ .
SecretTrace: Given the tracing key t k tk t k and a set of quantum shares { ∣ s h i ⟩ } i ∈ Q ⊆ [ m ] ∖ I i d x \{\lvert sh_i\rangle\}_{i\in Q\subseteq[m]\setminus I_{\mathrm{idx}}} {∣ s h i ⟩ } i ∈ Q ⊆ [ m ] ∖ I idx with ∣ Q ∣ = k − f \lvert Q\rvert= k-f ∣ Q ∣ = k − f for some f < k f<k f < k , and oracle access to a reconstruction device R \mathcal{R} R built from f f f leaked shares, the tracer outputs a candidate evidence set I ′ \mathcal{I}' I ′ .
SecretVerify: Given the verification keys { v k i } i = 0 m − 1 \{vk_i\}_{i=0}^{m-1} { v k i } i = 0 m − 1 and a candidate evidence set I ′ \mathcal{I}' I ′ , the verifier outputs a bit b ∈ { 0 , 1 } b \in\{0,1\} b ∈ { 0 , 1 } indicating whether I ′ \mathcal{I}' I ′ satisfies the verification conditions.
Correctness requires that any authorized subset of at least k k k shares recover the original secret state up to negligible error in trace distance.
Definition 2 (Correctness (informal)). An LVT-QSS scheme is correct if any authorized subset P ⊆ [ m ] P \subseteq[m] P ⊆ [ m ] with ∣ P ∣ ≥ k \lvert P\rvert\ge k ∣ P ∣ ≥ k can recover the secret state with probability at least 1 − negl ( λ ) 1-\operatorname{negl}(\lambda) 1 − negl ( λ ) . Upon successful recovery, the reconstructed state is within trace distance at most negl ( λ ) \operatorname{negl}(\lambda) negl ( λ ) of the original secret state. A fully formal definition is given in Appendix B 1.
An LVT-QSS scheme is required to satisfy three central security properties: secrecy, traceability, and non-imputability. Secrecy is the standard threshold requirement that any subset of fewer than k k k parties obtains essentially no information about the secret. We formalize this requirement as follows.
Definition 3 (Secrecy (informal)). An LVT-QSS scheme satisfies secrecy if any unauthorized subset of fewer than k k k parties learns essentially no information about the secret state. A fully formal definition is given in Appendix B 2.
In a traceable secret-sharing scheme, secrecy must continue to hold even in the presence of the tracer. In particular, access to the tracing key t k tk t k should not weaken the secrecy guarantee. We formalize this stronger requirement below.
Definition 4 (Tracer secrecy (informal)). An LVT-QSS scheme satisfies tracer secrecy if any unauthorized subset of fewer than k k k parties obtains only negligible information about the shared secret state, even when the tracing key t k tk t k is available to it. A fully formal definition is given in Appendix B 3.
A leak-verifiable and traceable quantum secret-sharing scheme must satisfy traceability. Let I i d x ⊆ [ m ] I_{\mathrm{idx}} \subseteq[m] I idx ⊆ [ m ] be a coalition of leaked parties with ∣ I i d x ∣ = f < k \lvert I_{\mathrm{idx}}\rvert=f<k ∣ I idx ∣ = f < k , and let I \mathcal{I} I denote the corresponding tag set. Using the shares in its possession, the coalition may construct a black-box reconstruction procedure R \mathcal{R} R that takes as input an additional set of k − f k-f k − f shares and attempts to recover the secret state. Traceability requires that whenever such a reconstruction device succeeds with sufficiently high probability, a tracing algorithm given black-box access to R \mathcal{R} R can identify the coalition responsible for constructing R \mathcal{R} R .
To make this precise, let Q ⊆ [ m ] ∖ I i d x Q \subseteq[m]\setminus I_{\mathrm{idx}} Q ⊆ [ m ] ∖ I idx be a subset of size k − f k-f k − f , chosen uniformly at random from the parties outside the coalition. If, on input the shares { ∣ s h i ⟩ } i ∈ Q \{\lvert sh_i\rangle\}_{i\in Q} {∣ s h i ⟩ } i ∈ Q , the box R \mathcal{R} R outputs a state negligibly close to the original secret, then we regard R \mathcal{R} R as a good reconstruction box. We formalize this notion below.
Definition 5 (Good reconstruction boxes (informal)). A reconstruction box constructed from the leaked shares of a coalition of f < k f<k f < k parties is called good if, when supplemented with a uniformly random set of k − f k-f k − f shares from parties outside the coalition, it reconstructs the secret state up to negligible trace distance with probability at least ϵ \epsilon ϵ . A fully formal definition is given in Appendix B 4.
Definition 6 (Traceability (informal)). An LVT-QSS scheme is traceable if any useful reconstruction box constructed from leaked shares can be attributed to the coalition responsible for those shares; in particular, if the box reconstructs the secret using additional shares from parties outside the coalition, then the tracing procedure identifies the coalition’s tag set except with negligible probability. The full tracing experiment and formal definition are given in Appendix B 5.
Definition 7 (Non-imputability (informal)). An LVT-QSS scheme is non-imputable if accepted tracing evidence cannot falsely identify an honest participant as responsible for share leakage, except with negligible probability. The full non-imputability experiment and formal definition are given in Appendix B 6.
Leakage-verifiable and traceable quantum secret sharing protocol
The construction relies on standard cryptographic primitives. In particular, we use a quantum-secure collision-resistant and preimage-resistant hash function H H H and a post-quantum IND-CPA-secure symmetric-key encryption scheme Π S K E = ( E n c , D e c ) \Pi_{\mathrm{SKE}} = (\mathrm{Enc},\mathrm{Dec}) Π SKE = ( Enc , Dec ) . We further assume that Π S K E \Pi_{\mathrm{SKE}} Π SKE satisfies the sparse-hit property with parameter α max ( λ ) \alpha_{\max}(\lambda) α m a x ( λ ) . For a key k ∈ { 0 , 1 } λ k \in\{0,1\}^{\lambda} k ∈ { 0 , 1 } λ and a message m ∈ { 0 , 1 } ∗ m \in\{0,1\}^{*} m ∈ { 0 , 1 } ∗ , the encryption algorithm outputs a ciphertext c ← E n c ( m , k ) ∈ { 0 , 1 } ℓ ( ∣ m ∣ ) c \leftarrow\mathrm{Enc}(m,k) \in\{0,1\}^{\ell(|m|)} c ← Enc ( m , k ) ∈ { 0 , 1 } ℓ ( ∣ m ∣ ) , whereas the decryption algorithm D e c \mathrm{Dec} Dec , on input ( c , k ) (c,k) ( c , k ) , outputs either m m m or ⊥ \perp ⊥ .
For any QPT adversary A A A , let Adv A I N D - C P A ( λ ) \operatorname{Adv}^{\mathrm{IND\text{-}CPA}}_{A}(\lambda) Adv A IND - CPA ( λ ) denote the advantage of A A A in the post-quantum IND-CPA experiment against Π S K E \Pi_{\mathrm{SKE}} Π SKE . We assume that this advantage is negligible in the security parameter λ \lambda λ . We now describe the constituent algorithms in detail.
The dealer holds an arbitrary secret quantum state ∣ ψ ⟩ = ∑ s α s ∣ s ⟩ ∈ H λ |\psi\rangle= \sum_s \alpha_s|s\rangle\in\mathcal{H}_{\lambda} ∣ ψ ⟩ = ∑ s α s ∣ s ⟩ ∈ H λ . The goal of the LVT-QSS scheme is to securely share this quantum state among m m m parties, such that any subset of at least k k k parties can later reconstruct the state. The process of sharing the quantum state involves two main steps: setting up the system parameters and generating the secret shares. These algorithms ensure that the shares are distributed securely and that the secret state can be reconstructed only by authorized parties.
Protocol: Initialization and share generation in LVT-QSS
1. Setup(1 λ , m 1^\lambda,m 1 λ , m ). On input the security parameter 1 λ 1^\lambda 1 λ and the number of parties m m m :
Sample distinct tags t a g 0 , … , t a g m − 1 ← $ F tag_0,\ldots,tag_{m-1} \mathrel{\stackrel{\$}{\leftarrow}} \mathbb{F} t a g 0 , … , t a g m − 1 ← $ F , and set T a g s : = { t a g 0 , … , t a g m − 1 } Tags := \{tag_0,\ldots,tag_{m-1}\} T a g s := { t a g 0 , … , t a g m − 1 } .
Sample a tracing key t k ← $ { 0 , 1 } λ tk \mathrel{\stackrel{\$}{\leftarrow}} \{0,1\}^{\lambda} t k ← $ { 0 , 1 } λ .
2. GenSecretShares(∣ ψ ⟩ , m , k , T a g s , t k |\psi\rangle,m,k,Tags,tk ∣ ψ ⟩ , m , k , T a g s , t k ). On input a secret state ∣ ψ ⟩ |\psi\rangle ∣ ψ ⟩ , parameters m m m and k k k , the tag set T a g s Tags T a g s , and the tracing key t k tk t k :
Let F = Z q \mathbb{F}=\mathbb{Z}_q F = Z q , where q q q is prime and ⌈ log 2 q ⌉ = λ \lceil\log_2 q\rceil=\lambda ⌈ log 2 q ⌉ = λ . Sample m m m distinct elements x 0 , … , x m − 1 ∈ F x_0,\ldots,x_{m-1}\in\mathbb{F} x 0 , … , x m − 1 ∈ F , and a random key u k ← $ F u_k \mathrel{\stackrel{\$}{\leftarrow}} \mathbb{F} u k ← $ F .
For each i ∈ { 0 , … , m − 1 } i\in\{0,\ldots,m-1\} i ∈ { 0 , … , m − 1 } , compute c t i ← E n c ( t a g i , t k ) ct_i\leftarrow\mathrm{Enc}(tag_i,tk) c t i ← Enc ( t a g i , t k ) , v k i ← H ( t a g i ) vk_i\leftarrow H(tag_i) v k i ← H ( t a g i ) , and r i ← E n c ( c t i , u k ) r_i\leftarrow\mathrm{Enc}(ct_i,u_k) r i ← Enc ( c t i , u k ) .
For any vector c = ( c 0 , … , c k − 1 ) ∈ F k \mathbf{c}=(c_0,\ldots,c_{k-1})\in\mathbb{F}^k c = ( c 0 , … , c k − 1 ) ∈ F k , define p c ( t ) = c 0 + c 1 t + ⋯ + c k − 1 t k − 1 p_{\mathbf{c}}(t)=c_0+c_1t+\cdots+c_{k-1}t^{k-1} p c ( t ) = c 0 + c 1 t + ⋯ + c k − 1 t k − 1 .
Encode the secret state as
∣ ψ ⟩ ↦ ∑ s α s ∑ c ∈ F k c 0 = u k , c k − 1 = s ∣ p c ( x 0 ) , r 0 ⟩ ⊗ ⋯ ⊗ ∣ p c ( x m − 1 ) , r m − 1 ⟩ . |\psi\rangle\mapsto\sum_s \alpha_s \sum_{\substack{\mathbf{c}\in\mathbb{F}^k\\c_0=u_k,\ c_{k-1}=s}} |p_{\mathbf{c}}(x_0),r_0\rangle\otimes\cdots\otimes|p_{\mathbf{c}}(x_{m-1}),r_{m-1}\rangle. ∣ ψ ⟩ ↦ s ∑ α s c ∈ F k c 0 = u k , c k − 1 = s ∑ ∣ p c ( x 0 ) , r 0 ⟩ ⊗ ⋯ ⊗ ∣ p c ( x m − 1 ) , r m − 1 ⟩ .
Initialize registers ( R 0 , A 0 ) , … , ( R m − 1 , A m − 1 ) (R_0,A_0),\ldots,(R_{m-1},A_{m-1}) ( R 0 , A 0 ) , … , ( R m − 1 , A m − 1 ) according to the above state. Denote the quantum share in register pair ( R i , A i ) (R_i,A_i) ( R i , A i ) by ∣ s h i ⟩ |sh_i\rangle ∣ s h i ⟩ for each i ∈ { 0 , … , m − 1 } i\in\{0,\ldots,m-1\} i ∈ { 0 , … , m − 1 } .
We now describe the recovery algorithm. Given any authorized set containing at least k k k valid shares, the algorithm reconstructs the secret quantum state. The recovery process involves selecting k k k valid shares from the set, applying a Vandermonde transform to reconstruct the secret, and removing any residual dependencies to fully recover the state.
Protocol: Secret recovery in LVT-QSS
3. SecretRecover({ ∣ s h i ⟩ } i ∈ P \{|sh_i\rangle\}_{i\in P} { ∣ s h i ⟩ } i ∈ P ). On input a set of shares indexed by P ⊆ [ m ] P\subseteq[m] P ⊆ [ m ] :
If ∣ P ∣ < k |P|<k ∣ P ∣ < k , output ⊥ \perp ⊥ . Otherwise, choose a subset P ′ ⊆ P P'\subseteq P P ′ ⊆ P such that ∣ P ′ ∣ = k |P'|=k ∣ P ′ ∣ = k . Without loss of generality, relabel the corresponding register pairs as ( R 0 , A 0 ) , … , ( R k − 1 , A k − 1 ) (R_0,A_0),\ldots,(R_{k-1},A_{k-1}) ( R 0 , A 0 ) , … , ( R k − 1 , A k − 1 ) .
Apply the inverse Vandermonde transform V k ( x 0 , … , x k − 1 ) − 1 V_k(x_0,\ldots,x_{k-1})^{-1} V k ( x 0 , … , x k − 1 ) − 1 to registers R 0 , … , R k − 1 R_0,\ldots,R_{k-1} R 0 , … , R k − 1 .
Cyclically right-shift the k k k register pairs ( R 0 , A 0 ) , … , ( R k − 1 , A k − 1 ) (R_0,A_0),\ldots,(R_{k-1},A_{k-1}) ( R 0 , A 0 ) , … , ( R k − 1 , A k − 1 ) by one position.
Copy R 1 R_1 R 1 into an ancilla register B B B via ∣ u k ⟩ R 1 ∣ 0 ⟩ B ↦ ∣ u k ⟩ R 1 ∣ u k ⟩ B |u_k\rangle_{R_1}|0\rangle_B\mapsto|u_k\rangle_{R_1}|u_k\rangle_B ∣ u k ⟩ R 1 ∣0 ⟩ B ↦ ∣ u k ⟩ R 1 ∣ u k ⟩ B .
Apply the linear transform V k − 1 ( x k , … , x m − 1 ) V_{k-1}(x_k,\ldots,x_{m-1}) V k − 1 ( x k , … , x m − 1 ) to registers R 1 , … , R k − 1 R_1,\ldots,R_{k-1} R 1 , … , R k − 1 .
For each i = 1 , … , k − 1 i=1,\ldots,k-1 i = 1 , … , k − 1 , remove the residual dependence by adding R 0 ⋅ ( x k + i − 1 ) k − 1 R_0\cdot(x_{k+i-1})^{k-1} R 0 ⋅ ( x k + i − 1 ) k − 1 to register R i R_i R i .
Output the content of register R 0 R_0 R 0 as the recovered secret state.
We next describe the tracing and verification algorithms. First, the tracing algorithm takes as input the tracing key and a set of valid leaked shares, and extracts the identities of the leaking parties by tracing the shares back to their corresponding parties. Then, the verification algorithm takes the verification keys and a candidate identity set I ′ \mathcal{I}' I ′ returned by the tracing algorithm, and verifies whether the traced identities are valid by checking them against the verification keys.
Protocol: Secret tracing and verification in LVT-QSS
4. SecretTrace(t k , { ∣ s h i ⟩ } i ∈ Q tk,\{|sh_i\rangle\}_{i\in Q} t k , { ∣ s h i ⟩ } i ∈ Q ). On input a tracing key t k tk t k and a collection of valid shares indexed by a set Q ⊆ [ m ] ∖ I i d x Q\subseteq[m]\setminus I_{\mathrm{idx}} Q ⊆ [ m ] ∖ I idx with ∣ Q ∣ = k − f |Q|=k-f ∣ Q ∣ = k − f :
For each i ∈ Q i\in Q i ∈ Q , copy the content of A i A_i A i into an ancilla register C i C_i C i : ∣ r i ⟩ A i ∣ 0 ⟩ C i ↦ ∣ r i ⟩ A i ∣ r i ⟩ C i |r_i\rangle_{A_i}|0\rangle_{C_i}\mapsto|r_i\rangle_{A_i}|r_i\rangle_{C_i} ∣ r i ⟩ A i ∣0 ⟩ C i ↦ ∣ r i ⟩ A i ∣ r i ⟩ C i .
Feed the register pairs { ( R i , A i ) } i ∈ Q \{(R_i,A_i)\}_{i\in Q} {( R i , A i ) } i ∈ Q into the reconstruction box R \mathcal{R} R , which outputs an ancilla register B B B and auxiliary registers A ~ 0 , … , A ~ k − 1 \widetilde{A}_0,\ldots,\widetilde{A}_{k-1} A 0 , … , A k − 1 .
Measure B B B to obtain u k u_k u k , and measure A ~ 0 , … , A ~ k − 1 \widetilde{A}_0,\ldots,\widetilde{A}_{k-1} A 0 , … , A k − 1 to obtain { r i } i = 0 k − 1 \{r_i\}_{i=0}^{k-1} { r i } i = 0 k − 1 . Set I ← { r i } i = 0 k − 1 I\leftarrow\{r_i\}_{i=0}^{k-1} I ← { r i } i = 0 k − 1 .
Measure each C i C_i C i to obtain r i ′ r'_i r i ′ and set I ′ ′ ← { r i ′ } i ∈ Q I''\leftarrow\{r'_i\}_{i\in Q} I ′′ ← { r i ′ } i ∈ Q .
Update I ← I ∖ I ′ ′ I\leftarrow I\setminus I'' I ← I ∖ I ′′ and output
I ′ ← { D e c ( D e c ( r , u k ) , t k ) : r ∈ I } . \mathcal{I}'\leftarrow\{\mathrm{Dec}(\mathrm{Dec}(r,u_k),tk):r\in I\}. I ′ ← { Dec ( Dec ( r , u k ) , t k ) : r ∈ I } .
5. SecretVerify ({ v k i } i = 0 m − 1 , I ′ \{vk_i\}_{i=0}^{m-1}, \mathcal{I}' { v k i } i = 0 m − 1 , I ′ ). On input the verification keys { v k i } i = 0 m − 1 \{vk_i\}_{i=0}^{m-1} { v k i } i = 0 m − 1 and a candidate evidence set I ′ \mathcal{I}' I ′ :
If ∣ I ′ ∣ ≠ f |\mathcal{I}'| \ne f ∣ I ′ ∣ = f , output ⊥ \perp ⊥ .
Enumerate I ′ = { t a g 1 , … , t a g f } \mathcal{I}' = \{\mathrm{tag}_1,\ldots,\mathrm{tag}_f\} I ′ = { tag 1 , … , tag f } . For each t a g ∈ I ′ \mathrm{tag} \in\mathcal{I}' tag ∈ I ′ , compute v : = H ( t a g ) v := H(\mathrm{tag}) v := H ( tag ) . If v ∉ { v k i } i = 0 m − 1 v \notin\{vk_i\}_{i=0}^{m-1} v ∈ / { v k i } i = 0 m − 1 , output ⊥ \perp ⊥ .
Otherwise, output 1.
Proof
Theorem 8. The ( k , m ) (k,m) ( k , m ) -threshold LVT-QSS scheme is correct.
Proof sketch. Correctness follows from the linear structure of the coherent threshold encoding. The shares are evaluations of a degree-( k − 1 ) (k-1) ( k − 1 ) polynomial over distinct field points, with the secret embedded in one coefficient. Any authorized set of at least k k k shares contains k k k evaluations that define an invertible Vandermonde system, allowing the reconstruction procedure to recover the secret coefficient by a reversible linear transformation. Hence the recovered state is negligibly close to the original secret state except with negligible probability. The complete proof is given in Appendix C 1.
Theorem 9. The ( k , m ) (k,m) ( k , m ) -threshold LVT-QSS scheme satisfies secrecy.
Proof sketch. Secrecy follows from the random degrees of freedom in the coherent polynomial encoding. For a fixed secret basis value s s s , the coefficient c k − 1 = s c_{k-1}=s c k − 1 = s is fixed, while the remaining coefficients, including c 0 = u k c_0=u_k c 0 = u k , are sampled independently of s s s . Thus, any unauthorized set M M M with ∣ M ∣ < k |M|<k ∣ M ∣ < k observes fewer than k k k evaluations of a degree-( k − 1 ) (k-1) ( k − 1 ) polynomial whose remaining k − 1 k-1 k − 1 coefficients are uniformly random. The induced distribution of the evaluations seen by M M M is therefore uniform and independent of s s s . After tracing out the purification environment and the registers outside M M M , the reduced state on the adversary’s view is independent of the secret state. Hence any measurement on fewer than k k k shares has only negligible distinguishing advantage. The complete proof is given in Appendix C 2.
Theorem 10. The ( k , m ) (k,m) ( k , m ) -threshold LVT-QSS scheme satisfies tracer secrecy.
Proof sketch. The share registers R M R_M R M of any unauthorized subset M M M , with ∣ M ∣ < k |M|<k ∣ M ∣ < k , are already independent of the secret by secrecy of the underlying threshold sharing. The auxiliary registers A M A_M A M contain only tracing-related data generated from the tracing key, local randomness, and the user key, all of which are independent of the secret state. Therefore, even if the tracing key is included as a classical register T T T , the joint state on V i e w M ⊗ T \mathrm{View}_M \otimes T View M ⊗ T is independent of which secret was shared. Hence the distinguishing advantage of any unauthorized subset is negligible. The complete proof is given in Appendix C 3.
Theorem 11 (Informal). Assume that H : F → F H : \mathbb{F} \to\mathbb{F} H : F → F is quantum-secure collision-resistant and preimage-resistant, and that the symmetric-key encryption scheme Π S K E = ( E n c , D e c ) \Pi_{\mathrm{SKE}}=(\mathrm{Enc},\mathrm{Dec}) Π SKE = ( Enc , Dec ) satisfies the sparse-hit property with negligible parameter α max ( λ ) \alpha_{\max}(\lambda) α m a x ( λ ) . If the number of sparse-hit trials is polynomially bounded in λ \lambda λ , then the LVT-QSS scheme is traceable against any QPT adversary: every useful reconstruction box constructed from leaked shares can be traced to the coalition that created it, except with negligible probability. *
Proof sketch. A successful tracing attack must produce a good reconstruction box while causing either a valid tracing output to be rejected or an incorrect tag set to be accepted. The first case is ruled out by the completeness of the verification procedure. In the second case, the accepted tag set either contains a forged tag, which yields a collision under H H H , or contains an honest tag accepted through a sparse-hit event in the encryption layer. Collision resistance and the negligible sparse-hit probability bound these cases, and a union bound over polynomially many trials gives negligible tracing advantage. The complete proof is given in Appendix C 4.
Theorem 12 (Informal). Assume that H : F → F H : \mathbb{F} \to\mathbb{F} H : F → F is quantum-secure collision-resistant and preimage-resistant. Then the LVT-QSS scheme is non-imputabile against any QPT adversary: no honest participant can be falsely accused of being a leaker, except with negligible probability.
Proof sketch. The proof reduces any successful non-imputability attack to either finding a preimage or a collision for H H H . We replace the verification key of the challenged honest party by an independently sampled hash value y ∗ = H ( w ∗ ) y^*=H(w^*) y ∗ = H ( w ∗ ) , which is identically distributed to the real key. If an adversary nevertheless causes this honest party to be falsely implicated, then the accepted tag must either hash to y ∗ y^* y ∗ , giving a preimage of the challenge, or hash to the verification key of another party, giving a collision in H H H . Since H H H is quantum-secure preimage resistant and collision resistant, both events occur only with negligible probability. The complete proof is given in Appendix C 5.
Malicious-but-accountable model
We now consider a malicious-but-accountable reconstruction model. Let V : = { t a g i ∣ i ∈ V i d x } V := \{\mathrm{tag}_i \mid i \in V_{\mathrm{idx}}\} V := { tag i ∣ i ∈ V idx } and U : = { t a g i ∣ i ∈ U i d x } U := \{\mathrm{tag}_i \mid i \in U_{\mathrm{idx}}\} U := { tag i ∣ i ∈ U idx } denote the malicious and honest tag sets, respectively. Here V i d x , U i d x = [ m ] V_{\mathrm{idx}},U_{\mathrm{idx}}=[m] V idx , U idx = [ m ] are the corresponding index sets, with ∣ V i d x ∣ = t < k |V_{\mathrm{idx}}|=t<k ∣ V idx ∣ = t < k . Unlike in the honest-reconstruction setting, malicious parties may submit forged shares, and hence the reconstruction-box abstraction is insufficient. Instead, reconstruction must be modeled explicitly, and tracing is performed with respect to the auxiliary information generated during the reconstruction procedure. The condition t < k t < k t < k is essential: if t ≥ k t \ge k t ≥ k , then the malicious parties can reconstruct and leak the secret using only their own shares, so no nontrivial tracing guarantee can be required in general. We therefore restrict attention to the regime t < k t < k t < k .
In this model, the role of tracing is to provide accountability. More precisely, the tracer produces publicly verifiable compliance proofs for parties that behaved honestly during reconstruction, thereby excluding them as suspects and isolating the malicious parties responsible for submitting forged shares. The corresponding notions of traceability and non-imputability are formalized in Sec. III B 1.
Security definitions
We define an MTA-QSS scheme for securely sharing a quantum state ∣ ψ ⟩ = ∑ s α s ∣ s ⟩ |\psi\rangle= \sum_s \alpha_s|s\rangle ∣ ψ ⟩ = ∑ s α s ∣ s ⟩ among m m m parties in the malicious-but-accountable setting. The scheme is required to support secret reconstruction from any subset of at least k k k shares, together with tracing and public verification based on the auxiliary information generated during reconstruction.
Formally, an MTA-QSS scheme is specified by the following five QPT algorithms.
Setup: Given the security parameter 1 λ 1^\lambda 1 λ and the number of parties m m m , the trusted authority generates a tracing key set { t k i } i = 0 m − 1 \{tk_i\}_{i=0}^{m-1} { t k i } i = 0 m − 1 and a tag set T a g s = { t a g i } i = 0 m − 1 Tags = \{tag_i\}_{i=0}^{m-1} T a g s = { t a g i } i = 0 m − 1 .
GenSecretShares: Given a secret quantum state ∣ ψ ⟩ |\psi\rangle ∣ ψ ⟩ , the number of parties m m m , the threshold parameter k k k , the tag set T a g s Tags T a g s , and the tracing keys { t k i } i = 0 m − 1 \{tk_i\}_{i=0}^{m-1} { t k i } i = 0 m − 1 , the dealer generates the quantum shares { ∣ s h i ⟩ } i = 0 m − 1 \{|sh_i\rangle\}_{i=0}^{m-1} { ∣ s h i ⟩ } i = 0 m − 1 together with the verification keys { v k i } i = 0 m − 1 \{vk_i\}_{i=0}^{m-1} { v k i } i = 0 m − 1 , the auxiliary key u k uk u k , and the check key c k ck c k .
SecretRecover: Given the shares indexed by a set P ⊆ [ m ] P \subseteq[m] P ⊆ [ m ] , the algorithm outputs either a reconstructed quantum state together with a tracing transcript I I I , or the failure symbol ⊥ \perp ⊥ .
SecretTrace: Given the tracing keys { t k i } i = 0 m − 1 \{tk_i\}_{i=0}^{m-1} { t k i } i = 0 m − 1 , the auxiliary key u k uk u k , and the tracing transcript I I I , the tracing algorithm outputs two sets U ′ U' U ′ and V ′ V' V ′ .
SecretVerify: Given the verification keys { v k i } i = 0 m − 1 \{vk_i\}_{i=0}^{m-1} { v k i } i = 0 m − 1 , the auxiliary key u k uk u k , the check key c k ck c k , the sets U ′ U' U ′ and V ′ V' V ′ , and the tracing transcript I I I , the verification algorithm outputs a bit b ∈ { 0 , 1 } b \in\{0,1\} b ∈ { 0 , 1 } , where b = 1 b = 1 b = 1 if and only if ( U ′ , V ′ ) (U', V') ( U ′ , V ′ ) satisfies the scheme’s verification condition.
Correctness for an MTA-QSS scheme is defined in the usual threshold sense: any subset of at least k k k valid shares reconstructs the secret.
Definition 13 (Correctness (informal)). An MTA-QSS scheme is correct if any subset P ⊆ [ m ] P \subseteq[m] P ⊆ [ m ] with ∣ P ∣ ≥ k |P| \ge k ∣ P ∣ ≥ k , using honestly generated shares, can reconstruct a state that is within trace distance at most negl ( λ ) \operatorname{negl}(\lambda) negl ( λ ) of the original secret state with probability at least 1 − negl ( λ ) 1-\operatorname{negl}(\lambda) 1 − negl ( λ ) . No correctness guarantee is required when some of the input shares are forged or adversarially corrupted. A fully formal definition is given in Appendix D1.
An MTA-QSS scheme is required to satisfy three security properties: secrecy, traceability, and non-imputability. Among them, secrecy is the basic confidentiality requirement, namely that any set of fewer than k k k parties obtains no information about the secret. In the malicious-but-accountable setting, we adopt the general secrecy notion of Definition 3.
Definition 14 (Tracer secrecy (informal)). An MTA-QSS scheme satisfies tracer secrecy if any subset M ⊆ [ m ] M \subseteq[m] M ⊆ [ m ] with ∣ M ∣ < k |M| < k ∣ M ∣ < k learns essentially no information about the secret state, even when given access to the tracing keys and the auxiliary key u k uk u k . The fully formal definition is given in Appendix D2.
Definition 15 (Traceability (informal)). An MTA-QSS scheme is traceable if the honest parties contributing valid shares can be identified during reconstruction, from which the parties who submitted forged shares can be inferred. The full tracing experiment and formal definition are given in Appendix D3.
Definition 16 (Non-imputability (informal)). An MTA-QSS scheme is non-imputable if the evidence generated during reconstruction cannot falsely attribute a forged share to any honest party contributing a valid share. The full non-imputability experiment and formal definition are given in Appendix D4.
Malicious-traceable and accountable quantum secret sharing protocol
We next present the malicious-traceable and accountable quantum secret sharing protocol. As in the LVT-QSS construction, it is built from the same underlying cryptographic primitives and relies on the same security assumptions. The protocol consists of five phases: setup, share generation, recovery, tracing, and verification.
The dealer holds an arbitrary secret quantum state ∣ ψ ⟩ = ∑ s α s ∣ s ⟩ ∈ H λ |\psi\rangle= \sum_s \alpha_s|s\rangle\in\mathcal{H}_\lambda ∣ ψ ⟩ = ∑ s α s ∣ s ⟩ ∈ H λ . We begin by describing the initialization and share-generation phases of the MTA-QSS scheme. Given a secret quantum state, these procedures generate the system parameters and encode the secret into m m m distributed quantum shares. The recovery, tracing, and verification phases will be presented subsequently.
Protocol: Initialization and share generation of MTA-QSS
Setup ( 1 λ , m ) (1^\lambda,m) ( 1 λ , m ) . On input the security parameter 1 λ 1^\lambda 1 λ and the number of parties m m m , the setup proceeds as follows:
Sample m m m distinct tags t a g 0 , … , t a g m − 1 ← $ F tag_0,\ldots,tag_{m-1} \mathrel{\overset{\$}{\leftarrow}} \mathbb{F} t a g 0 , … , t a g m − 1 ← $ F and set
T a g s : = { t a g 0 , … , t a g m − 1 } . Tags := \{tag_0,\ldots,tag_{m-1}\}. T a g s := { t a g 0 , … , t a g m − 1 } .
Choose m m m pairwise distinct field elements g 0 , … , g m − 1 ∈ F g_0,\ldots,g_{m-1}\in\mathbb{F} g 0 , … , g m − 1 ∈ F , and compute
t k i : = H ( g i ) , i = 0 , … , m − 1 , tk_i := H(g_i), \qquad i=0,\ldots,m-1, t k i := H ( g i ) , i = 0 , … , m − 1 ,
where each t k i tk_i t k i is encoded as a λ \lambda λ -bit string with λ = ⌈ log 2 q ⌉ \lambda=\lceil\log_2 q\rceil λ = ⌈ log 2 q ⌉ .
GenSecretShares ( ∣ ψ ⟩ , m , k , T a g s , { t k i } i = 0 m − 1 ) (|\psi\rangle,m,k,Tags,\{tk_i\}_{i=0}^{m-1}) ( ∣ ψ ⟩ , m , k , T a g s , { t k i } i = 0 m − 1 ) . On input a secret state ∣ ψ ⟩ |\psi\rangle ∣ ψ ⟩ , the parameters m m m and k k k , the tag set T a g s Tags T a g s , and the tracing key set { t k i } i = 0 m − 1 \{tk_i\}_{i=0}^{m-1} { t k i } i = 0 m − 1 , proceed as follows:
Select m m m distinct elements x 0 , … , x m − 1 ∈ F x_0,\ldots,x_{m-1}\in\mathbb{F} x 0 , … , x m − 1 ∈ F .
Sample an auxiliary key u k ← $ F uk\mathrel{\overset{\$}{\leftarrow}}\mathbb{F} u k ← $ F .
Compute the check key c k : = H ( ⨁ i = 0 m − 1 t k i ) ck:=H\left(\bigoplus_{i=0}^{m-1}tk_i\right) c k := H ( ⨁ i = 0 m − 1 t k i ) .
For each i ∈ { 0 , … , m − 1 } i\in\{0,\ldots,m-1\} i ∈ { 0 , … , m − 1 } , compute
c t i ← Enc ( t a g i , c k ) , v k i ← H ( t a g i ) , and r i ← Enc ( c t i , u k ) . ct_i\leftarrow\operatorname{Enc}(tag_i,ck),\quad vk_i\leftarrow H(tag_i),\quad\text{and}\quad r_i\leftarrow\operatorname{Enc}(ct_i,uk). c t i ← Enc ( t a g i , c k ) , v k i ← H ( t a g i ) , and r i ← Enc ( c t i , u k ) .
Let F = Z q \mathbb{F}=\mathbb{Z}_q F = Z q . For any vector c = ( c 0 , … , c k − 1 ) ∈ F k c=(c_0,\ldots,c_{k-1})\in\mathbb{F}^k c = ( c 0 , … , c k − 1 ) ∈ F k , define the polynomial p c ( t ) = c 0 + c 1 t + ⋯ + c k − 1 t k − 1 p_c(t)=c_0+c_1t+\cdots+c_{k-1}t^{k-1} p c ( t ) = c 0 + c 1 t + ⋯ + c k − 1 t k − 1 .
Encode the secret state as
∣ ψ ⟩ ↦ ∑ s α s ∑ c ∈ F k c 0 = u k , c k − 1 = s ⨂ i = 0 m − 1 ∣ p c ( x i ) , r i ∥ t k i ⟩ . |\psi\rangle\mapsto\sum_s\alpha_s\sum_{\substack{c\in\mathbb{F}^k\\c_0=uk,\ c_{k-1}=s}}\bigotimes_{i=0}^{m-1}|p_c(x_i),r_i\Vert tk_i\rangle. ∣ ψ ⟩ ↦ s ∑ α s c ∈ F k c 0 = u k , c k − 1 = s ∑ i = 0 ⨂ m − 1 ∣ p c ( x i ) , r i ∥ t k i ⟩ .
Initialize register pairs ( R i , A i ) (R_i,A_i) ( R i , A i ) so that each pair contains the corresponding share and auxiliary information. Denote the quantum share in the i i i th register pair by ∣ s h i ⟩ |sh_i\rangle ∣ s h i ⟩ .
We next present the secret-recovery phase of the MTA-QSS scheme. For any subset of at least k k k shares, the procedure reconstructs the secret quantum state and simultaneously extracts the auxiliary classical information I I I . This auxiliary output is subsequently used for tracing and verification.
Protocol: Secret recovery in MTA-QSS
SecretRecover ( { ∣ s h i ⟩ } i ∈ P ) (\{|sh_i\rangle\}_{i\in P}) ({ ∣ s h i ⟩ } i ∈ P ) . On input a set of shares indexed by P ⊆ [ m ] P\subseteq[m] P ⊆ [ m ] , proceed as follows:
If ∣ P ∣ < k |P|<k ∣ P ∣ < k , output ⊥ \perp ⊥ . Otherwise, choose any subset P ′ ⊆ P P'\subseteq P P ′ ⊆ P of size k k k and relabel the corresponding register pairs as ( R 0 , A 0 ) , … , ( R k − 1 , A k − 1 ) (R_0,A_0),\ldots,(R_{k-1},A_{k-1}) ( R 0 , A 0 ) , … , ( R k − 1 , A k − 1 ) .
Apply the inverse Vandermonde transform V k ( x 0 , … , x k − 1 ) − 1 V_k(x_0,\ldots,x_{k-1})^{-1} V k ( x 0 , … , x k − 1 ) − 1 to the registers R 0 , … , R k − 1 R_0,\ldots,R_{k-1} R 0 , … , R k − 1 .
Cyclically right-shift the k k k register pairs to obtain ( ( R k − 1 , A k − 1 ) , ( R 0 , A 0 ) , … , ( R k − 2 , A k − 2 ) ) ((R_{k-1},A_{k-1}),(R_0,A_0),\ldots,(R_{k-2},A_{k-2})) (( R k − 1 , A k − 1 ) , ( R 0 , A 0 ) , … , ( R k − 2 , A k − 2 )) .
Apply the linear transform V k − 1 ( x k , … , x m − 1 ) V_{k-1}(x_k,\ldots,x_{m-1}) V k − 1 ( x k , … , x m − 1 ) to the registers R 1 , … , R k − 1 R_1,\ldots,R_{k-1} R 1 , … , R k − 1 .
Remove the residual dependence by adding R 0 ⋅ ( x k + i − 1 ) k − 1 R_0\cdot(x_{k+i-1})^{k-1} R 0 ⋅ ( x k + i − 1 ) k − 1 to R i R_i R i for each i = 1 , … , k − 1 i=1,\ldots,k-1 i = 1 , … , k − 1 .
Measure the ancillary registers A 0 , … , A k − 1 A_0,\ldots,A_{k-1} A 0 , … , A k − 1 to obtain the classical outcomes r i ∥ t k i r_i\Vert tk_i r i ∥ t k i , and define I : = { r j ∥ t k j } j = 0 k − 1 I:=\{r_j\Vert tk_j\}_{j=0}^{k-1} I := { r j ∥ t k j } j = 0 k − 1 .
Output the content of R 0 R_0 R 0 as the recovered secret state.
We next describe the tracing and verification phases of the MTA-QSS scheme. Given the auxiliary classical information I I I obtained during recovery, the tracing procedure extracts the associated tags and partitions them according to the tracing key. The verification procedure then checks that the recovered tags are consistent with the verification keys, thereby validating the traced evidence.
Protocol: Secret tracing and verification in MTA-QSS
SecretTrace ( { t k i } i = 0 m − 1 , u k , I ) (\{tk_i\}_{i=0}^{m-1},uk,I) ({ t k i } i = 0 m − 1 , u k , I ) . On input a tracing key set { t k i } i = 0 m − 1 \{tk_i\}_{i=0}^{m-1} { t k i } i = 0 m − 1 , the auxiliary key u k uk u k , and a classical information set I I I , proceed as follows:
Compute the check key c k : = H ( ⨁ i = 0 m − 1 t k i ) ck:=H\left(\bigoplus_{i=0}^{m-1}tk_i\right) c k := H ( ⨁ i = 0 m − 1 t k i ) .
For each I j ∈ I I_j\in I I j ∈ I , let I j ( λ ) I_j^{(\lambda)} I j ( λ ) denote the last λ \lambda λ bits of I j I_j I j . Partition I I I into
U : = { I j ∣ I j ( λ ) ∈ { t k i } i = 0 m − 1 } \mathcal{U}:=\{I_j\mid I_j^{(\lambda)}\in\{tk_i\}_{i=0}^{m-1}\} U := { I j ∣ I j ( λ ) ∈ { t k i } i = 0 m − 1 }
and
V : = { I j ∣ I j ( λ ) ∉ { t k i } i = 0 m − 1 } . \mathcal{V}:=\{I_j\mid I_j^{(\lambda)}\notin\{tk_i\}_{i=0}^{m-1}\}. V := { I j ∣ I j ( λ ) ∈ / { t k i } i = 0 m − 1 } .
c t j : = Dec ( r j , u k ) , t a g j : = Dec ( c t j , c k ) . ct_j:=\operatorname{Dec}(r_j,uk),\qquad tag_j:=\operatorname{Dec}(ct_j,ck). c t j := Dec ( r j , u k ) , t a g j := Dec ( c t j , c k ) .
U ′ : = { t a g j ∣ I j ∈ U } , V ′ : = { t a g j ∣ I j ∈ V } . U':=\{tag_j\mid I_j\in\mathcal{U}\},\qquad V':=\{tag_j\mid I_j\in\mathcal{V}\}. U ′ := { t a g j ∣ I j ∈ U } , V ′ := { t a g j ∣ I j ∈ V } .
SecretVerify ( { v k i } i = 0 m − 1 , u k , c k , U ′ , V ′ , I ) (\{vk_i\}_{i=0}^{m-1},uk,ck,U',V',I) ({ v k i } i = 0 m − 1 , u k , c k , U ′ , V ′ , I ) . On input the verification key set { v k i } i = 0 m − 1 \{vk_i\}_{i=0}^{m-1} { v k i } i = 0 m − 1 , the auxiliary key u k uk u k , the check key c k ck c k , the sets U ′ U' U ′ and V ′ V' V ′ , and the classical information set I I I , proceed as follows:
U ′ ′ : = { Enc ( Enc ( t a g z , c k ) , u k ) ∣ t a g z ∈ U ′ } , U'':=\{\operatorname{Enc}(\operatorname{Enc}(tag_z,ck),uk)\mid tag_z\in U'\}, U ′′ := { Enc ( Enc ( t a g z , c k ) , u k ) ∣ t a g z ∈ U ′ } ,
V ′ ′ : = { Enc ( Enc ( t a g z , c k ) , u k ) ∣ t a g z ∈ V ′ } . V'':=\{\operatorname{Enc}(\operatorname{Enc}(tag_z,ck),uk)\mid tag_z\in V'\}. V ′′ := { Enc ( Enc ( t a g z , c k ) , u k ) ∣ t a g z ∈ V ′ } .
If U ′ ′ ∪ V ′ ′ ≠ { r j } j = 0 k − 1 U''\cup V''\ne\{r_j\}_{j=0}^{k-1} U ′′ ∪ V ′′ = { r j } j = 0 k − 1 , output ⊥ \perp ⊥ .
If there exists t a g z ∈ V ′ tag_z\in V' t a g z ∈ V ′ such that H ( t a g z ) ∈ { v k i } i = 0 m − 1 H(tag_z)\in\{vk_i\}_{i=0}^{m-1} H ( t a g z ) ∈ { v k i } i = 0 m − 1 , output ⊥ \perp ⊥ .
If for all t a g z ∈ U ′ tag_z\in U' t a g z ∈ U ′ , H ( t a g z ) ∈ { v k i } i = 0 m − 1 H(tag_z)\in\{vk_i\}_{i=0}^{m-1} H ( t a g z ) ∈ { v k i } i = 0 m − 1 , output 1 1 1 ; otherwise output ⊥ \perp ⊥ .
Proof
Theorem 17. The ( k , m ) (k,m) ( k , m ) -threshold MTA-QSS scheme is correct.
Proof sketch. The MTA-QSS scheme uses the same coherent ( k , m ) (k,m) ( k , m ) -threshold encoding and decoding maps on the quantum share registers as the LVT-QSS scheme. The only difference is that MTA-QSS appends additional auxiliary classical information, namely ( r j ∥ t k j ) (r_j\|t_{k_j}) ( r j ∥ t k j ) instead of r j r_j r j , to each share. These auxiliary registers are not used by the decoding map on the quantum share registers and therefore do not affect the recovered secret state. Correctness then follows from the correctness of LVT-QSS in Theorem 8 . A full proof is given in Appendix E1.
Theorem 18. The ( k , m ) (k,m) ( k , m ) -threshold MTA-QSS scheme satisfies secrecy.
Proof sketch. For any unauthorized set M ⊂ [ m ] M \subset[m] M ⊂ [ m ] with ∣ M ∣ < k |M| < k ∣ M ∣ < k , the MTA-QSS scheme uses the same quantum encoding on the share registers as the LVT-QSS scheme. Hence, the reduced state on the quantum share registers held by M M M is independent of the secret, by Theorem 9 . The additional auxiliary registers in MTA-QSS contain only classical information generated from protocol randomness, such as tags and tracing-related data, and are independent of the secret state. Therefore, the joint view of any unauthorized set is independent of the secret. A full proof is given in Appendix E2.
Theorem 19. The ( k , m ) (k,m) ( k , m ) -threshold MTA-QSS scheme satisfies tracer secrecy.
Proof sketch. For any unauthorized set M ⊆ [ m ] M \subseteq[m] M ⊆ [ m ] with ∣ M ∣ < k |M| < k ∣ M ∣ < k , the quantum share registers held by M M M are distributed exactly as in the LVT-QSS scheme and are therefore independent of the secret. The additional information available in the tracer-secrecy experiment consists of auxiliary classical registers, the tracing keys, and the auxiliary key u k u_k u k . These values are generated from protocol randomness and tracing data, independently of the input secret state. Thus, even conditioned on the tracing keys, the joint state of the adversary’s view and the tracer-related registers is independent of the secret. The tracer-secrecy advantage is therefore negligible. A full proof is given in Appendix E3.
Theorem 20 (Informal). The MTA-QSS scheme is traceable against any QPT adversary: during reconstruction, the honest parties contributing valid shares can be identified except with negligible probability, from which the parties who submitted forged shares can be inferred.
Proof sketch. The proof follows the formal tracing experiment in Appendix D3. Let U U U be the tag set corresponding to the honestly generated shares used in reconstruction, and let ( U ′ , V ′ ) ← SecretTrace ( t k , u k , I ) (U',V') \leftarrow\operatorname{SecretTrace}(tk,u_k,I) ( U ′ , V ′ ) ← SecretTrace ( t k , u k , I ) . The adversary can win only if one of the following events occurs: the tracing evidence fails verification; verification accepts a set U ′ U' U ′ containing a forged tag; or verification accepts a tag set U ′ ⊆ T a g s U' \subseteq Tags U ′ ⊆ T a g s with U ′ ≠ U U' \ne U U ′ = U .
The first event occurs only with negligible probability by the consistency of SecretTrace and SecretVerify on honestly generated reconstruction evidence. The second event yields a collision in the hash function used to derive the verification keys, and hence occurs only with negligible probability. The third event is ruled out because the reconstruction evidence I I I , together with u k u_k u k and c k ck c k , uniquely determines the tags recovered by SecretTrace and checked by SecretVerify. Therefore, every possible winning event has negligible probability, and the adversary’s traceability advantage is negligible. A full proof is given in Appendix E4.
Theorem 21 (Informal). The MTA-QSS scheme is non-imputable against any QPT adversary: the evidence generated during reconstruction cannot falsely attribute a forged share to any honest party contributing a valid share, except with negligible probability.
Proof sketch. The proof follows the non-imputability experiment in Appendix D4. Let i ∗ i^* i ∗ be the designated honest participant that the adversary attempts to frame, and let t a g ∗ tag^* t a g ∗ be its tag. Since i ∗ i^* i ∗ is honest, t a g ∗ tag^* t a g ∗ is an honestly generated tag and its hash is contained in the verification-key set.
For the adversary to win, it must output evidence that passes SecretVerify while placing t a g ∗ tag^* t a g ∗ in the set of blamed tags. This is impossible under the verification rule: any tag accepted as belonging to the blamed set must fail the honest-tag verification condition, whereas t a g ∗ tag^* t a g ∗ satisfies it. Hence the framing event cannot occur, and in particular occurs with negligible probability. A full proof is given in Appendix E5.
To assess the robustness of the LVT-QSS protocol under noise, we adopt a model in which each recovery share independently undergoes depolarizing noise with probability p p p . Since secret recovery in LVT-QSS relies on Lagrange interpolation, we employ a conservative approximation: if any single recovery share is corrupted, the recovery round is considered failed, and the output state is approximated as a random guess. The expected reconstruction fidelity is therefore
F ( p ) = ( 1 − p ) k + 1 − ( 1 − p ) k d , F(p) = (1-p)^k + \frac{1-(1-p)^k}{d}, F ( p ) = ( 1 − p ) k + d 1 − ( 1 − p ) k ,
where the second term represents the baseline fidelity after interpolation failure, and d d d denotes the dimension of the secret Hilbert space H λ \mathcal{H}_{\lambda} H λ .
We evaluate three performance metrics for four representative parameter sets ( k , m ) = ( 3 , 5 ) , ( 4 , 7 ) , ( 5 , 9 ) , ( 6 , 11 ) (k,m) = (3,5), (4,7), (5,9), (6,11) ( k , m ) = ( 3 , 5 ) , ( 4 , 7 ) , ( 5 , 9 ) , ( 6 , 11 ) : the reconstruction fidelity F F F , the tracing accuracy (for f = 2 f=2 f = 2 leakers), and the verification success rate (for f = 2 f = 2 f = 2 leakers). Each data point is averaged over 500 independent Monte Carlo trials.
As shown in Figure 1 , all metrics decrease monotonically with increasing noise probability p p p , with smaller access structures consistently exhibiting stronger robustness. The reconstruction fidelity and tracing accuracy exhibit highly similar decay profiles, indicating that both are primarily governed by the same recovery-failure mechanism: when any share is corrupted by noise, Lagrange interpolation fails, and both reconstruction quality and tracing capability degrade simultaneously. In contrast, the verification success rate decays more rapidly because it corresponds to a stricter joint success condition: not only must all leakers’ tags be traced correctly, but the corresponding results must also pass a consistency check. Overall, LVT-QSS maintains relatively high reconstruction fidelity and tracing accuracy in low to intermediate noise, whereas verification success becomes the limiting factor at an earlier stage.
Figure 1. Noise resilience of LVT-QSS under per-share depolarizing noise for different parameter sets ( k , m ) (k,m) ( k , m ) . Panels show (a) reconstruction fidelity, (b) tracing accuracy, and (c) verification success rate, with f = 2 f = 2 f = 2 leakers for tracing and verification.
For MTA-QSS, as shown in Figure 2 , both tracing accuracy and verification success rate decrease monotonically with noise, and smaller parameter sets remain consistently more robust, while larger sets are more sensitive. Notably, the tracing accuracy and verification success curves nearly coincide. This behavior arises from the protocol design: compared to LVT-QSS, MTA-QSS exhibits higher robustness because the auxiliary key is retained by the Dealer, so noise only affects the quantum registers during the reconstruction stage, while both tracing and verification operate solely on the classical information obtained from the reconstruction. Consequently, noise does not accumulate along the verification pathway, which effectively reduces its impact on both tracing and verification, maintaining higher accuracy under identical noise conditions. The resulting sensitivity to noise is therefore nearly identical for both metrics, yielding the observed curve coincidence.
Figure 2. Noise resilience of MTA-QSS under per-share depolarizing noise for different parameter sets ( k , m ) (k,m) ( k , m ) . Panels show (a) tracing accuracy and (b) verification success rate, with t = 2 t=2 t = 2 malicious parties.
Overall, MTA-QSS maintains high tracing accuracy and verification success in low-noise regimes. In the presence of malicious parties and local noise, the protocol performance is primarily determined by reliable tracing of honest parties’ tags and the stability of subsequent consistency verification, reflecting the enhanced structural robustness of the scheme.
Discussion
In this work, we move beyond the traditional focus of quantum secret sharing on secrecy and correct reconstruction, and further examine the issue of traceability in multiparty distributed settings. Existing quantum secret sharing schemes are primarily designed to prevent unauthorized access and ensure correct recovery by authorized sets; however, when valid shares are leaked or forged shares are submitted during the reconstruction stage, such schemes typically do not provide protocol level mechanisms for behavior tracing and responsibility attribution. Our results show that these requirements should not be regarded merely as external management or enforcement issues, but can instead be incorporated into the security characterization of quantum secret sharing itself.
More specifically, we show that, in quantum secret sharing, traceability corresponds to different security requirements under different types of adversarial behavior, and therefore needs to be characterized in a scenario-dependent manner. We focus on two representative settings. The first is the leakage of valid shares, where the security goal is to trace an already occurred leakage event and attribute responsibility accordingly. The second is malicious interference during the reconstruction stage, where dishonest participants attempt to disrupt secret recovery by submitting forged shares; in this setting, the protocol is required to identify the source of the malicious behavior. Based on this distinction, we introduce leakage-verifiable and traceable quantum secret sharing (LVT-QSS) and malicious-traceable and accountable quantum secret sharing (MTA-QSS), respectively, thereby extending the security definition of quantum secret sharing to include behavior tracing and responsibility attribution under abnormal situations.
At the same time, the present framework still has clear boundaries of applicability, particularly with respect to the adversarial model, implementation assumptions, and resource overhead. In the current work, we provide corresponding traceability definitions and protocol constructions separately for the two threat models of valid-share leakage and malicious forgery during reconstruction, but do not yet place them within a unified framework. An immediate question for future work is whether one can develop a unified protocol and security framework that simultaneously captures both settings, and further leads to more general, or even composable, security formulations. Such a framework would be useful for describing more realistic adversaries that may possess multiple attack capabilities at once.
It also remains important to understand whether these security properties continue to hold under stronger adversarial models, such as collusion among multiple dishonest participants, adaptive corruption, or attempts to evade tracing by exploiting device imperfections and noise. In addition, implementing traceability is likely to incur nontrivial costs, including extra classical communication, verification complexity, storage requirements, and implementation difficulty. Compared with conventional quantum secret sharing, these additional mechanisms enhance the ability to trace abnormal behavior and attribute responsibility, but may also affect fault tolerance, reconstruction efficiency, and noise robustness. A further direction worth exploring is whether one can achieve a stronger protocol guarantee in which the secret can still be correctly reconstructed even in the presence of malicious participants during the reconstruction stage, while those malicious participants can nevertheless be identified and traced. More broadly, it would also be of interest to extend the traceability perspective developed here to other distributed quantum cryptographic tasks, and to develop lower-overhead protocol variants that are more amenable to experimental implementation. In summary, our results show that the security goals of
quantum secret sharing should not be limited to secrecy and recoverability alone. In realistic multiparty settings, one must also account for the tracing of abnormal behavior and the attribution of responsibility. By introducing the formal frameworks of LVT-QSS and MTA-QSS, we provide an initial theoretical starting point for traceable quantum secret sharing, and show that incorporating traceability into the security characterization of distributed quantum cryptographic protocols is both natural and meaningful.
Acknowledgments
This work is supported by the Natural Science Foundation of Shanghai under Grant No. 25ZR1402098 and the National Natural Science Foundation of China under Grant No. 62373155.
Quantum-Secure Collision-Resistant and One-Way Hash Functions
Let λ \lambda λ be the security parameter and F = F q ( λ ) \mathbb{F}=\mathbb{F}_{q}(\lambda) F = F q ( λ ) a finite field with log q ( λ ) = poly ( λ ) \log q(\lambda)=\operatorname{poly}(\lambda) log q ( λ ) = poly ( λ ) . We consider a hash function H : F → F H:\mathbb{F}\to\mathbb{F} H : F → F .
Quantum Collision Resistance. We say that H H H is collision-resistant against QPT adversaries if for every QPT algorithm B \mathcal{B} B ,
Adv B , H c o l l ( λ ) = Pr [ ( x , x ′ ) ← B ( 1 λ ) : x ≠ x ′ ∧ H ( x ) = H ( x ′ ) ] ≤ negl ( λ ) . (5) \operatorname{Adv}^{\mathrm{coll}}_{\mathcal{B},H}(\lambda)=\Pr\left[(x,x')\leftarrow\mathcal{B}(1^{\lambda}):x\ne x'\land H(x)=H(x')\right]\le\operatorname{negl}(\lambda). \tag*{(5)} Adv B , H coll ( λ ) = Pr [ ( x , x ′ ) ← B ( 1 λ ) : x = x ′ ∧ H ( x ) = H ( x ′ ) ] ≤ negl ( λ ) . (5)
Quantum One-Wayness (Preimage Resistance). We say that H H H is one-way (preimage resistant) against
QPT adversaries if for every QPT algorithm B \mathcal{B} B ,
Adv B , H o w ( λ ) = Pr [ x ← X ; x ′ ← B ( 1 λ , H ( x ) ) : H ( x ′ ) = H ( x ) ] ≤ negl ( λ ) . (6) \operatorname{Adv}^{\mathrm{ow}}_{\mathcal{B},H}(\lambda)=\Pr\left[x\leftarrow\mathcal{X};\ x'\leftarrow\mathcal{B}(1^\lambda,H(x)):H(x')=H(x)\right]\leq\operatorname{negl}(\lambda). \tag*{(6)} Adv B , H ow ( λ ) = Pr [ x ← X ; x ′ ← B ( 1 λ , H ( x )) : H ( x ′ ) = H ( x ) ] ≤ negl ( λ ) . (6)
Throughout this work, we assume the existence of a hash function H H H that is both quantum-secure collision-resistant and quantum-secure one-way against QPT adversaries. These assumptions are standard in post-quantum cryptography. Lattice-based constructions, such as those by Peikert–Rosen [21 ] and Lyubashevsky–Micciancio [22 ] , provide concrete candidates for collision-resistant hashing. In our protocols, these hash-function properties support verification and traceability within a threshold secret-sharing framework, whose classical foundations were established by Shamir [23 ] and Blakley [24 ] . In particular, quantum-secure one-wayness, which also underlies constructions of quantum public-key encryption [25 , 26 ] , protects participant tags against recovery from their public hash values.
Correctness
Definition 22 (Correctness (formal)). An LVT-QSS scheme is correct if there exists a negligible function negl ( ⋅ ) \operatorname{negl}(\cdot) negl ( ⋅ ) such that, for security parameter λ ∈ N \lambda\in\mathbb{N} λ ∈ N , number of parties m ∈ N m \in\mathbb{N} m ∈ N , threshold k k k with 1 ≤ k ≤ m 1 \leq k \leq m 1 ≤ k ≤ m , subset P ⊆ [ m ] P \subseteq[m] P ⊆ [ m ] with ∣ P ∣ ≥ k |P| \geq k ∣ P ∣ ≥ k , and secret state ∣ ψ ⟩ ∈ H λ |\psi\rangle\in\mathcal{H}_\lambda ∣ ψ ⟩ ∈ H λ , the following holds.
Let ρ : = ∣ ψ ⟩ ⟨ ψ ∣ \rho:= |\psi\rangle\langle\psi| ρ := ∣ ψ ⟩ ⟨ ψ ∣ . Generate the shares and run the reconstruction algorithm as
( t k , T a g s ) ← Setup ( 1 λ , m ) , (tk,\mathit{Tags})\leftarrow\operatorname{Setup}(1^\lambda,m), ( t k , Tags ) ← Setup ( 1 λ , m ) , ( s h , v k ) ← GenSecretShares ( ∣ ψ ⟩ , m , k , T a g s , t k ) , (sh,vk)\leftarrow\operatorname{GenSecretShares}(|\psi\rangle,m,k,\mathit{Tags},tk), ( s h , v k ) ← GenSecretShares ( ∣ ψ ⟩ , m , k , Tags , t k ) , o u t ← SecretRecover ( { ∣ s h i ⟩ } i ∈ P ) . (7) out\leftarrow\operatorname{SecretRecover}(\{|sh_i\rangle\}_{i\in P}). \tag*{(7)} o u t ← SecretRecover ({ ∣ s h i ⟩ } i ∈ P ) . (7) where s h : = { ∣ s h i ⟩ } i = 0 m − 1 sh := \{|sh_i\rangle\}_{i=0}^{m-1} s h := { ∣ s h i ⟩ } i = 0 m − 1 , and v k : = { v k i } i = 0 m − 1 vk := \{vk_i\}_{i=0}^{m-1} v k := { v k i } i = 0 m − 1 . Then
Pr [ o u t = ρ ′ and 1 2 ∥ ρ ′ − ρ ∥ 1 ≤ negl ( λ ) ] ≥ 1 − negl ( λ ) , (8) \Pr\left[out=\rho' \mathbin{\text{ and }} \frac{1}{2}\|\rho'-\rho\|_1\leq\operatorname{negl}(\lambda)\right]\geq1-\operatorname{negl}(\lambda), \tag*{(8)} Pr [ o u t = ρ ′ and 2 1 ∥ ρ ′ − ρ ∥ 1 ≤ negl ( λ ) ] ≥ 1 − negl ( λ ) , (8) where the probability is taken over the internal randomness of Setup, GenSecretShares, and SecretRecover.
Secrecy
Definition 23 (Secrecy (formal)). Let H = { H λ } λ ∈ N \mathcal{H}=\{\mathcal{H}_\lambda\}_{\lambda\in\mathbb{N}} H = { H λ } λ ∈ N denote the secret-state spaces of an LVT-QSS scheme. For every M ⊆ [ m ] M\subseteq[m] M ⊆ [ m ] with ∣ M ∣ < k |M|<k ∣ M ∣ < k and any two secret states ∣ ψ 0 ⟩ , ∣ ψ 1 ⟩ ∈ H λ |\psi_0\rangle,|\psi_1\rangle\in\mathcal{H}_\lambda ∣ ψ 0 ⟩ , ∣ ψ 1 ⟩ ∈ H λ , define
View M : = ⨂ i ∈ M ( R i ⊗ A i ) \operatorname{View}_M:=\bigotimes_{i\in M}(R_i\otimes A_i) View M := i ∈ M ⨂ ( R i ⊗ A i ) and let ρ View M ( b ) \rho_{\operatorname{View}_M}^{(b)} ρ View M ( b ) be the reduced state generated by sharing ∣ ψ b ⟩ |\psi_b\rangle ∣ ψ b ⟩ , for b ∈ { 0 , 1 } b\in\{0,1\} b ∈ { 0 , 1 } . Then there exists a negligible function negl ( ⋅ ) \operatorname{negl}(\cdot) negl ( ⋅ ) such that, for security parameter λ ∈ N \lambda\in\mathbb{N} λ ∈ N ,
1 2 ∥ ρ View M ( 0 ) − ρ View M ( 1 ) ∥ 1 ≤ negl ( λ ) . \frac{1}{2}\left\|\rho_{\operatorname{View}_M}^{(0)}-\rho_{\operatorname{View}_M}^{(1)}\right\|_1\leq\operatorname{negl}(\lambda). 2 1 ρ View M ( 0 ) − ρ View M ( 1 ) 1 ≤ negl ( λ ) .
Tracer secrecy
Definition 24 (Tracer secrecy (formal)). Let H = { H λ } λ ∈ N \mathcal{H}=\{\mathcal{H}_\lambda\}_{\lambda\in\mathbb{N}} H = { H λ } λ ∈ N denote the secret-state spaces of an LVT-QSS scheme. For every M ⊆ [ m ] M\subseteq[m] M ⊆ [ m ] with ∣ M ∣ < k |M|<k ∣ M ∣ < k and any two secret states ∣ ψ 0 ⟩ , ∣ ψ 1 ⟩ ∈ H λ |\psi_0\rangle,|\psi_1\rangle\in\mathcal{H}_\lambda ∣ ψ 0 ⟩ , ∣ ψ 1 ⟩ ∈ H λ , define
View M : = ⨂ i ∈ M ( R i ⊗ A i ) , T : = t k \operatorname{View}_M:=\bigotimes_{i\in M}(R_i\otimes A_i),\qquad T:=tk View M := i ∈ M ⨂ ( R i ⊗ A i ) , T := t k and let ρ View M , T ( b ) \rho_{\operatorname{View}_M,T}^{(b)} ρ View M , T ( b ) be the reduced state generated by sharing ∣ ψ b ⟩ |\psi_b\rangle ∣ ψ b ⟩ , for b ∈ { 0 , 1 } b\in\{0,1\} b ∈ { 0 , 1 } . Then there exists a negligible function negl ( ⋅ ) \operatorname{negl}(\cdot) negl ( ⋅ ) such that, for security parameter λ ∈ N \lambda\in\mathbb{N} λ ∈ N ,
1 2 ∥ ρ View M , T ( 0 ) − ρ View M , T ( 1 ) ∥ 1 ≤ negl ( λ ) . \frac{1}{2}\left\|\rho_{\operatorname{View}_M,T}^{(0)}-\rho_{\operatorname{View}_M,T}^{(1)}\right\|_1\leq\operatorname{negl}(\lambda). 2 1 ρ View M , T ( 0 ) − ρ View M , T ( 1 ) 1 ≤ negl ( λ ) .
Good reconstruction boxes
Definition 25 (Good reconstruction boxes (formal)). Let λ ∈ N \lambda\in\mathbb{N} λ ∈ N , let m , f , k ∈ N m,f,k\in\mathbb{N} m , f , k ∈ N satisfy 0 < f < k ≤ m 0<f<k\leq m 0 < f < k ≤ m , and let I i d x ⊆ [ m ] \mathcal{I}_{\mathrm{idx}}\subseteq[m] I idx ⊆ [ m ] with ∣ I i d x ∣ = f |\mathcal{I}_{\mathrm{idx}}|=f ∣ I idx ∣ = f . Let ∣ ψ ⟩ |\psi\rangle ∣ ψ ⟩ be a secret state and let ρ : = ∣ ψ ⟩ ⟨ ψ ∣ \rho:=|\psi\rangle\langle\psi| ρ := ∣ ψ ⟩ ⟨ ψ ∣ . A reconstruction box R \mathcal{R} R is ( m , k , f , ∣ ψ ⟩ , ϵ ) (m,k,f,|\psi\rangle,\epsilon) ( m , k , f , ∣ ψ ⟩ , ϵ ) -good if, for uniformly random Q ⊆ [ m ] ∖ I i d x Q\subseteq[m]\setminus\mathcal{I}_{\mathrm{idx}} Q ⊆ [ m ] ∖ I idx with ∣ Q ∣ = k − f |Q|=k-f ∣ Q ∣ = k − f ,
Pr [ ρ ′ ← R ( { ∣ s h i ⟩ } i ∈ Q ) : 1 2 ∥ ρ ′ − ρ ∥ 1 ≤ negl ( λ ) ] ≥ ϵ . \Pr\left[\rho'\leftarrow\mathcal{R}(\{|sh_i\rangle\}_{i\in Q}):\frac{1}{2}\|\rho'-\rho\|_1\leq\operatorname{negl}(\lambda)\right]\geq\epsilon. Pr [ ρ ′ ← R ({ ∣ s h i ⟩ } i ∈ Q ) : 2 1 ∥ ρ ′ − ρ ∥ 1 ≤ negl ( λ ) ] ≥ ϵ . The probability is taken over the random choice of Q Q Q , the randomness of R \mathcal{R} R , and the randomness used to generate the shares.
Traceability
We define the following tracing experiment, which formalizes the traceability of the quantum secret-sharing scheme.
Let A \mathcal{A} A be a QPT adversary, let ∣ ψ ⟩ ∈ H λ |\psi\rangle\in\mathcal{H}_\lambda ∣ ψ ⟩ ∈ H λ be an arbitrary secret state, and let ϵ ∈ [ 0 , 1 ] \epsilon\in[0,1] ϵ ∈ [ 0 , 1 ] . Tags serve as unique identifiers of participants.
Experiment 1 ExpTrace A , L V T - Q S S , ϵ ( λ ) \operatorname{ExpTrace}_{\mathcal{A},\mathrm{LVT\text{-}QSS},\epsilon}(\lambda) ExpTrace A , LVT - QSS , ϵ ( λ )
( m , k , I i d x , s t ) ← A ( 1 λ ) (m,k,\mathcal{I}_{\mathrm{idx}},st)\leftarrow\mathcal{A}(1^\lambda) ( m , k , I idx , s t ) ← A ( 1 λ ) , where I i d x = { i 1 , … , i f } ⊆ [ m ] \mathcal{I}_{\mathrm{idx}}=\{i_1,\ldots,i_f\}\subseteq[m] I idx = { i 1 , … , i f } ⊆ [ m ] denotes the set of corrupted parties.
( t k , T a g s ) ← S e t u p ( 1 λ , m ) (tk, Tags) \leftarrow Setup(1^\lambda,m) ( t k , T a g s ) ← S e t u p ( 1 λ , m ) , where T a g s = { t a g i } i = 0 m − 1 Tags=\{tag_i\}_{i=0}^{m-1} T a g s = { t a g i } i = 0 m − 1 . Define I : = { t a g i : i ∈ I i d x } I:=\{tag_i:i\in I_{\mathrm{idx}}\} I := { t a g i : i ∈ I idx } . The set T a g s Tags T a g s is hidden from A \mathcal{A} A .
( { ∣ s h i ⟩ } i = 0 m − 1 , { v k i } i = 0 m − 1 ) ← G e n S e c r e t S h a r e s ( ∣ ψ ⟩ , m , k , T a g s , t k ) (\{|sh_i\rangle\}_{i=0}^{m-1},\{vk_i\}_{i=0}^{m-1})\leftarrow GenSecretShares(|\psi\rangle,m,k,Tags,tk) ({ ∣ s h i ⟩ } i = 0 m − 1 , { v k i } i = 0 m − 1 ) ← G e n S ecr e tS ha r es ( ∣ ψ ⟩ , m , k , T a g s , t k ) , and let v k : = ( v k 0 , … , v k m − 1 ) vk:=(vk_0,\ldots,vk_{m-1}) v k := ( v k 0 , … , v k m − 1 ) .
R ← A ( s t , { ∣ s h i ⟩ } i ∈ I i d x ) \mathcal{R}\leftarrow\mathcal{A}(st,\{|sh_i\rangle\}_{i\in I_{\mathrm{idx}}}) R ← A ( s t , { ∣ s h i ⟩ } i ∈ I idx ) .
If R \mathcal{R} R is not ( m , k , f , ∣ ψ ⟩ , ϵ ) (m,k,f,|\psi\rangle,\epsilon) ( m , k , f , ∣ ψ ⟩ , ϵ ) -good, output 0.
Sample Q ⊆ [ m ] ∖ I i d x Q\subseteq[m]\setminus I_{\mathrm{idx}} Q ⊆ [ m ] ∖ I idx uniformly at random subject to ∣ Q ∣ = k − f |Q|=k-f ∣ Q ∣ = k − f , and compute
I ′ ← SecretTrace R ( ⋅ ) ( t k , { ∣ s h i ⟩ } i ∈ Q ) . I'\leftarrow\operatorname{SecretTrace}^{\mathcal{R}(\cdot)}(tk,\{|sh_i\rangle\}_{i\in Q}). I ′ ← SecretTrace R ( ⋅ ) ( t k , { ∣ s h i ⟩ } i ∈ Q ) .
Output 0 if I ′ = I I'=I I ′ = I and SecretVerify ( v k , I ′ ) = 1 \operatorname{SecretVerify}(vk,I')=1 SecretVerify ( v k , I ′ ) = 1 ; otherwise output 1.
Definition 26 (Traceability). For any QPT adversary A \mathcal{A} A and ϵ ∈ [ 0 , 1 ] \epsilon\in[0,1] ϵ ∈ [ 0 , 1 ] , define its tracing advantage as
Adv A , L V T - Q S S , ϵ t r a c e ( λ ) : = ϵ ⋅ Pr [ ExpTrace A , L V T - Q S S , ϵ ( λ ) = 1 ] . (9) \operatorname{Adv}^{\mathrm{trace}}_{\mathcal{A},\mathrm{LVT\text{-}QSS},\epsilon}(\lambda):=\epsilon\cdot\Pr\left[\operatorname{ExpTrace}_{\mathcal{A},\mathrm{LVT\text{-}QSS},\epsilon}(\lambda)=1\right]. \tag*{(9)} Adv A , LVT - QSS , ϵ trace ( λ ) := ϵ ⋅ Pr [ ExpTrace A , LVT - QSS , ϵ ( λ ) = 1 ] . (9)
The LVT-QSS scheme is formally traceable if the tracing advantage of every QPT adversary A \mathcal{A} A is negligible in λ \lambda λ .
Non-imputability
We define the following non-imputability experiment. Let A \mathcal{A} A be a QPT adversary, and let ∣ ψ ⟩ ∈ H λ |\psi\rangle\in\mathcal{H}_\lambda ∣ ψ ⟩ ∈ H λ be an arbitrary secret state. Tags serve as unique identifiers of participants.
Experiment 2 ExpNI A , L V T - Q S S ( λ ) \operatorname{ExpNI}_{\mathcal{A},\mathrm{LVT\text{-}QSS}}(\lambda) ExpNI A , LVT - QSS ( λ )
( m , k , i ∗ , s t ) ← A ( 1 λ ) (m,k,i^*,st)\leftarrow\mathcal{A}(1^\lambda) ( m , k , i ∗ , s t ) ← A ( 1 λ ) , where i ∗ ∈ [ m ] i^*\in[m] i ∗ ∈ [ m ] denotes the honest participant that A \mathcal{A} A aims to frame.
( t k , T a g s ) ← S e t u p ( 1 λ , m ) (tk,Tags)\leftarrow Setup(1^\lambda,m) ( t k , T a g s ) ← S e t u p ( 1 λ , m ) , where T a g s = { t a g i } i = 0 m − 1 Tags=\{tag_i\}_{i=0}^{m-1} T a g s = { t a g i } i = 0 m − 1 . Let t a g ∗ : = t a g i ∗ tag^*:=tag_{i^*} t a g ∗ := t a g i ∗ .
( { ∣ s h i ⟩ } i = 0 m − 1 , { v k i } i = 0 m − 1 ) ← G e n S e c r e t S h a r e s ( ∣ ψ ⟩ , m , k , T a g s , t k ) (\{|sh_i\rangle\}_{i=0}^{m-1},\{vk_i\}_{i=0}^{m-1})\leftarrow GenSecretShares(|\psi\rangle,m,k,Tags,tk) ({ ∣ s h i ⟩ } i = 0 m − 1 , { v k i } i = 0 m − 1 ) ← G e n S ecr e tS ha r es ( ∣ ψ ⟩ , m , k , T a g s , t k ) , and let v k : = ( v k 0 , … , v k m − 1 ) vk:=(vk_0,\ldots,vk_{m-1}) v k := ( v k 0 , … , v k m − 1 ) .
I t a g ∗ ← $ A ( s t , { ∣ s h i ⟩ } i ∈ [ m ] ∖ { i ∗ } , t k , v k ) I^*_{tag}\mathrel{\stackrel{\$}{\leftarrow}}\mathcal{A}(st,\{|sh_i\rangle\}_{i\in[m]\setminus\{i^*\}},tk,vk) I t a g ∗ ← $ A ( s t , { ∣ s h i ⟩ } i ∈ [ m ] ∖ { i ∗ } , t k , v k ) .
Output 1 if t a g ∗ ∈ I t a g ∗ tag^*\in I^*_{tag} t a g ∗ ∈ I t a g ∗ and SecretVerify ( v k , I t a g ∗ ) = 1 \operatorname{SecretVerify}(vk,I^*_{tag})=1 SecretVerify ( v k , I t a g ∗ ) = 1 ; otherwise output 0.
Definition 27 (Non-imputability). For any QPT adversary A \mathcal{A} A , define its non-imputability advantage by
Adv A , L V T - Q S S n i ( λ ) : = Pr [ ExpNI A , L V T - Q S S ( λ ) = 1 ] . (10) \operatorname{Adv}^{\mathrm{ni}}_{\mathcal{A},\mathrm{LVT\text{-}QSS}}(\lambda):=\Pr\left[\operatorname{ExpNI}_{\mathcal{A},\mathrm{LVT\text{-}QSS}}(\lambda)=1\right]. \tag*{(10)} Adv A , LVT - QSS ni ( λ ) := Pr [ ExpNI A , LVT - QSS ( λ ) = 1 ] . (10)
The LVT-QSS scheme is formally non-imputable if Adv A , L V T - Q S S n i ( λ ) \operatorname{Adv}^{\mathrm{ni}}_{\mathcal{A},\mathrm{LVT\text{-}QSS}}(\lambda) Adv A , LVT - QSS ni ( λ ) is negligible in λ \lambda λ for every QPT adversary A \mathcal{A} A .
Proofs of LVT-QSS
Proof of Theorem 8
Proof. We show that any set of at least k k k valid shares enables correct reconstruction of the secret quantum state.
Linear structure of the coherent encoding. In the GenSecretShares procedure, the quantum secret ∣ ψ ⟩ = ∑ s α s ∣ s ⟩ |\psi\rangle=\sum_s\alpha_s|s\rangle ∣ ψ ⟩ = ∑ s α s ∣ s ⟩ is coherently encoded and distributed among the m m m parties’ registers. Specifically, there exists an isometry V V V such that
V ( ∑ s α s ∣ s ⟩ ) = ∑ s α s ∣ E ( s ) ⟩ , (11) V\left(\sum_s\alpha_s|s\rangle\right)=\sum_s\alpha_s|E(s)\rangle, \tag*{(11)} V ( s ∑ α s ∣ s ⟩ ) = s ∑ α s ∣ E ( s )⟩ , (11)
where ∣ E ( s ) ⟩ |E(s)\rangle ∣ E ( s )⟩ denotes the coherent encoding of the basis element ∣ s ⟩ |s\rangle ∣ s ⟩ .
Let x 0 , … , x m − 1 ∈ F x_0,\ldots,x_{m-1}\in\mathbb{F} x 0 , … , x m − 1 ∈ F be distinct elements, and define the Vandermonde matrix
V m = [ 1 x 0 x 0 2 ⋯ x 0 k − 1 ⋮ ⋮ ⋮ ⋮ 1 x m − 1 x m − 1 2 ⋯ x m − 1 k − 1 ] ∈ F m × k . (12) V_m=
\begin{bmatrix}
1 & x_0 & x_0^2 & \cdots& x_0^{k-1}\\
\vdots& \vdots& \vdots& & \vdots\\
1 & x_{m-1} & x_{m-1}^2 & \cdots& x_{m-1}^{k-1}
\end{bmatrix}\in\mathbb{F}^{m\times k}. \tag*{(12)} V m = 1 ⋮ 1 x 0 ⋮ x m − 1 x 0 2 ⋮ x m − 1 2 ⋯ ⋯ x 0 k − 1 ⋮ x m − 1 k − 1 ∈ F m × k . (12)
For any coefficient vector c = ( c 0 , … , c k − 1 ) T ∈ F k \mathbf{c}=(c_0,\ldots,c_{k-1})^{\mathsf{T}}\in\mathbb{F}^k c = ( c 0 , … , c k − 1 ) T ∈ F k , define the polynomial
p c ( t ) = c 0 + c 1 t + ⋯ + c k − 1 t k − 1 . (13) p_{\mathbf{c}}(t)=c_0+c_1t+\cdots+c_{k-1}t^{k-1}. \tag*{(13)} p c ( t ) = c 0 + c 1 t + ⋯ + c k − 1 t k − 1 . (13)
The encoding in GenSecretShares is expressed as
∣ ψ ⟩ ⟼ ∑ s ∈ F α s ∑ c ∈ F k c 0 = u k , c k − 1 = s ⨂ j = 0 m − 1 ∣ p c ( x j ) , r j ⟩ . (14) |\psi\rangle\longmapsto\sum_{s\in\mathbb{F}}\alpha_s
\sum_{\substack{\mathbf{c}\in\mathbb{F}^k\\c_0=uk,\ c_{k-1}=s}}
\bigotimes_{j=0}^{m-1}|p_{\mathbf{c}}(x_j),r_j\rangle. \tag*{(14)} ∣ ψ ⟩ ⟼ s ∈ F ∑ α s c ∈ F k c 0 = u k , c k − 1 = s ∑ j = 0 ⨂ m − 1 ∣ p c ( x j ) , r j ⟩ . (14)
where y j = p c ( x j ) y_j=p_{\mathbf{c}}(x_j) y j = p c ( x j ) , and u k ← $ F uk\mathrel{\stackrel{\$}{\leftarrow}}\mathbb{F} u k ← $ F . Since the points x 0 , … , x m − 1 x_0,\ldots,x_{m-1} x 0 , … , x m − 1 are distinct, the Vandermonde matrix V m V_m V m has full rank, and any set of k k k rows forms an invertible submatrix. Therefore, any k k k evaluations { y j } \{y_j\} { y j } uniquely determine the polynomial p c ( t ) p_{\mathbf{c}}(t) p c ( t ) and the coefficient vector c \mathbf{c} c .
Reconstruction from any k k k shares. Let P ′ ⊆ { 0 , … , m − 1 } P'\subseteq\{0,\ldots,m-1\} P ′ ⊆ { 0 , … , m − 1 } be any set of k k k parties. Without loss of generality, take P ′ = { 0 , 1 , … , k − 1 } P'=\{0,1,\ldots,k-1\} P ′ = { 0 , 1 , … , k − 1 } . The basis state on the corresponding registers { R 0 , … , R k − 1 } \{R_0,\ldots,R_{k-1}\} { R 0 , … , R k − 1 } is
∣ y 0 , … , y k − 1 ⟩ = ∣ p c ( x 0 ) , … , p c ( x k − 1 ) ⟩ = ∣ V k ( x 0 , … , x k − 1 ) ⋅ c ⟩ . (15) |y_0,\ldots,y_{k-1}\rangle=|p_{\mathbf{c}}(x_0),\ldots,p_{\mathbf{c}}(x_{k-1})\rangle
=|V_k(x_0,\ldots,x_{k-1})\cdot\mathbf{c}\rangle. \tag*{(15)} ∣ y 0 , … , y k − 1 ⟩ = ∣ p c ( x 0 ) , … , p c ( x k − 1 )⟩ = ∣ V k ( x 0 , … , x k − 1 ) ⋅ c ⟩ . (15)
where V k ( x 0 , … , x k − 1 ) ∈ F k × k V_k(x_0,\ldots,x_{k-1})\in\mathbb{F}^{k\times k} V k ( x 0 , … , x k − 1 ) ∈ F k × k is the corresponding Vandermonde submatrix. Since V k V_k V k is invertible, we have
c = V k − 1 ( x 0 , … , x k − 1 ) ⋅ ( y 0 , … , y k − 1 ) T . (16) \mathbf{c}=V_k^{-1}(x_0,\ldots,x_{k-1})\cdot(y_0,\ldots,y_{k-1})^{\mathsf{T}}. \tag*{(16)} c = V k − 1 ( x 0 , … , x k − 1 ) ⋅ ( y 0 , … , y k − 1 ) T . (16)
Applying the unitary implementation of this invertible linear transformation to the registers { R 0 , … , R k − 1 } \{R_0,\ldots,R_{k-1}\} { R 0 , … , R k − 1 } gives
⨂ j = 0 k − 1 ∣ y j ⟩ → V k − 1 ∣ c 0 , … , c k − 1 ⟩ . (17) \bigotimes_{j=0}^{k-1}|y_j\rangle\xrightarrow{V_k^{-1}}|c_0,\ldots,c_{k-1}\rangle. \tag*{(17)} j = 0 ⨂ k − 1 ∣ y j ⟩ V k − 1 ∣ c 0 , … , c k − 1 ⟩ . (17)
In particular, the highest-degree coefficient satisfies c k − 1 = s c_{k-1}=s c k − 1 = s .
Next, the SecretRecover procedure applies a cyclic right-shift permutation S r S_r S r to the registers { R 0 , … , R k − 1 } \{R_0,\ldots,R_{k-1}\} { R 0 , … , R k − 1 } and { A 0 , … , A k − 1 } \{A_0,\ldots,A_{k-1}\} { A 0 , … , A k − 1 } :
∣ c 0 , … , c k − 1 ; r 0 , … , r k − 1 ⟩ → S r ∣ c k − 1 , c 0 , … , c k − 2 ; r k − 1 , r 0 , … , r k − 2 ⟩ . (18) \lvert c_0,\ldots,c_{k-1};r_0,\ldots,r_{k-1}\rangle
\xrightarrow{S_r}
\lvert c_{k-1},c_0,\ldots,c_{k-2};r_{k-1},r_0,\ldots,r_{k-2}\rangle. \tag*{(18)} ∣ c 0 , … , c k − 1 ; r 0 , … , r k − 1 ⟩ S r ∣ c k − 1 , c 0 , … , c k − 2 ; r k − 1 , r 0 , … , r k − 2 ⟩ . (18)
By construction, the subsequent reversible linear transformations and controlled additions act only on { R 1 , … , R k − 1 } \{R_1,\ldots,R_{k-1}\} { R 1 , … , R k − 1 } , together with the auxiliary registers, and do not affect R 0 R_0 R 0 . Consequently, register R 0 R_0 R 0 contains
∑ s α s ∣ s ⟩ = ∣ ψ ⟩ , \sum_s \alpha_s\lvert s\rangle=\lvert\psi\rangle, s ∑ α s ∣ s ⟩ = ∣ ψ ⟩ ,
showing that SecretRecover correctly reconstructs the secret from any k k k valid shares.
Finally, let P ′ ⊆ [ m ] P' \subseteq[m] P ′ ⊆ [ m ] be any authorized set with ∣ P ′ ∣ ≥ k \lvert P'\rvert\ge k ∣ P ′ ∣ ≥ k . The recovery procedure selects any k k k -subset P ′ ′ ⊆ P ′ P''\subseteq P' P ′′ ⊆ P ′ and applies the above reconstruction map to the shares { ∣ s h i ⟩ } i ∈ P ′ ′ \{\lvert sh_i\rangle\}_{i\in P''} {∣ s h i ⟩ } i ∈ P ′′ . Let
∣ ψ ′ ⟩ ← SecretRecover ( { ∣ s h i ⟩ } i ∈ P ′ ) \lvert\psi'\rangle\leftarrow\operatorname{SecretRecover}(\{\lvert sh_i\rangle\}_{i\in P'}) ∣ ψ ′ ⟩ ← SecretRecover ({∣ s h i ⟩ } i ∈ P ′ )
and ρ ′ : = ∣ ψ ′ ⟩ ⟨ ψ ′ ∣ \rho' := \lvert\psi'\rangle\langle\psi'\rvert ρ ′ := ∣ ψ ′ ⟩ ⟨ ψ ′ ∣ . Then
Pr [ Td ( ρ , ρ ′ ) ≤ negl ( λ ) ] ≥ 1 − negl ( λ ) . (19) \Pr\left[\operatorname{Td}(\rho,\rho')\le\operatorname{negl}(\lambda)\right]\ge1-\operatorname{negl}(\lambda). \tag*{(19)} Pr [ Td ( ρ , ρ ′ ) ≤ negl ( λ ) ] ≥ 1 − negl ( λ ) . (19)
Therefore, the ( k , m ) (k,m) ( k , m ) -threshold LVT-QSS scheme is correct. □ \square □
Proof of Theorem 9
Proof. We prove that any set of fewer than k k k parties learns no information about the secret quantum state.
Purification and encoding. All internal randomness in the protocol is purified into an environment register E E E . The encoding procedure is realized by an isometry
U e n c : H λ → ( ⨂ i = 0 m − 1 H R i ) ⊗ ( ⨂ i = 0 m − 1 H A i ) ⊗ H E . (20) U_{\mathrm{enc}}:\mathcal{H}_{\lambda}\to\left(\bigotimes_{i=0}^{m-1}\mathcal{H}_{R_i}\right)\otimes\left(\bigotimes_{i=0}^{m-1}\mathcal{H}_{A_i}\right)\otimes\mathcal{H}_E . \tag*{(20)} U enc : H λ → ( i = 0 ⨂ m − 1 H R i ) ⊗ ( i = 0 ⨂ m − 1 H A i ) ⊗ H E . (20)
Let q = ∣ F ∣ q=\lvert\mathbb{F}\rvert q = ∣ F ∣ , and let the secret state be
∣ ψ ⟩ = ∑ s α s ∣ s ⟩ , ∑ s ∣ α s ∣ 2 = 1. \lvert\psi\rangle=\sum_s\alpha_s\lvert s\rangle,\qquad\sum_s\lvert\alpha_s\rvert^2=1. ∣ ψ ⟩ = s ∑ α s ∣ s ⟩ , s ∑ ∣ α s ∣ 2 = 1.
In the encoding, the secret basis value s s s is embedded as the highest-degree coefficient c k − 1 = s c_{k-1}=s c k − 1 = s . The remaining coefficients c 0 , c 1 , … , c k − 2 c_0,c_1,\ldots,c_{k-2} c 0 , c 1 , … , c k − 2 are sampled uniformly from F \mathbb{F} F and independently of s s s , with c 0 = u k c_0=u_k c 0 = u k . For a coefficient vector c = ( c 0 , … , c k − 1 ) c=(c_0,\ldots,c_{k-1}) c = ( c 0 , … , c k − 1 ) , define
p c ( t ) = ∑ ℓ = 0 k − 1 c ℓ t ℓ . (21) p_c(t)=\sum_{\ell=0}^{k-1}c_\ell t^\ell. \tag*{(21)} p c ( t ) = ℓ = 0 ∑ k − 1 c ℓ t ℓ . (21)
The encoded global state can be written as
∣ Ψ ⟩ = 1 q k − 1 ∑ s α s ∑ c ∈ F k c k − 1 = s ( ⨂ i = 0 m − 1 ∣ p c ( x i ) ⟩ R i ) ⊗ ( ⨂ i = 0 m − 1 ∣ r i ⟩ A i ) ⊗ ∣ ξ c ⟩ E . (22) \lvert\Psi\rangle=
\frac{1}{\sqrt{q^{k-1}}}\sum_s\alpha_s
\sum_{\substack{c\in\mathbb{F}^k\\c_{k-1}=s}}
\left(\bigotimes_{i=0}^{m-1}\lvert p_c(x_i)\rangle_{R_i}\right)
\otimes
\left(\bigotimes_{i=0}^{m-1}\lvert r_i\rangle_{A_i}\right)
\otimes\lvert\xi_c\rangle_E . \tag*{(22)} ∣ Ψ ⟩ = q k − 1 1 s ∑ α s c ∈ F k c k − 1 = s ∑ ( i = 0 ⨂ m − 1 ∣ p c ( x i ) ⟩ R i ) ⊗ ( i = 0 ⨂ m − 1 ∣ r i ⟩ A i ) ⊗ ∣ ξ c ⟩ E . (22)
Since the classical randomness c 0 , … , c k − 2 c_0,\ldots,c_{k-2} c 0 , … , c k − 2 can be purified into the environment, we assume without loss of generality that the states { ∣ ξ c ⟩ E } c \{\lvert\xi_c\rangle_E\}_c {∣ ξ c ⟩ E } c are pairwise orthogonal.
Reduced state on an unauthorized set. Let M ⊆ [ m ] M\subseteq[m] M ⊆ [ m ] be any unauthorized set with ∣ M ∣ < k \lvert M\rvert<k ∣ M ∣ < k . Tracing out the environment register eliminates the cross terms, since
Tr E ( ∣ ξ c ⟩ ⟨ ξ c ′ ∣ ) = δ c , c ′ . \operatorname{Tr}_E(\lvert\xi_c\rangle\langle\xi_{c'}\rvert)=\delta_{c,c'}. Tr E (∣ ξ c ⟩ ⟨ ξ c ′ ∣) = δ c , c ′ .
Further tracing out all registers outside M M M gives the reduced state on the adversary’s view:
ρ V i e w M ( ∣ ψ ⟩ ⟨ ψ ∣ ) = 1 q k − 1 ∑ s ∣ α s ∣ 2 ∑ c ∈ F k c k − 1 = s ( ⨂ i ∈ M ∣ p c ( x i ) ⟩ ⟨ p c ( x i ) ∣ ) ⊗ ρ A M . (23) \rho_{\mathrm{View}_M}(\lvert\psi\rangle\langle\psi\rvert)
=
\frac{1}{q^{k-1}}\sum_s\lvert\alpha_s\rvert^2
\sum_{\substack{c\in\mathbb{F}^k\\c_{k-1}=s}}
\left(\bigotimes_{i\in M}\lvert p_c(x_i)\rangle\langle p_c(x_i)\rvert\right)
\otimes\rho_{A_M}. \tag*{(23)} ρ View M (∣ ψ ⟩ ⟨ ψ ∣) = q k − 1 1 s ∑ ∣ α s ∣ 2 c ∈ F k c k − 1 = s ∑ ( i ∈ M ⨂ ∣ p c ( x i )⟩ ⟨ p c ( x i )∣ ) ⊗ ρ A M . (23)
where
ρ A M : = ⨂ i ∈ M ∣ r i ⟩ ⟨ r i ∣ \rho_{A_M}:=\bigotimes_{i\in M}\lvert r_i\rangle\langle r_i\rvert ρ A M := i ∈ M ⨂ ∣ r i ⟩ ⟨ r i ∣
is independent of the secret.
Define the linear map
T M : F k → F ∣ M ∣ , T M ( c ) = ( p c ( x i ) ) i ∈ M . T_M:\mathbb{F}^k\to\mathbb{F}^{\lvert M\rvert},\qquad
T_M(c)=(p_c(x_i))_{i\in M}. T M : F k → F ∣ M ∣ , T M ( c ) = ( p c ( x i ) ) i ∈ M .
Fix s ∈ F s\in\mathbb{F} s ∈ F , and impose only the constraint c k − 1 = s c_{k-1}=s c k − 1 = s . The remaining variables c 0 , c 1 , … , c k − 2 c_0,c_1,\ldots,c_{k-2} c 0 , c 1 , … , c k − 2 are uniformly random over F k − 1 \mathbb{F}^{k-1} F k − 1 and independent of s s s . Since the points { x i } i ∈ M \{x_i\}_{i\in M} { x i } i ∈ M are distinct and ∣ M ∣ < k \lvert M\rvert<k ∣ M ∣ < k , the corresponding Vandermonde submatrix has full row rank ∣ M ∣ \lvert M\rvert ∣ M ∣ . Therefore, for every y ∈ F ∣ M ∣ y\in\mathbb{F}^{\lvert M\rvert} y ∈ F ∣ M ∣ , the system
T M ( c ) = y , c k − 1 = s T_M(c)=y,\qquad c_{k-1}=s T M ( c ) = y , c k − 1 = s
has exactly q k − 1 − ∣ M ∣ q^{k-1-\lvert M\rvert} q k − 1 − ∣ M ∣ solutions in the variables c 0 , … , c k − 2 c_0,\ldots,c_{k-2} c 0 , … , c k − 2 , independent of s s s and y y y . Hence
∑ c ∈ F k c k − 1 = s ⨂ i ∈ M ∣ p c ( x i ) ⟩ ⟨ p c ( x i ) ∣ = q k − 1 − ∣ M ∣ ∑ y ∈ F ∣ M ∣ ∣ y ⟩ ⟨ y ∣ . (24) \sum_{\substack{c\in\mathbb{F}^k\\c_{k-1}=s}}
\bigotimes_{i\in M}\lvert p_c(x_i)\rangle\langle p_c(x_i)\rvert
=
q^{k-1-\lvert M\rvert}\sum_{y\in\mathbb{F}^{\lvert M\rvert}}\lvert y\rangle\langle y\rvert. \tag*{(24)} c ∈ F k c k − 1 = s ∑ i ∈ M ⨂ ∣ p c ( x i )⟩ ⟨ p c ( x i )∣ = q k − 1 − ∣ M ∣ y ∈ F ∣ M ∣ ∑ ∣ y ⟩ ⟨ y ∣ . (24)
Substituting this expression into the reduced state and using ∑ s ∣ α s ∣ 2 = 1 \sum_s |\alpha_s|^2 = 1 ∑ s ∣ α s ∣ 2 = 1 , we obtain
ρ V i e w M ( ∣ ψ ⟩ ⟨ ψ ∣ ) = 1 q k − 1 ∑ s ∣ α s ∣ 2 q k − 1 − ∣ M ∣ ∑ y ∈ F ∣ M ∣ ∣ y ⟩ ⟨ y ∣ ⊗ ρ A M = ( 1 q ∣ M ∣ ∑ y ∈ F ∣ M ∣ ∣ y ⟩ ⟨ y ∣ ) ⊗ ρ A M . (25) \rho_{\mathrm{View}_M}(|\psi\rangle\langle\psi|) = \frac{1}{q^{k-1}} \sum_s |\alpha_s|^2 q^{k-1-|M|} \sum_{y\in\mathbb{F}^{|M|}} |y\rangle\langle y| \otimes\rho_{A_M}
= \left(\frac{1}{q^{|M|}} \sum_{y\in\mathbb{F}^{|M|}} |y\rangle\langle y|\right)\otimes\rho_{A_M}. \tag*{(25)} ρ View M ( ∣ ψ ⟩ ⟨ ψ ∣ ) = q k − 1 1 s ∑ ∣ α s ∣ 2 q k − 1 − ∣ M ∣ y ∈ F ∣ M ∣ ∑ ∣ y ⟩ ⟨ y ∣ ⊗ ρ A M = q ∣ M ∣ 1 y ∈ F ∣ M ∣ ∑ ∣ y ⟩ ⟨ y ∣ ⊗ ρ A M . (25)
Denote this fixed state by
σ M : = ( 1 q ∣ M ∣ ∑ y ∈ F ∣ M ∣ ∣ y ⟩ ⟨ y ∣ ) ⊗ ρ A M . (26) \sigma_M := \left(\frac{1}{q^{|M|}} \sum_{y\in\mathbb{F}^{|M|}} |y\rangle\langle y|\right)\otimes\rho_{A_M}. \tag*{(26)} σ M := q ∣ M ∣ 1 y ∈ F ∣ M ∣ ∑ ∣ y ⟩ ⟨ y ∣ ⊗ ρ A M . (26)
Crucially, σ M \sigma_M σ M is independent of the amplitudes { α s } \{\alpha_s\} { α s } and therefore independent of the secret state. Thus, for any two secret states ∣ ψ 0 ⟩ |\psi_0\rangle ∣ ψ 0 ⟩ and ∣ ψ 1 ⟩ |\psi_1\rangle ∣ ψ 1 ⟩ , the corresponding adversarial views satisfy
ρ V i e w M ( 0 ) = ρ V i e w M ( 1 ) = σ M . (27) \rho_{\mathrm{View}_M}^{(0)}=\rho_{\mathrm{View}_M}^{(1)}=\sigma_M. \tag*{(27)} ρ View M ( 0 ) = ρ View M ( 1 ) = σ M . (27)
Consequently,
1 2 ∥ ρ V i e w M ( 0 ) − ρ V i e w M ( 1 ) ∥ 1 = 0 ≤ negl ( λ ) . (28) \frac{1}{2}\left\|\rho_{\mathrm{View}_M}^{(0)}-\rho_{\mathrm{View}_M}^{(1)}\right\|_1=0\leq\operatorname{negl}(\lambda). \tag*{(28)} 2 1 ρ View M ( 0 ) − ρ View M ( 1 ) 1 = 0 ≤ negl ( λ ) . (28)
Thus every unauthorized subset M M M with ∣ M ∣ < k |M|<k ∣ M ∣ < k has negligible distinguishing advantage between any two secret states. Therefore, the LVT-QSS scheme satisfies secrecy. □
Proof of Theorem 10
Proof. Let M ⊆ [ m ] M\subseteq[m] M ⊆ [ m ] be an unauthorized subset with ∣ M ∣ < k |M|<k ∣ M ∣ < k , and let T T T denote the classical register storing the tracing key t k tk t k generated by Setup ( 1 λ , m ) \operatorname{Setup}(1^\lambda,m) Setup ( 1 λ , m ) . By Theorem 9, the unauthorized view V i e w M = R M ⊗ A M \mathrm{View}_M=R_M\otimes A_M View M = R M ⊗ A M , without the tracing-key register T T T , is independent of the secret state. Hence, for any two secret states ∣ ψ 0 ⟩ |\psi_0\rangle ∣ ψ 0 ⟩ and ∣ ψ 1 ⟩ |\psi_1\rangle ∣ ψ 1 ⟩ , there exists a density operator σ M \sigma_M σ M , depending only on M M M and the public parameters, such that
ρ V i e w M ( 0 ) = ρ V i e w M ( 1 ) = σ M . (29) \rho_{\mathrm{View}_M}^{(0)}=\rho_{\mathrm{View}_M}^{(1)}=\sigma_M. \tag*{(29)} ρ View M ( 0 ) = ρ View M ( 1 ) = σ M . (29)
It remains to check that adding the tracing-key register T T T does not introduce any dependence on the secret. The tracing key t k tk t k is generated by Setup ( 1 λ , m ) \operatorname{Setup}(1^\lambda,m) Setup ( 1 λ , m ) independently of the secret input. Moreover, the auxiliary registers A M A_M A M are generated from t k tk t k , local randomness, and the user key, all of which are independent of which secret state is shared. Therefore, conditioned on any fixed tracing key t k tk t k , the unauthorized view is still independent of the secret. That is, for every t k tk t k ,
ρ V i e w M ∣ t k ( 0 ) = ρ V i e w M ∣ t k ( 1 ) . (30) \rho_{\mathrm{View}_M\mid tk}^{(0)}=\rho_{\mathrm{View}_M\mid tk}^{(1)}. \tag*{(30)} ρ View M ∣ t k ( 0 ) = ρ View M ∣ t k ( 1 ) . (30)
Since T T T is a classical register storing t k tk t k , the joint state on V i e w M ⊗ T \mathrm{View}_M\otimes T View M ⊗ T can be written as
ρ V i e w M , T ( b ) = ∑ t k p ( t k ) ∣ t k ⟩ ⟨ t k ∣ T ⊗ ρ V i e w M ∣ t k ( b ) , b ∈ { 0 , 1 } . (31) \rho_{\mathrm{View}_M,T}^{(b)}=\sum_{tk}p(tk)|tk\rangle\langle tk|_T\otimes\rho_{\mathrm{View}_M\mid tk}^{(b)},\quad b\in\{0,1\}. \tag*{(31)} ρ View M , T ( b ) = t k ∑ p ( t k ) ∣ t k ⟩ ⟨ t k ∣ T ⊗ ρ View M ∣ t k ( b ) , b ∈ { 0 , 1 } . (31)
Using the equality of the conditional views for every t k tk t k , we obtain
ρ V i e w M , T ( 0 ) = ρ V i e w M , T ( 1 ) . (32) \rho_{\mathrm{View}_M,T}^{(0)}=\rho_{\mathrm{View}_M,T}^{(1)}. \tag*{(32)} ρ View M , T ( 0 ) = ρ View M , T ( 1 ) . (32)
Consequently,
1 2 ∥ ρ V i e w M , T ( 0 ) − ρ V i e w M , T ( 1 ) ∥ 1 = 0 ≤ negl ( λ ) . (33) \frac{1}{2}\left\|\rho_{\mathrm{View}_M,T}^{(0)}-\rho_{\mathrm{View}_M,T}^{(1)}\right\|_1=0\leq\operatorname{negl}(\lambda). \tag*{(33)} 2 1 ρ View M , T ( 0 ) − ρ View M , T ( 1 ) 1 = 0 ≤ negl ( λ ) . (33)
Thus every unauthorized subset M M M with ∣ M ∣ < k |M|<k ∣ M ∣ < k has negligible distinguishing advantage between any two secret states even when the tracing key is included in its view. Therefore, the ( k , m ) (k,m) ( k , m ) -threshold LVT-QSS scheme satisfies tracer secrecy. □
Proof of Theorem 11
Theorem 11 (Formal). Assume that H : F → F H:\mathbb{F}\to\mathbb{F} H : F → F is quantum-secure collision resistant and preimage resistant, and that the symmetric-key encryption scheme Π S K E = ( Enc , Dec ) \Pi_{\mathrm{SKE}}=(\operatorname{Enc},\operatorname{Dec}) Π SKE = ( Enc , Dec ) satisfies the sparse-hit property with parameter α max ( λ ) \alpha_{\max}(\lambda) α m a x ( λ ) . Then, for any QPT adversary A A A , there exist a QPT algorithm B 1 B_1 B 1 and a negligible function negl ( ⋅ ) \operatorname{negl}(\cdot) negl ( ⋅ ) such that, for security parameter λ ∈ N \lambda\in\mathbb{N} λ ∈ N ,
Adv A , L V T - Q S S , ϵ t r a c e ( λ ) ≤ ϵ ( λ ) ( Adv B 1 , H ( λ ) + ℓ ( m − f ) α max ( λ ) + negl ( λ ) ) . (34) \operatorname{Adv}^{\mathrm{trace}}_{A,\mathrm{LVT\text{-}QSS},\epsilon}(\lambda)
\leq\epsilon(\lambda)\left(\operatorname{Adv}_{B_1,H}(\lambda)+\ell(m-f)\alpha_{\max}(\lambda)+\operatorname{negl}(\lambda)\right). \tag*{(34)} Adv A , LVT - QSS , ϵ trace ( λ ) ≤ ϵ ( λ ) ( Adv B 1 , H ( λ ) + ℓ ( m − f ) α m a x ( λ ) + negl ( λ ) ) . (34) where ℓ : = ∣ I ∖ I ′ ′ ∣ \ell:=|I\setminus I''| ℓ := ∣ I ∖ I ′′ ∣ . Consequently, if ℓ ( m − f ) = poly ( λ ) \ell(m-f)=\operatorname{poly}(\lambda) ℓ ( m − f ) = poly ( λ ) and α max ( λ ) \alpha_{\max}(\lambda) α m a x ( λ ) is negligible, then the LVT-QSS scheme is traceable.
Proof. Let I i d x ⊆ [ m ] I_{\mathrm{idx}}\subseteq[m] I idx ⊆ [ m ] be the set of leaked indices, with ∣ I i d x ∣ = f |I_{\mathrm{idx}}|=f ∣ I idx ∣ = f , and let I : = { t a g i ∣ i ∈ I i d x } ⊆ T a g s I:=\{tag_i\mid i\in I_{\mathrm{idx}}\}\subseteq Tags I := { t a g i ∣ i ∈ I idx } ⊆ T a g s be the corresponding leaked tag set. Let I ′ I' I ′ denote the output of SecretTrace, and let o k : = SecretVerify ( v k , I ′ ) ∈ { 0 , 1 } ok:=\operatorname{SecretVerify}(vk,I')\in\{0,1\} o k := SecretVerify ( v k , I ′ ) ∈ { 0 , 1 } . The traceability experiment fails precisely when the protocol executes correctly, but either verification rejects or it accepts an incorrect leaked tag set. Accordingly, define
E 1 : = { G ∧ o k = 0 } , (35) E_1:=\{G\land ok=0\}, \tag*{(35)} E 1 := { G ∧ o k = 0 } , (35)
E 2 : = { G ∧ o k = 1 ∧ I ′ ≠ I } . (36) E_2:=\{G\land ok=1\land I'\ne I\}. \tag*{(36)} E 2 := { G ∧ o k = 1 ∧ I ′ = I } . (36)
Then
Pr [ ExpTrace = 1 ] ≤ Pr [ E 1 ] + Pr [ E 2 ] . (37) \Pr[\operatorname{ExpTrace}=1]\leq\Pr[E_1]+\Pr[E_2]. \tag*{(37)} Pr [ ExpTrace = 1 ] ≤ Pr [ E 1 ] + Pr [ E 2 ] . (37)
By completeness of SecretVerify, one has
Pr [ E 1 ] ≤ negl ( λ ) . (38) \Pr[E_1]\leq\operatorname{negl}(\lambda). \tag*{(38)} Pr [ E 1 ] ≤ negl ( λ ) . (38)
Next decompose E 2 E_{2} E 2 into
E 2 f o r g e : = { G ∧ o k = 1 ∧ ∃ t a g ∗ ∈ T ′ : t a g ∗ ∉ T a g s } , (39) E_{2}^{\mathrm{forge}} := \{G \land ok = 1 \land\exists tag^{*} \in T^{\prime}: tag^{*} \notin Tags\}, \tag*{(39)} E 2 forge := { G ∧ o k = 1 ∧ ∃ t a g ∗ ∈ T ′ : t a g ∗ ∈ / T a g s } , (39)
E 2 w r o n g : = { G ∧ o k = 1 ∧ T ′ ⊆ T a g s ∧ T ′ ≠ T } . (40) E_{2}^{\mathrm{wrong}} := \{G \land ok = 1 \land T^{\prime} \subseteq Tags \land T^{\prime} \ne T\}. \tag*{(40)} E 2 wrong := { G ∧ o k = 1 ∧ T ′ ⊆ T a g s ∧ T ′ = T } . (40)
Thus
Pr [ E 2 ] ≤ Pr [ E 2 f o r g e ] + Pr [ E 2 w r o n g ] . (41) \Pr[E_{2}] \le\Pr[E_{2}^{\mathrm{forge}}] + \Pr[E_{2}^{\mathrm{wrong}}]. \tag*{(41)} Pr [ E 2 ] ≤ Pr [ E 2 forge ] + Pr [ E 2 wrong ] . (41)
If E 2 f o r g e E_{2}^{\mathrm{forge}} E 2 forge occurs, then some t a g ∗ ∈ T ′ ∖ T a g s tag^{*} \in T^{\prime} \setminus Tags t a g ∗ ∈ T ′ ∖ T a g s is accepted by SecretVerify. By the definition of SecretVerify, this implies H ( t a g ∗ ) ∈ { v k i } i = 0 m − 1 H(tag^{*}) \in\{vk_{i}\}_{i=0}^{m-1} H ( t a g ∗ ) ∈ { v k i } i = 0 m − 1 , and hence H ( t a g ∗ ) = H ( t a g j ) H(tag^{*}) = H(tag_{j}) H ( t a g ∗ ) = H ( t a g j ) for some t a g j ∈ T a g s tag_{j} \in Tags t a g j ∈ T a g s . Since t a g ∗ ≠ t a g j tag^{*} \ne tag_{j} t a g ∗ = t a g j , this yields a collision in H H H . Therefore,
Pr [ E 2 f o r g e ] ≤ Adv B 1 , H c o l l ( λ ) . (42) \Pr[E_{2}^{\mathrm{forge}}] \le\operatorname{Adv}^{\mathrm{coll}}_{\mathcal{B}_{1},H}(\lambda). \tag*{(42)} Pr [ E 2 forge ] ≤ Adv B 1 , H coll ( λ ) . (42)
Now suppose that E 2 w r o n g E_{2}^{\mathrm{wrong}} E 2 wrong occurs. Since T ′ ⊆ T a g s T^{\prime} \subseteq Tags T ′ ⊆ T a g s but T ′ ≠ T T^{\prime} \ne T T ′ = T and ∣ T ′ ∣ = ∣ T ∣ = f |T^{\prime}| = |T| = f ∣ T ′ ∣ = ∣ T ∣ = f , there exists some i ∉ I i d x i \notin I_{\mathrm{idx}} i ∈ / I idx such that t a g i ∈ T ′ tag_{i} \in T^{\prime} t a g i ∈ T ′ . By the tracing rule, this implies that for some r ∈ I ∖ I ′ ′ r \in I \setminus I^{\prime\prime} r ∈ I ∖ I ′′ , the first-layer decryption output Dec ( r , u k ) \operatorname{Dec}(r,uk) Dec ( r , u k ) falls into the set S i S_{i} S i of ciphertexts that decrypt to t a g i tag_{i} t a g i under the tracing key. By the sparse-hit property,
Pr [ Dec ( r , u k ) ∈ S i ] ≤ ∣ S i ∣ α max ( λ ) . (43) \Pr[\operatorname{Dec}(r,uk) \in S_{i}] \le|S_{i}| \alpha_{\max}(\lambda). \tag*{(43)} Pr [ Dec ( r , u k ) ∈ S i ] ≤ ∣ S i ∣ α m a x ( λ ) . (43)
Let l : = ∣ I ∖ I ′ ′ ∣ l := |I \setminus I^{\prime\prime}| l := ∣ I ∖ I ′′ ∣ . A union bound over all r ∈ I ∖ I ′ ′ r \in I \setminus I^{\prime\prime} r ∈ I ∖ I ′′ and all i ∉ I i d x i \notin I_{\mathrm{idx}} i ∈ / I idx gives
Pr [ E 2 w r o n g ] ≤ l ( m − f ) α max ( λ ) , (44) \Pr[E_{2}^{\mathrm{wrong}}] \le l(m-f)\alpha_{\max}(\lambda), \tag*{(44)} Pr [ E 2 wrong ] ≤ l ( m − f ) α m a x ( λ ) , (44)
absorbing the polynomial bound on ∣ S i ∣ |S_{i}| ∣ S i ∣ into α max ( λ ) \alpha_{\max}(\lambda) α m a x ( λ ) . Combining the above estimates, we obtain
Pr [ ExpTrace A , L V T - Q S S , ϵ ( λ ) = 1 ] ≤ Adv B 1 , H c o l l ( λ ) + l ( m − f ) α max ( λ ) + negl ( λ ) . (45) \Pr[\operatorname{ExpTrace}_{\mathcal{A},\mathrm{LVT\text{-}QSS},\epsilon}(\lambda)=1]
\le\operatorname{Adv}^{\mathrm{coll}}_{\mathcal{B}_{1},H}(\lambda)
+l(m-f)\alpha_{\max}(\lambda)+\operatorname{negl}(\lambda). \tag*{(45)} Pr [ ExpTrace A , LVT - QSS , ϵ ( λ ) = 1 ] ≤ Adv B 1 , H coll ( λ ) + l ( m − f ) α m a x ( λ ) + negl ( λ ) . (45)
Therefore,
Adv A , L V T - Q S S , ϵ t r a c e ( λ ) = ϵ Pr [ ExpTrace A , L V T - Q S S , ϵ ( λ ) = 1 ] ≤ ϵ ( Adv B 1 , H c o l l ( λ ) + l ( m − f ) α max ( λ ) + negl ( λ ) ) . (46) \begin{aligned}
\operatorname{Adv}^{\mathrm{trace}}_{\mathcal{A},\mathrm{LVT\text{-}QSS},\epsilon}(\lambda)
&= \epsilon\Pr[\operatorname{ExpTrace}_{\mathcal{A},\mathrm{LVT\text{-}QSS},\epsilon}(\lambda)=1] \\
&\le\epsilon\bigl(\operatorname{Adv}^{\mathrm{coll}}_{\mathcal{B}_{1},H}(\lambda)
+l(m-f)\alpha_{\max}(\lambda)+\operatorname{negl}(\lambda)\bigr). \tag*{(46)}
\end{aligned} Adv A , LVT - QSS , ϵ trace ( λ ) = ϵ Pr [ ExpTrace A , LVT - QSS , ϵ ( λ ) = 1 ] ≤ ϵ ( Adv B 1 , H coll ( λ ) + l ( m − f ) α m a x ( λ ) + negl ( λ ) ) . (46)
Since Adv B 1 , H c o l l ( λ ) \operatorname{Adv}^{\mathrm{coll}}_{\mathcal{B}_{1},H}(\lambda) Adv B 1 , H coll ( λ ) is negligible, l ( m − f ) = poly ( λ ) l(m-f)=\operatorname{poly}(\lambda) l ( m − f ) = poly ( λ ) , and α max ( λ ) \alpha_{\max}(\lambda) α m a x ( λ ) is negligible, the right-hand side is negligible. Therefore, the LVT-QSS scheme is traceable. □ \square □
Proof of Theorem 12
Theorem 12 (Formal). Assume that H : F → F H:\mathbb{F}\to\mathbb{F} H : F → F is quantum-secure collision-resistant and preimage-resistant. Then, for any QPT adversary A \mathcal{A} A , there exist QPT algorithms B 2 p r e \mathcal{B}_{2}^{\mathrm{pre}} B 2 pre and B 2 c o l l \mathcal{B}_{2}^{\mathrm{coll}} B 2 coll , and a negligible function negl ( ⋅ ) \operatorname{negl}(\cdot) negl ( ⋅ ) , such that, for security parameter λ ∈ N \lambda\in\mathbb{N} λ ∈ N ,
Adv A , L V T - Q S S n i ( λ ) ≤ Adv B 2 p r e , H p r e ( λ ) + Adv B 2 c o l l , H c o l l ( λ ) + negl ( λ ) . (47) \operatorname{Adv}^{\mathrm{ni}}_{\mathcal{A},\mathrm{LVT\text{-}QSS}}(\lambda)
\le\operatorname{Adv}^{\mathrm{pre}}_{\mathcal{B}_{2}^{\mathrm{pre}},H}(\lambda)
+\operatorname{Adv}^{\mathrm{coll}}_{\mathcal{B}_{2}^{\mathrm{coll}},H}(\lambda)
+\operatorname{negl}(\lambda). \tag*{(47)} Adv A , LVT - QSS ni ( λ ) ≤ Adv B 2 pre , H pre ( λ ) + Adv B 2 coll , H coll ( λ ) + negl ( λ ) . (47) Consequently, the LVT-QSS scheme is non-imputable.
Proof. Let A \mathcal{A} A be an arbitrary QPT adversary in the non-imputability experiment ExpNI A , L V T - Q S S ( λ ) \operatorname{ExpNI}_{\mathcal{A},\mathrm{LVT\text{-}QSS}}(\lambda) ExpNI A , LVT - QSS ( λ ) . We show that any successful adversary yields either a preimage or a collision for H H H .
Game 0. This is the real experiment ExpNI A , L V T - Q S S ( λ ) \operatorname{ExpNI}_{\mathcal{A},\mathrm{LVT\text{-}QSS}}(\lambda) ExpNI A , LVT - QSS ( λ ) . Setup generates pairwise distinct tags T a g s = { t a g i } i ∈ [ m ] Tags=\{tag_{i}\}_{i\in[m]} T a g s = { t a g i } i ∈ [ m ] , and the verification keys are v k i : = H ( t a g i ) vk_{i}:=H(tag_{i}) v k i := H ( t a g i ) .
Game 1. This game is identical to Game 0 except that, after GenSecretShares, the verification key of the challenged honest party i ∗ i^{*} i ∗ is replaced by v k i ∗ : = y ∗ vk_{i^{*}}:=y^{*} v k i ∗ := y ∗ , where y ∗ = H ( w ∗ ) y^{*}=H(w^{*}) y ∗ = H ( w ∗ ) and w ∗ ← $ F w^{*}\mathrel{\leftarrow^{\$}}\mathbb{F} w ∗ ← $ F is sampled independently.
Because t a g i ∗ tag_{i^{*}} t a g i ∗ and w ∗ w^{*} w ∗ are sampled from the same distribution, the values H ( t a g i ∗ ) H(tag_{i^{*}}) H ( t a g i ∗ ) and H ( w ∗ ) H(w^{*}) H ( w ∗ ) are identically distributed. Therefore, the adversary’s views in Games 0 and 1 are identically distributed, and
Pr [ ExpNI A , L V T - Q S S ( λ ) = 1 ] = Pr [ ExpNI A , L V T - Q S S ( 1 ) ( λ ) = 1 ] . (48) \Pr[\operatorname{ExpNI}_{\mathcal{A},\mathrm{LVT\text{-}QSS}}(\lambda)=1]
=
\Pr[\operatorname{ExpNI}_{\mathcal{A},\mathrm{LVT\text{-}QSS}}^{(1)}(\lambda)=1]. \tag*{(48)} Pr [ ExpNI A , LVT - QSS ( λ ) = 1 ] = Pr [ ExpNI A , LVT - QSS ( 1 ) ( λ ) = 1 ] . (48)
Suppose that ExpNI A , L V T - Q S S ( 1 ) ( λ ) = 1 \operatorname{ExpNI}_{\mathcal{A},\mathrm{LVT\text{-}QSS}}^{(1)}(\lambda)=1 ExpNI A , LVT - QSS ( 1 ) ( λ ) = 1 . Then the adversary outputs a set I ∗ I^{*} I ∗ containing a tag t a g ∗ tag^{*} t a g ∗ attributed to the challenged honest party i ∗ i^{*} i ∗ , and SecretVerify( v k , I ∗ ) = 1 (vk,I^{*})=1 ( v k , I ∗ ) = 1 . By the definition of SecretVerify,
H ( t a g ∗ ) ∈ { v k i } i = 0 m − 1 . H(tag^{*}) \in\{vk_{i}\}_{i=0}^{m-1}. H ( t a g ∗ ) ∈ { v k i } i = 0 m − 1 .
In Game 1,
{ v k i } i = 0 m − 1 = { y ∗ } ∪ { H ( t a g i ) } i ≠ i ∗ . \{vk_{i}\}_{i=0}^{m-1}=\{y^{*}\}\cup\{H(tag_{i})\}_{i\ne i^{*}}. { v k i } i = 0 m − 1 = { y ∗ } ∪ { H ( t a g i ) } i = i ∗ .
There are two cases. If H ( t a g ∗ ) = y ∗ H(tag^{*})=y^{*} H ( t a g ∗ ) = y ∗ , then t a g ∗ tag^{*} t a g ∗ is a valid preimage of H H H under the random image y ∗ y^{*} y ∗ . This event can therefore be used to construct a QPT algorithm B 2 p r e \mathcal{B}_{2}^{\mathrm{pre}} B 2 pre that, on input y ∗ y^{*} y ∗ , outputs t a g ∗ tag^{*} t a g ∗ as a valid preimage, thereby violating the preimage resistance of H H H . Hence,
Pr [ H ( t a g ∗ ) = y ∗ ] ≤ Adv B 2 p r e , H p r e ( λ ) . (49) \Pr[H(tag^{*})=y^{*}] \le\operatorname{Adv}^{\mathrm{pre}}_{\mathcal{B}_{2}^{\mathrm{pre}},H}(\lambda). \tag*{(49)} Pr [ H ( t a g ∗ ) = y ∗ ] ≤ Adv B 2 pre , H pre ( λ ) . (49)
If H ( t a g ∗ ) = H ( t a g i ) H(tag^{*})=H(tag_{i}) H ( t a g ∗ ) = H ( t a g i ) for some i ≠ i ∗ i\ne i^{*} i = i ∗ , then, since the tags are distinct, t a g ∗ ≠ t a g i tag^{*}\ne tag_{i} t a g ∗ = t a g i , and the pair ( t a g ∗ , t a g i ) (tag^{*},tag_{i}) ( t a g ∗ , t a g i ) is a collision for H H H . This event can therefore be used to construct a QPT algorithm B 2 c o l l \mathcal{B}_{2}^{\mathrm{coll}} B 2 coll that outputs this pair, thereby violating the collision resistance of H H H . Thus,
Pr [ ∃ i ≠ i ∗ : H ( t a g ∗ ) = H ( t a g i ) ] ≤ Adv B 2 c o l l , H c o l l ( λ ) . (50) \Pr[\exists i\ne i^{*}:H(tag^{*})=H(tag_{i})]
\le\operatorname{Adv}^{\mathrm{coll}}_{\mathcal{B}_{2}^{\mathrm{coll}},H}(\lambda). \tag*{(50)} Pr [ ∃ i = i ∗ : H ( t a g ∗ ) = H ( t a g i )] ≤ Adv B 2 coll , H coll ( λ ) . (50)
Since a successful execution of Game 1 implies one of these two cases, we obtain
Adv A , L V T - Q S S n i ( λ ) ≤ Adv B 2 p r e , H p r e ( λ ) + Adv B 2 c o l l , H c o l l ( λ ) . (51) \operatorname{Adv}^{\mathrm{ni}}_{\mathcal{A},\mathrm{LVT\text{-}QSS}}(\lambda)
\le\operatorname{Adv}^{\mathrm{pre}}_{\mathcal{B}_{2}^{\mathrm{pre}},H}(\lambda)
+\operatorname{Adv}^{\mathrm{coll}}_{\mathcal{B}_{2}^{\mathrm{coll}},H}(\lambda). \tag*{(51)} Adv A , LVT - QSS ni ( λ ) ≤ Adv B 2 pre , H pre ( λ ) + Adv B 2 coll , H coll ( λ ) . (51)
Because H H H is quantum-secure preimage resistant and collision resistant, the right-hand side is negligible in λ \lambda λ . Therefore, the LVT-QSS scheme is non-imputable. □ \square □
Formal Definitions of MTA-QSS
Correctness
Definition 28 (Correctness (formal)). An MTA-QSS scheme is correct if there exists a negligible function negl ( ⋅ ) \operatorname{negl}(\cdot) negl ( ⋅ ) such that, for security parameter λ ∈ N \lambda\in\mathbb{N} λ ∈ N , number of parties m ∈ N m \in\mathbb{N} m ∈ N , threshold k k k with 1 ≤ k ≤ m 1 \le k \le m 1 ≤ k ≤ m , subset P ⊆ [ m ] P \subseteq[m] P ⊆ [ m ] with ∣ P ∣ ≥ k |P| \ge k ∣ P ∣ ≥ k , and secret state ∣ ψ ⟩ ∈ H λ |\psi\rangle\in\mathcal{H}_{\lambda} ∣ ψ ⟩ ∈ H λ , the following holds.
Let ρ : = ∣ ψ ⟩ ⟨ ψ ∣ \rho:= |\psi\rangle\langle\psi| ρ := ∣ ψ ⟩ ⟨ ψ ∣ . Generate the shares and run the reconstruction algorithm as
( t k , T a g s ) ← S e t u p ( 1 λ , m ) , ( s h , v k , u k , c k ) ← G e n S e c r e t S h a r e s ( ∣ ψ ⟩ , m , k , T a g s , t k ) , o u t ← S e c r e t R e c o v e r ( { ∣ s h i ⟩ } i ∈ P ) . (52) \begin{aligned}
(tk,Tags)&\leftarrow Setup(1^{\lambda},m),\\
(sh,vk,uk,ck)&\leftarrow GenSecretShares(|\psi\rangle,m,k,Tags,tk),\\
out&\leftarrow SecretRecover(\{ |sh_i\rangle\}_{i\in P}). \tag*{(52)}
\end{aligned} ( t k , T a g s ) ( s h , v k , u k , c k ) o u t ← S e t u p ( 1 λ , m ) , ← G e n S ecr e tS ha r es ( ∣ ψ ⟩ , m , k , T a g s , t k ) , ← S ecr e tR eco v er ({ ∣ s h i ⟩ } i ∈ P ) . (52) where t k : = { t k i } i = 0 m − 1 tk := \{tk_i\}_{i=0}^{m-1} t k := { t k i } i = 0 m − 1 , s h : = { ∣ s h i ⟩ } i = 0 m − 1 sh := \{|sh_i\rangle\}_{i=0}^{m-1} s h := { ∣ s h i ⟩ } i = 0 m − 1 , and v k : = { v k i } i = 0 m − 1 vk := \{vk_i\}_{i=0}^{m-1} v k := { v k i } i = 0 m − 1 .
Then
Pr [ o u t = ( ρ ′ , ⋅ ) and 1 2 ∥ ρ ′ − ρ ∥ 1 ≤ negl ( λ ) ] ≥ 1 − negl ( λ ) . (53) \Pr\left[out=(\rho',\cdot)\ \text{and}\ \frac{1}{2}\left\|\rho'-\rho\right\|_1\leq\operatorname{negl}(\lambda)\right]\geq1-\operatorname{negl}(\lambda). \tag*{(53)} Pr [ o u t = ( ρ ′ , ⋅ ) and 2 1 ∥ ρ ′ − ρ ∥ 1 ≤ negl ( λ ) ] ≥ 1 − negl ( λ ) . (53) where the probability is taken over the internal randomness of Setup, GenSecretShares, and SecretRecover.
This requirement applies only when all shares used in reconstruction are honestly generated by GenSecretShares. No correctness guarantee is required when some of the input shares are forged or adversarially corrupted.
Tracer secrecy
Definition 29 (Tracer secrecy (formal)). Let H = { H λ } λ ∈ N \mathcal{H}=\{\mathcal{H}_{\lambda}\}_{\lambda\in\mathbb{N}} H = { H λ } λ ∈ N denote the secret-state spaces of an MTA-QSS scheme. For every M ⊆ [ m ] M\subseteq[m] M ⊆ [ m ] with ∣ M ∣ < k |M|<k ∣ M ∣ < k and any two secret states ∣ ψ 0 ⟩ , ∣ ψ 1 ⟩ ∈ H λ |\psi_0\rangle,|\psi_1\rangle\in\mathcal{H}_{\lambda} ∣ ψ 0 ⟩ , ∣ ψ 1 ⟩ ∈ H λ , define
View M : = ⨂ i ∈ M ( R i ⊗ A i ) , T : = ⨂ i = 0 m − 1 t k i , Y : = u k \operatorname{View}_{M}:=\bigotimes_{i\in M}(R_i\otimes A_i),\qquad T:=\bigotimes_{i=0}^{m-1}tk_i,\qquad Y:=uk View M := i ∈ M ⨂ ( R i ⊗ A i ) , T := i = 0 ⨂ m − 1 t k i , Y := u k and let ρ View M , T , Y ( b ) \rho_{\operatorname{View}_{M,T,Y}}^{(b)} ρ View M , T , Y ( b ) be the reduced state generated by sharing ∣ ψ b ⟩ |\psi_b\rangle ∣ ψ b ⟩ , for b ∈ { 0 , 1 } b\in\{0,1\} b ∈ { 0 , 1 } . Then there exists a negligible function negl ( ⋅ ) \operatorname{negl}(\cdot) negl ( ⋅ ) such that, for security parameter λ ∈ N \lambda\in\mathbb{N} λ ∈ N ,
1 2 ∥ ρ View M , T , Y ( 0 ) − ρ View M , T , Y ( 1 ) ∥ 1 ≤ negl ( λ ) . \frac{1}{2}\left\|\rho_{\operatorname{View}_{M,T,Y}}^{(0)}-\rho_{\operatorname{View}_{M,T,Y}}^{(1)}\right\|_1\leq\operatorname{negl}(\lambda). 2 1 ρ View M , T , Y ( 0 ) − ρ View M , T , Y ( 1 ) 1 ≤ negl ( λ ) .
Traceability
We define the following tracing experiment. Let A \mathcal{A} A be a QPT adversary, let ∣ ψ ⟩ ∈ H λ |\psi\rangle\in\mathcal{H}_{\lambda} ∣ ψ ⟩ ∈ H λ be an arbitrary secret state, and let T a g s = { t a g i } i = 0 m − 1 Tags=\{tag_i\}_{i=0}^{m-1} T a g s = { t a g i } i = 0 m − 1 , where t a g i tag_i t a g i uniquely identifies party i i i .
Experiment 3 ExpTrace A , M T A - Q S S ( λ ) \operatorname{ExpTrace}_{\mathcal{A},\mathrm{MTA\text{-}QSS}}(\lambda) ExpTrace A , MTA - QSS ( λ )
( m , k , V i d x , s t ) ← A ( 1 λ ) (m,k,V_{\mathrm{idx}},st)\leftarrow\mathcal{A}(1^{\lambda}) ( m , k , V idx , s t ) ← A ( 1 λ ) , where V i d x = { i 0 , … , i t − 1 } ⊆ [ m ] V_{\mathrm{idx}}=\{i_0,\ldots,i_{t-1}\}\subseteq[m] V idx = { i 0 , … , i t − 1 } ⊆ [ m ] denotes the set of participants corrupted by A \mathcal{A} A .
( { t k i } i = 0 m − 1 , T a g s ) ← S e t u p ( 1 λ , m ) (\{tk_i\}_{i=0}^{m-1},Tags)\leftarrow Setup(1^{\lambda},m) ({ t k i } i = 0 m − 1 , T a g s ) ← S e t u p ( 1 λ , m ) .
( { ∣ s h i ⟩ } i = 0 m − 1 , { v k i } i = 0 m − 1 , u k , c k ) ← G e n S e c r e t S h a r e s ( ∣ ψ ⟩ , m , k , T a g s , { t k i } i = 0 m − 1 ) (\{|sh_i\rangle\}_{i=0}^{m-1},\{vk_i\}_{i=0}^{m-1},uk,ck)\leftarrow GenSecretShares(|\psi\rangle,m,k,Tags,\{tk_i\}_{i=0}^{m-1}) ({ ∣ s h i ⟩ } i = 0 m − 1 , { v k i } i = 0 m − 1 , u k , c k ) ← G e n S ecr e tS ha r es ( ∣ ψ ⟩ , m , k , T a g s , { t k i } i = 0 m − 1 ) .
Set t k : = ( t k 0 , … , t k m − 1 ) tk:=(tk_0,\ldots,tk_{m-1}) t k := ( t k 0 , … , t k m − 1 ) , and v k : = ( v k 0 , … , v k m − 1 ) vk:=(vk_0,\ldots,vk_{m-1}) v k := ( v k 0 , … , v k m − 1 ) .
Sample a subset U i d x ⊆ [ m ] ∖ V i d x U_{\mathrm{idx}}\subseteq[m]\setminus V_{\mathrm{idx}} U idx ⊆ [ m ] ∖ V idx uniformly at random subject to ∣ U i d x ∣ = k − t |U_{\mathrm{idx}}|=k-t ∣ U idx ∣ = k − t . Define P : = U i d x ∪ V i d x P:=U_{\mathrm{idx}}\cup V_{\mathrm{idx}} P := U idx ∪ V idx , and let U : = { t a g i : i ∈ U i d x } U:=\{tag_i:i\in U_{\mathrm{idx}}\} U := { t a g i : i ∈ U idx } and V : = { t a g i : i ∈ V i d x } V:=\{tag_i:i\in V_{\mathrm{idx}}\} V := { t a g i : i ∈ V idx } .
{ ∣ s h i m a l ⟩ } i ∈ V i d x ← A ( s t , { ∣ s h i ⟩ } i ∈ V i d x ) \{|sh_i^{\mathrm{mal}}\rangle\}_{i\in V_{\mathrm{idx}}}\leftarrow\mathcal{A}(st,\{|sh_i\rangle\}_{i\in V_{\mathrm{idx}}}) { ∣ s h i mal ⟩ } i ∈ V idx ← A ( s t , { ∣ s h i ⟩ } i ∈ V idx ) . For each i ∈ P i\in P i ∈ P , define
∣ s h i ~ ⟩ : = { ∣ s h i m a l ⟩ , i ∈ V i d x , ∣ s h i ⟩ , i ∈ U i d x . |\widetilde{sh_i}\rangle:=
\begin{cases}
|sh_i^{\mathrm{mal}}\rangle, & i\in V_{\mathrm{idx}},\\
|sh_i\rangle, & i\in U_{\mathrm{idx}}.
\end{cases} ∣ s h i ⟩ := { ∣ s h i mal ⟩ , ∣ s h i ⟩ , i ∈ V idx , i ∈ U idx . ( ∣ ψ ′ ⟩ , I ) ← S e c r e t R e c o v e r ( { ∣ s h i ~ ⟩ } i ∈ P ) (|\psi'\rangle,I)\leftarrow SecretRecover(\{|\widetilde{sh_i}\rangle\}_{i\in P}) ( ∣ ψ ′ ⟩ , I ) ← S ecr e tR eco v er ({ ∣ s h i ⟩ } i ∈ P ) .
( U ′ , V ′ ) ← S e c r e t T r a c e ( t k , u k , I ) (U',V')\leftarrow SecretTrace(tk,uk,I) ( U ′ , V ′ ) ← S ecr e tT r a ce ( t k , u k , I ) .
Output 0 0 0 if U ′ = U U'=U U ′ = U and S e c r e t V e r i f y ( v k , u k , c k , U ′ , V ′ , I ) = 1 SecretVerify(vk,uk,ck,U',V',I)=1 S ecr e t V er i f y ( v k , u k , c k , U ′ , V ′ , I ) = 1 ; otherwise output 1 1 1 .
Definition 30 (Traceability (formal)). For any QPT adversary A \mathcal{A} A , define its tracing advantage as
Adv A , M T A - Q S S t r a c e ( λ ) : = Pr [ ExpTrace A , M T A - Q S S ( λ ) = 1 ] . (54) \operatorname{Adv}_{\mathcal{A},\mathrm{MTA\text{-}QSS}}^{\mathrm{trace}}(\lambda):=\Pr[\operatorname{ExpTrace}_{\mathcal{A},\mathrm{MTA\text{-}QSS}}(\lambda)=1]. \tag*{(54)} Adv A , MTA - QSS trace ( λ ) := Pr [ ExpTrace A , MTA - QSS ( λ ) = 1 ] . (54) The MTA-QSS scheme is traceable if the tracing advantage of every QPT adversary is negligible in λ \lambda λ .
Non-imputability
We define the following non-imputability experiment. Let A \mathcal{A} A be a QPT adversary, let λ \lambda λ be the security parameter, and let ∣ ψ ⟩ ∈ H λ |\psi\rangle\in\mathcal{H}_{\lambda} ∣ ψ ⟩ ∈ H λ be an arbitrary secret quantum state.
Experiment 4 ExpNI A , M T A - Q S S ( λ ) \operatorname{ExpNI}_{\mathcal{A},\mathrm{MTA\text{-}QSS}}(\lambda) ExpNI A , MTA - QSS ( λ )
( m , k , i ∗ , s t ) ← A ( 1 λ ) (m,k,i^*,st)\leftarrow\mathcal{A}(1^{\lambda}) ( m , k , i ∗ , s t ) ← A ( 1 λ ) , where i ∗ ∈ [ m ] i^*\in[m] i ∗ ∈ [ m ] is the index of the honest party that A \mathcal{A} A attempts to frame.
( { t k i } i = 0 m − 1 , T a g s ) ← S e t u p ( 1 λ , m ) (\{tk_i\}_{i=0}^{m-1},Tags)\leftarrow Setup(1^{\lambda},m) ({ t k i } i = 0 m − 1 , T a g s ) ← S e t u p ( 1 λ , m ) , where T a g s = ( t a g 0 , … , t a g m − 1 ) Tags=(tag_0,\ldots,tag_{m-1}) T a g s = ( t a g 0 , … , t a g m − 1 ) . Define t a g ∗ : = t a g i ∗ tag^*:=tag_{i^*} t a g ∗ := t a g i ∗ .
( { ∣ s h i ⟩ } i = 0 m − 1 , { v k i } i = 0 m − 1 , u k , c k ) ← GenSecretShares ( ∣ ψ ⟩ , m , k , Tags , { t k i } i = 0 m − 1 ) \left(\{|sh_i\rangle\}_{i=0}^{m-1},\{v_{ki}\}_{i=0}^{m-1},u_k,c_k\right)\leftarrow\operatorname{GenSecretShares}(|\psi\rangle,m,k,\operatorname{Tags},\{tk_i\}_{i=0}^{m-1}) ( { ∣ s h i ⟩ } i = 0 m − 1 , { v k i } i = 0 m − 1 , u k , c k ) ← GenSecretShares ( ∣ ψ ⟩ , m , k , Tags , { t k i } i = 0 m − 1 ) .
Set t k : = ( t k 0 , … , t k m − 1 ) tk := (tk_0,\ldots,tk_{m-1}) t k := ( t k 0 , … , t k m − 1 ) and v k : = ( v k 0 , … , v k m − 1 ) vk := (vk_0,\ldots,vk_{m-1}) v k := ( v k 0 , … , v k m − 1 ) .
Sample a subset P r e s t ⊆ [ m ] ∖ { i ∗ } P_{\mathrm{rest}}\subseteq[m]\setminus\{i^*\} P rest ⊆ [ m ] ∖ { i ∗ } uniformly at random subject to ∣ P r e s t ∣ = k − 1 |P_{\mathrm{rest}}|=k-1 ∣ P rest ∣ = k − 1 , and define P : = P r e s t ∪ { i ∗ } P := P_{\mathrm{rest}}\cup\{i^*\} P := P rest ∪ { i ∗ } .
Then compute
( ⋅ , I ) ← SecretRecover ( { ∣ s h i ⟩ } i ∈ P ) . (\cdot,I)\leftarrow\operatorname{SecretRecover}(\{|sh_i\rangle\}_{i\in P}). ( ⋅ , I ) ← SecretRecover ({ ∣ s h i ⟩ } i ∈ P ) .
( U ∗ , V ∗ ) ← A ( s t , { ∣ s h i ⟩ } i ∈ [ m ] ∖ { i ∗ } , t k , v k , I ) (U^*,V^*)\leftarrow\mathcal{A}(st,\{|sh_i\rangle\}_{i\in[m]\setminus\{i^*\}},tk,vk,I) ( U ∗ , V ∗ ) ← A ( s t , { ∣ s h i ⟩ } i ∈ [ m ] ∖ { i ∗ } , t k , v k , I ) .
Output 1 1 1 if t a g ∗ ∈ V ∗ tag^*\in V^* t a g ∗ ∈ V ∗ and SecretVerify ( v k , u k , c k , U ∗ , V ∗ , I ) = 1 \operatorname{SecretVerify}(vk,u_k,c_k,U^*,V^*,I)=1 SecretVerify ( v k , u k , c k , U ∗ , V ∗ , I ) = 1 ; otherwise output 0 0 0 .
Definition 31 (Non-imputability (formal)). For any QPT adversary A \mathcal{A} A , define its non-imputability advantage as
Adv A , M T A - Q S S n i ( λ ) : = Pr [ ExpNI A , M T A - Q S S ( λ ) = 1 ] . (55) \operatorname{Adv}^{\mathrm{ni}}_{\mathcal{A},\mathrm{MTA\text{-}QSS}}(\lambda):=\Pr[\operatorname{ExpNI}_{\mathcal{A},\mathrm{MTA\text{-}QSS}}(\lambda)=1]. \tag*{(55)} Adv A , MTA - QSS ni ( λ ) := Pr [ ExpNI A , MTA - QSS ( λ ) = 1 ] . (55)
The MTA-QSS scheme is non-imputable if the non-imputability advantage of every QPT adversary is negligible in λ \lambda λ .
Proofs of MTA-QSS
Proof of Theorem 17
Proof. It is sufficient to consider honestly generated shares. For such shares, the MTA-QSS scheme uses exactly the same coherent ( k , m ) (k,m) ( k , m ) -threshold encoding on the quantum share registers as the LVT-QSS scheme, and the reconstruction procedure SecretRecover applies the same decoding map on these registers.
The two schemes differ only in the auxiliary classical registers. In MTA-QSS, the auxiliary register associated with the j j j th share stores ( r j ∥ t k j ) (r_j\|tk_j) ( r j ∥ t k j ) , whereas in LVT-QSS it stores only r j r_j r j . These auxiliary registers do not affect the decoding operation on the quantum share registers and therefore do not alter the recovered secret state.
It follows that, for honestly generated shares, the reduced state on the output secret register in MTA-QSS is identical to that in LVT-QSS. Since correctness for LVT-QSS was established in Theorem 8 , the MTA-QSS scheme is correct. □ \square □
Proof of Theorem 18
Proof. Let M ⊆ [ m ] M\subseteq[m] M ⊆ [ m ] be any unauthorized set with ∣ M ∣ < k |M|<k ∣ M ∣ < k . For each b ∈ { 0 , 1 } b\in\{0,1\} b ∈ { 0 , 1 } , let ρ V i e w M ( b ) \rho^{(b)}_{\mathrm{View}_M} ρ View M ( b ) denote the reduced state on the registers R M ⊗ A M R_M\otimes A_M R M ⊗ A M when the shared secret is the input state corresponding to b b b .
On the quantum share registers, the MTA-QSS scheme uses exactly the same encoding as the LVT-QSS scheme. Hence, by the same argument as in the proof of Theorem 9 , the reduced state on R M R_M R M is independent of the secret for every unauthorized set M M M .
It remains to consider the auxiliary registers A M A_M A M . In MTA-QSS, these registers contain only classical values derived from protocol randomness, such as tags and tracing-related data, and are independent of the input secret state. Consequently, the joint reduced state on R M ⊗ A M R_M\otimes A_M R M ⊗ A M is also independent of the secret. In particular,
ρ V i e w M ( 0 ) = ρ V i e w M ( 1 ) . (56) \rho^{(0)}_{\mathrm{View}_M}=\rho^{(1)}_{\mathrm{View}_M}. \tag*{(56)} ρ View M ( 0 ) = ρ View M ( 1 ) . (56)
Therefore,
1 2 ∥ ρ V i e w M ( 0 ) − ρ V i e w M ( 1 ) ∥ t r = 0 ≤ negl ( λ ) . (57) \frac{1}{2}\left\|\rho^{(0)}_{\mathrm{View}_M}-\rho^{(1)}_{\mathrm{View}_M}\right\|_{\mathrm{tr}}=0\leq\operatorname{negl}(\lambda). \tag*{(57)} 2 1 ρ View M ( 0 ) − ρ View M ( 1 ) tr = 0 ≤ negl ( λ ) . (57)
Hence, the ( k , m ) (k,m) ( k , m ) -threshold MTA-QSS scheme satisfies secrecy. □ \square □
Proof of Theorem 19
Proof. Fix any unauthorized set M ⊆ [ m ] M\subseteq[m] M ⊆ [ m ] with ∣ M ∣ < k |M|<k ∣ M ∣ < k and any two secret states ∣ ψ 0 ⟩ , ∣ ψ 1 ⟩ ∈ H λ |\psi_0\rangle,|\psi_1\rangle\in\mathcal{H}_\lambda ∣ ψ 0 ⟩ , ∣ ψ 1 ⟩ ∈ H λ . Let
( { t k i } i = 0 m − 1 , Tags ) ← Setup ( 1 λ , m ) , (\{tk_i\}_{i=0}^{m-1},\operatorname{Tags})\leftarrow\operatorname{Setup}(1^\lambda,m), ({ t k i } i = 0 m − 1 , Tags ) ← Setup ( 1 λ , m ) ,
set t k : = ( t k 0 , … , t k m − 1 ) tk := (tk_0,\ldots,tk_{m-1}) t k := ( t k 0 , … , t k m − 1 ) , and let T T T be the classical register storing t k tk t k .
For each b ∈ { 0 , 1 } b\in\{0,1\} b ∈ { 0 , 1 } , run ( { ∣ s h i ( b ) ⟩ } i = 0 m − 1 , ⋅ , u k ( b ) , ⋅ ) ← GenSecretShares ( ∣ ψ b ⟩ , m , k , Tags , t k ) (\{|sh_i^{(b)}\rangle\}_{i=0}^{m-1},\cdot, u_k^{(b)},\cdot)\leftarrow\operatorname{GenSecretShares}(|\psi_b\rangle,m,k,\operatorname{Tags},tk) ({ ∣ s h i ( b ) ⟩ } i = 0 m − 1 , ⋅ , u k ( b ) , ⋅ ) ← GenSecretShares ( ∣ ψ b ⟩ , m , k , Tags , t k ) , and let Y Y Y be the classical register storing u k ( b ) u_k^{(b)} u k ( b ) . Write ρ V i e w M , T , Y ( b ) \rho^{(b)}_{\mathrm{View}_M,T,Y} ρ View M , T , Y ( b ) for the reduced state on
V i e w M ⊗ T ⊗ Y = R M ⊗ A M ⊗ T ⊗ Y . \mathrm{View}_M\otimes T\otimes Y=R_M\otimes A_M\otimes T\otimes Y. View M ⊗ T ⊗ Y = R M ⊗ A M ⊗ T ⊗ Y .
By secrecy, the reduced state on the quantum share registers held by M M M is independent of the input secret. The remaining registers in the above view are classical: the auxiliary registers contain values of the form r i ∥ t k i r_i\|tk_i r i ∥ t k i , the register T T T contains the tracing keys, and Y Y Y contains u k ( b ) u_k^{(b)} u k ( b ) . These values are generated from protocol randomness and tracing data, independently of the input secret state. Hence, for every fixed value of t k tk t k , the conditional state on V i e w M ⊗ Y \mathrm{View}_M\otimes Y View M ⊗ Y is independent of b b b ; denote it by ρ V i e w M , Y ∣ t k \rho_{\mathrm{View}_M,Y\mid tk} ρ View M , Y ∣ t k .
Since T T T is classical, the joint state has the cq decomposition
ρ V i e w M , T , Y ( b ) = ∑ t k p ( t k ) ∣ t k ⟩ ⟨ t k ∣ T ⊗ ρ V i e w M , Y ∣ t k . (58) \rho^{(b)}_{\mathrm{View}_M,T,Y}
=
\sum_{tk}p(tk)\,|tk\rangle\langle tk|_T\otimes\rho_{\mathrm{View}_M,Y\mid tk}. \tag*{(58)} ρ View M , T , Y ( b ) = t k ∑ p ( t k ) ∣ t k ⟩ ⟨ t k ∣ T ⊗ ρ View M , Y ∣ t k . (58)
which is independent of b b b . Therefore,
ρ V i e w M , T , Y ( 0 ) = ρ V i e w M , T , Y ( 1 ) . (59) \rho^{(0)}_{\mathrm{View}_M,T,Y}=\rho^{(1)}_{\mathrm{View}_M,T,Y}. \tag*{(59)} ρ View M , T , Y ( 0 ) = ρ View M , T , Y ( 1 ) . (59)
and hence
1 2 ∥ ρ V i e w M , T , Y ( 0 ) − ρ V i e w M , T , Y ( 1 ) ∥ 1 = 0 ≤ negl ( λ ) . (60) \frac{1}{2}\left\|\rho^{(0)}_{\mathrm{View}_{M,T,Y}}-\rho^{(1)}_{\mathrm{View}_{M,T,Y}}\right\|_1=0\leq\operatorname{negl}(\lambda). \tag*{(60)} 2 1 ρ View M , T , Y ( 0 ) − ρ View M , T , Y ( 1 ) 1 = 0 ≤ negl ( λ ) . (60)
Thus, the MTA-QSS scheme satisfies tracer secrecy.
Proof of Theorem 20
Theorem 20 (Formal). The MTA-QSS scheme is traceable against any QPT adversary. For every QPT adversary A A A , there exists a negligible function negl ( ⋅ ) \operatorname{negl}(\cdot) negl ( ⋅ ) such that, for security parameter λ ∈ N \lambda\in\mathbb{N} λ ∈ N ,
Adv A , M T A - Q S S t r a c e ( λ ) ≤ negl ( λ ) . \operatorname{Adv}^{\mathrm{trace}}_{A,\mathrm{MTA\text{-}QSS}}(\lambda)\leq\operatorname{negl}(\lambda). Adv A , MTA - QSS trace ( λ ) ≤ negl ( λ ) . Proof. Let U i d x U_{\mathrm{idx}} U idx be the index set of honest parties involved in reconstruction, and let U ⊆ T a g s U\subseteq\mathit{Tags} U ⊆ Tags denote the corresponding honest tag set. Let ( U ′ , V ′ ) ← S e c r e t T r a c e ( t k , u k , I ) (U',V')\leftarrow\mathsf{SecretTrace}(tk,uk,I) ( U ′ , V ′ ) ← SecretTrace ( t k , u k , I ) and o k ← S e c r e t V e r i f y ( v k , u k , c k , U ′ , V ′ , I ) ok\leftarrow\mathsf{SecretVerify}(vk,uk,ck,U',V',I) o k ← SecretVerify ( v k , u k , c k , U ′ , V ′ , I ) . By definition, the traceability experiment fails if either o k = 0 ok=0 o k = 0 , or o k = 1 ok=1 o k = 1 but U ′ ≠ U U'\neq U U ′ = U . Accordingly, define
W 1 : = { o k = 0 } , W 2 : = { o k = 1 ∧ U ′ ≠ U } . (61) W_1:=\{ok=0\},\qquad W_2:=\{ok=1\land U'\neq U\}. \tag*{(61)} W 1 := { o k = 0 } , W 2 := { o k = 1 ∧ U ′ = U } . (61) Then
Pr [ E x p T r a c e = 1 ] = Pr [ W 1 ] + Pr [ W 2 ] . (62) \Pr[\mathsf{ExpTrace}=1]=\Pr[W_1]+\Pr[W_2]. \tag*{(62)} Pr [ ExpTrace = 1 ] = Pr [ W 1 ] + Pr [ W 2 ] . (62) For honestly generated auxiliary information, SecretVerify rejects the output of SecretTrace only with negligible probability. Hence
Pr [ W 1 ] ≤ negl ( λ ) . (63) \Pr[W_1]\leq\operatorname{negl}(\lambda). \tag*{(63)} Pr [ W 1 ] ≤ negl ( λ ) . (63) It remains to bound Pr [ W 2 ] \Pr[W_2] Pr [ W 2 ] . Write
W 2 f o r g e : = { o k = 1 ∧ ∃ t a g ∗ ∈ U ′ ∖ T a g s } , (64) W_2^{\mathrm{forge}}:=\{ok=1\land\exists\,tag^*\in U'\setminus\mathit{Tags}\}, \tag*{(64)} W 2 forge := { o k = 1 ∧ ∃ t a g ∗ ∈ U ′ ∖ Tags } , (64) and
W 2 w r o n g : = { o k = 1 ∧ U ′ ⊆ T a g s ∧ U ′ ≠ U } . (65) W_2^{\mathrm{wrong}}:=\{ok=1\land U'\subseteq\mathit{Tags}\land U'\neq U\}. \tag*{(65)} W 2 wrong := { o k = 1 ∧ U ′ ⊆ Tags ∧ U ′ = U } . (65) Then
Pr [ W 2 ] = Pr [ W 2 f o r g e ] + Pr [ W 2 w r o n g ] . (66) \Pr[W_2]=\Pr[W_2^{\mathrm{forge}}]+\Pr[W_2^{\mathrm{wrong}}]. \tag*{(66)} Pr [ W 2 ] = Pr [ W 2 forge ] + Pr [ W 2 wrong ] . (66) If W 2 f o r g e W_2^{\mathrm{forge}} W 2 forge occurs, then there exists t a g ∗ ∈ U ′ ∖ T a g s tag^*\in U'\setminus\mathit{Tags} t a g ∗ ∈ U ′ ∖ Tags that nevertheless passes verification. By the definition of SecretVerify, this implies
H ( t a g ∗ ) ∈ { v k i } i = 0 m − 1 , (67) H(tag^*)\in\{vk_i\}_{i=0}^{m-1}, \tag*{(67)} H ( t a g ∗ ) ∈ { v k i } i = 0 m − 1 , (67) and hence H ( t a g ∗ ) = H ( t a g j ) H(tag^*)=H(tag_j) H ( t a g ∗ ) = H ( t a g j ) for some t a g j ∈ T a g s tag_j\in\mathit{Tags} t a g j ∈ Tags . Since t a g ∗ ≠ t a g j tag^*\neq tag_j t a g ∗ = t a g j , this yields a collision in H H H . By collision resistance,
Pr [ W 2 f o r g e ] ≤ negl ( λ ) . (68) \Pr[W_2^{\mathrm{forge}}]\leq\operatorname{negl}(\lambda). \tag*{(68)} Pr [ W 2 forge ] ≤ negl ( λ ) . (68) Next consider W 2 w r o n g W_2^{\mathrm{wrong}} W 2 wrong . In this case, SecretVerify accepts a subset of honestly generated tags that differs from the true honest tag set U U U . However, for honestly generated reconstruction data, each element of I I I has the form r i ∥ t k i r_i\|tk_i r i ∥ t k i , and SecretTrace recovers the corresponding tag through the successive decryptions
r i ∥ t k i → Dec ( ⋅ , u k ) c t i → Dec ( ⋅ , c k ) t a g i . (69) r_i\mathbin{\|}tk_i\xrightarrow{\operatorname{Dec}(\cdot,uk)}ct_i\xrightarrow{\operatorname{Dec}(\cdot,ck)}tag_i. \tag*{(69)} r i ∥ t k i Dec ( ⋅ , u k ) c t i Dec ( ⋅ , c k ) t a g i . (69) Thus, once u k uk u k and c k ck c k are fixed, the recovered tags are uniquely determined by I I I . Since SecretVerify accepts only if these recovered tags are consistent with the verification keys and the auxiliary data extracted from I I I , the accepted valid-tag set must coincide with U U U , except with negligible probability. Therefore,
Pr [ W 2 w r o n g ] ≤ negl ( λ ) . (70) \Pr[W_2^{\mathrm{wrong}}]\leq\operatorname{negl}(\lambda). \tag*{(70)} Pr [ W 2 wrong ] ≤ negl ( λ ) . (70) Combining the above bounds gives
Pr [ E x p T r a c e = 1 ] ≤ negl ( λ ) , (71) \Pr[\mathsf{ExpTrace}=1]\leq\operatorname{negl}(\lambda), \tag*{(71)} Pr [ ExpTrace = 1 ] ≤ negl ( λ ) , (71) and hence
Adv A , M T A - Q S S t r a c e ( λ ) ≤ negl ( λ ) . (72) \operatorname{Adv}^{\mathrm{trace}}_{A,\mathrm{MTA\text{-}QSS}}(\lambda)\leq\operatorname{negl}(\lambda). \tag*{(72)} Adv A , MTA - QSS trace ( λ ) ≤ negl ( λ ) . (72)
Proof of Theorem 21
Theorem 21 (Formal). The MTA-QSS scheme is non-imputable against any QPT adversary. For every QPT adversary A A A , there exists a negligible function negl ( ⋅ ) \operatorname{negl}(\cdot) negl ( ⋅ ) such that, for security parameter λ ∈ N \lambda\in\mathbb{N} λ ∈ N ,
Adv A , M T A - Q S S n i ( λ ) ≤ negl ( λ ) . \operatorname{Adv}^{\mathrm{ni}}_{A,\mathrm{MTA\text{-}QSS}}(\lambda)\leq\operatorname{negl}(\lambda). Adv A , MTA - QSS ni ( λ ) ≤ negl ( λ ) . Proof. Consider the experiment E x p N I A , M T A - Q S S ( λ ) \mathsf{ExpNI}_{A,\mathrm{MTA\text{-}QSS}}(\lambda) ExpNI A , MTA - QSS ( λ ) . Let i ∗ ∈ [ m ] i^*\in[m] i ∗ ∈ [ m ] be the target honest participant selected by the adversary, and let t a g ∗ : = t a g i ∗ tag^*:=tag_{i^*} t a g ∗ := t a g i ∗ be the corresponding tag. Since participant i ∗ i^* i ∗ remains honest throughout the experiment, t a g ∗ tag^* t a g ∗ is an honestly generated tag and therefore satisfies
H ( t a g ∗ ) ∈ { v k i } i = 0 m − 1 . (73) H(tag^*)\in\{vk_i\}_{i=0}^{m-1}. \tag*{(73)} H ( t a g ∗ ) ∈ { v k i } i = 0 m − 1 . (73) Suppose the adversary outputs a pair ( U ∗ , V ∗ ) (U^*,V^*) ( U ∗ , V ∗ ) . The framing event is defined by
F r a m e : = { t a g ∗ ∈ V ∗ ∧ S e c r e t V e r i f y ( v k , u k , c k , U ∗ , V ∗ , I ) = 1 } . (74) \mathsf{Frame}:=\left\{tag^*\in V^*
\land\mathsf{SecretVerify}(vk,uk,ck,U^*,V^*,I)=1\right\}. \tag*{(74)} Frame := { t a g ∗ ∈ V ∗ ∧ SecretVerify ( v k , u k , c k , U ∗ , V ∗ , I ) = 1 } . (74) However, by the definition of SecretVerify, acceptance requires that
∀ t a g z ∈ V ∗ , H ( t a g z ) ∉ { v k i } i = 0 m − 1 . (75) \forall\,tag_z\in V^*,\qquad H(tag_z)\notin\{vk_i\}_{i=0}^{m-1}. \tag*{(75)} ∀ t a g z ∈ V ∗ , H ( t a g z ) ∈ / { v k i } i = 0 m − 1 . (75) This condition is incompatible with t a g ∗ ∈ V ∗ tag^*\in V^* t a g ∗ ∈ V ∗ , since H ( t a g ∗ ) ∈ { v k i } i = 0 m − 1 H(tag^*)\in\{vk_i\}_{i=0}^{m-1} H ( t a g ∗ ) ∈ { v k i } i = 0 m − 1 . Hence the event Frame cannot occur, and therefore
Pr [ F r a m e ] = 0. (76) \Pr[\mathsf{Frame}]=0. \tag*{(76)} Pr [ Frame ] = 0. (76) By the definition of non-imputability advantage,
Adv A , M T A - Q S S n i ( λ ) = Pr [ F r a m e ] = 0 ≤ negl ( λ ) . (77) \operatorname{Adv}^{\mathrm{ni}}_{A,\mathrm{MTA\text{-}QSS}}(\lambda)=\Pr[\mathsf{Frame}]=0\leq\operatorname{negl}(\lambda). \tag*{(77)} Adv A , MTA - QSS ni ( λ ) = Pr [ Frame ] = 0 ≤ negl ( λ ) . (77) Hence, the MTA-QSS scheme is non-imputable.