Quantum Anonymous Secret Sharing with Permutation Invariant Codes

This paper proposes a quantum anonymous secret sharing protocol that achieves sender-anonymity by combining permutation-invariant quantum error-correcting codes with anonymous transmission algorithms, while also quantifying information leakage in ramp schemes using quantum conditional min-entropy to evaluate the security of intermediate shares.

The Gist

Imagine you have a top-secret recipe for the world's best cookie. You don't want just one person to hold the whole recipe, because if they lose it or get kidnapped, the recipe is gone forever. So, you decide to split the recipe into several pieces (shares) and give them to different friends. This is the basic idea of Secret Sharing: you need a specific number of friends to get back together to reconstruct the full recipe.

However, there's a problem with the old way of doing this: when your friends get together to put the pieces back together, everyone knows who showed up. If a bad guy is watching, they can see that "Alice" and "Bob" were the ones who recovered the secret. Maybe Alice is a whistleblower, or maybe Bob is trying to stay anonymous for a vote. They need a way to share the secret without anyone knowing who contributed the pieces.

This paper proposes a new, high-tech way to do this called Quantum Anonymous Secret Sharing. Here is how it works, broken down into simple concepts:

1. The Magic of "Permutation-Invariant" Codes

Think of the secret recipe not as a list of words, but as a special, tangled knot of string. In this new system, the way the knot is tied has a special property: it doesn't matter which piece of string you pull first.

In technical terms, the authors use "Permutation-Invariant" (PI) codes. Imagine you have a bag of 10 marbles, and the secret is hidden inside the total weight of the marbles, not in any specific marble. If you take out 3 marbles to check, it doesn't matter which 3 you took; as long as you have enough, you can figure out the secret. Because the system doesn't care about the order or identity of the pieces, the person decoding the secret (the "Decoder") can't tell which friends showed up. They just know, "Okay, I have enough pieces to solve the puzzle."

2. The "Ghost Messenger" Protocol

To make sure no one knows who is sending a piece of the secret, the authors use a set of "Ghost Messenger" tricks based on quantum physics (specifically, something called GHZ states, which are like a group of friends holding hands in a circle).

Imagine you are in a room with 10 people. You want to send a message to the person at the front of the room, but you don't want anyone to know it was you.

• The Trick: Everyone in the room performs a synchronized dance move (a quantum operation) at the same time.
• The Result: The message arrives at the front, but because everyone danced together, the "footprints" of the sender are erased. The Decoder receives the message, but it looks like it came from a cloud of possibilities rather than a single person. Even the other friends in the room can't tell who sent it.

3. Measuring the "Leak" with a New Ruler

The authors also wanted to know: "If a bad guy steals some of the pieces, how much of the secret do they actually learn?"

Old ways of measuring this were like taking an average of many different scenarios. But the authors argue that a bad guy only gets one chance to steal the secret. So, they introduced a new measuring stick called Conditional Min-Entropy.

Think of it like this:

• Old Ruler: "On average, if you steal 3 pieces, you learn 20% of the recipe."
• New Ruler (Min-Entropy): "If you are the smartest thief in the world and you steal 3 pieces, what is the best possible percentage of the recipe you can figure out?"

This new ruler is stricter. It tells you the worst-case scenario for security. The authors used this ruler to test different types of "knots" (codes) to see which ones leak the least information to thieves who don't have enough pieces to solve the whole puzzle.

4. The Hybrid Approach (The "Double Lock")

The paper also suggests a "Hybrid" method. Imagine the secret is a quantum cookie recipe, but you also add a classical "lock" (like a password) to it.

• You scramble the quantum recipe using a random password.
• You split the scrambled recipe and the password into shares.
• Even if a thief gets some pieces of the recipe, without the password pieces, the recipe looks like random noise.
• This makes the system even safer, effectively turning the quantum secret into a classical one that is harder to crack.

Summary of What They Achieved

• Anonymity: They created a system where friends can recover a secret without anyone (not even the person decoding it) knowing who participated.
• Robustness: Unlike some previous methods that required everyone to show up, this system works even if some friends are missing, as long as enough pieces are present.
• Better Measurement: They provided a new, strict way to measure exactly how much information leaks out if a thief steals a few pieces.

In short, this paper builds a "ghostly" vault where you can retrieve a secret without anyone knowing who opened the door, and they gave us a better way to measure how secure that vault really is.

Technical Summary

1. Problem Statement

Quantum Secret Sharing (QSS) allows a secret to be distributed among multiple parties such that only authorized subsets can reconstruct it. However, existing QSS schemes have two critical limitations:

• Lack of Sender Anonymity: While the secret is protected from unauthorized parties, the identities of the participants (shareholders) who contribute to the reconstruction are often exposed. In applications like anonymous voting or secure consensus, participants must remain anonymous to prevent coercion or bias.
• Fragility and Rigidity: Many existing Quantum Anonymous Secret Sharing (QASS) schemes rely on specific entangled states (like GHZ or W states) that require all shareholders to participate for reconstruction. They lack robustness against missing participants (erasures) and cannot handle threshold-based access structures where only a subset of shareholders is needed.
• Lack of Quantitative Leakage Metrics: For "ramp" QSS schemes (where intermediate sets of shares leak partial information), there is no standardized, single-shot metric to quantify exactly how much information an adversary gains from holding a specific number of shares.

2. Methodology

The authors propose a novel protocol and a new metric to address these issues.

A. Protocol Design: Anonymous Secret Sharing with PI Codes

The core of the solution involves combining Permutation-Invariant (PI) Quantum Error-Correcting (QEC) codes with anonymous transmission protocols.

1. Permutation-Invariant (PI) Codes:

   • These codes have a codespace invariant under the reordering of physical qubits.
   • Key Advantage: The decoding process depends only on the number of missing shares (erasures), not which specific shares are missing. This allows the decoder to reconstruct the secret without knowing the identities of the participating shareholders.
   • This enables threshold-based recovery (any $k$ out of $n$ shares) rather than requiring full consensus ($n$ out of $n$).

2. Anonymous Transmission Sub-protocols:

   • To hide the identity of the sender during the transmission of shares to the decoder, the authors utilize protocols from Christandl and Wehner [23]:
     • AE (Anonymous Entanglement): Creates an entangled Bell pair between a sender and receiver anonymously using an $n$-qubit GHZ state.
     • ANONQ (Anonymous Quantum Transmission): Uses quantum teleportation over the anonymous Bell pair to send a qubit without revealing the sender's identity.
     • Collision Detection: Ensures only one shareholder transmits at a time to prevent interference.
   • Tracelessness: The protocol ensures that even if an adversary gains access to the randomness used by corrupted players, they cannot determine who sent the shares.

3. Hybrid QASS (HQASS):

   • The authors extend the protocol to a hybrid scheme where a quantum secret is "lifted" to classical security. By applying random Pauli operators ($X$ and $Z$) to the quantum secret and encoding the choice of operators as classical secrets, the scheme ensures that an adversary must first break the classical secret sharing to learn anything about the quantum secret.

B. Metric: Conditional Min-Entropy for Information Leakage

To quantify information leakage in ramp schemes, the authors introduce Quantum Conditional Min-Entropy ($H_{min}$).

• Rationale: Traditional measures like Quantum Mutual Information are "average-case" measures (requiring many copies of a state). In a single-shot scenario (one secret instance), the adversary's best attempt at recovery is better modeled by the Conditional Min-Entropy.
• Connection to Knill-Laflamme: The metric is derived from the second Knill-Laflamme condition. It measures the maximum fidelity between the recovered state and the original reference state after an optimal recovery channel is applied.
• Calculation for Stabilizer Codes: For stabilizer codes, the authors derive a closed-form expression (Theorem III.1) using the Cleaning Lemma:
  $$H_{min}(R|E) = \log |G_{M^c}| - k$$
  Where $|G_{M^c}|$ is the number of logical Pauli operators that can be "cleaned" (trivialized) from the complement of the adversary's share set, and $k$ is the number of logical qubits. This avoids the exponential complexity of solving the general optimization problem.

3. Key Contributions

1. First Sender-Anonymous QSS with Threshold Access: The paper presents the first QSS protocol that achieves sender anonymity while supporting threshold access structures (recovering with $k < n$ shares). Previous works required all shareholders to participate, limiting their utility.
2. Robustness to Erasures: By utilizing PI codes, the scheme tolerates missing shareholders without compromising the anonymity of the remaining participants.
3. New Leakage Metric: The formalization of Conditional Min-Entropy as a valid, single-shot measure for information leakage in ramp QSS schemes, justified by its relationship to error correction conditions.
4. Hybrid Security Construction: A method to combine quantum and classical secret sharing to enhance security, ensuring the quantum secret's security is bounded by the classical secret's security.

4. Results

The authors evaluated several PI codes (4, 7, 9, 11, and 13 qubits) using the proposed $H_{min}$ metric.

• 4-Qubit Codes:

  • Three different 4-qubit PI codes (Aydin et al., Hagiwara & Nakayama, and Leung et al.) were tested.
  • Finding: All three codes exhibited identical $H_{min}$ values.
  • Leakage Behavior:
    • With 1 share: Maximum leakage ($H_{min} = 1$, Fidelity = 0.25).
    • With 2 shares: Half information leaked ($H_{min} = 0$, Fidelity = 0.5).
    • With 3+ shares: Full recovery ($H_{min} = -1$, Fidelity = 1.0).
  • The Hybrid QASS (HQASS) scheme using these codes showed a threshold of $k=3$ with no intermediate leakage, effectively acting as a perfect scheme for the hybrid case.

• Larger Codes (7, 9, 11, 13 qubits):

  • The study compared various PI codes (e.g., shifted GNU codes, codes by Kubischta/Teixeira).
  • Observation: The amount of information gained per share is not constant. Some codes exhibit "plateaus" where adding a share yields no new information, while others show gradual leakage.
  • Variability: Different PI codes with the same distance ($d=3$) exhibit different leakage profiles for intermediate share sets, suggesting that code selection is critical for optimizing security in ramp schemes.

5. Significance and Future Directions

• Practical Application: This work enables secure, anonymous collaboration in scenarios where participants must remain hidden (e.g., anonymous voting, distributed consensus in hostile environments) while allowing for flexible participation (thresholds).
• Theoretical Advancement: It bridges the gap between Quantum Error Correction (QEC) and Cryptography by using QEC properties (permutation invariance) to solve cryptographic anonymity problems.
• Future Work:
  • Replacing the GHZ-state-dependent anonymous protocols with more noise-resilient alternatives (e.g., using W states).
  • Investigating PI codes specifically designed to minimize leakage in intermediate sets (smoother ramping).
  • Formalizing the connection between ramp QSS and approximate QSS.
  • Developing faster algorithms to compute $H_{min}$ for larger codes, as the current semi-definite programming approach scales exponentially.

In summary, the paper provides a robust framework for anonymous quantum secret sharing that is both fault-tolerant (handling missing shares) and quantitatively analyzable (via conditional min-entropy), significantly advancing the state of quantum cryptographic protocols.