Technical Summary: Towards Unconditional Uncloneable Encryption

1. Problem Statement

Uncloneable encryption is a cryptographic primitive designed to encrypt classical messages into quantum ciphertexts such that two quantum adversaries, given the decryption key and quantum side-information derived from the ciphertext, cannot simultaneously decrypt the message. While schemes achieving this property have been proposed in the Quantum Random Oracle Model (QROM) and under specific computational assumptions (e.g., obfuscation), the existence of an unconditionally secure uncloneable encryption scheme in the plain model remains an open problem.

The core of this challenge is the "uncloneable bit" problem: the simplest case where a single classical bit ($m \in \{0, 1\}$) is encrypted. Despite its simplicity, no scheme has been proven to satisfy uncloneable-indistinguishability security without computational assumptions. The security of such a scheme is defined by a "no-cloning game" where a pirate (P) attempts to split a quantum ciphertext into two registers for Bob (B) and Charlie (C). B and C, each holding the secret key, must independently guess the original bit. The scheme is secure if the probability that both B and C guess correctly is bounded by $1/2 + \text{negl}(\lambda)$ (strong security) or $1/2 + f(\lambda)$ where $f(\lambda) \to 0$ (weak security).

2. Methodology

The authors propose a candidate scheme for the uncloneable bit based on the structure of Clifford algebras and pairwise anti-commuting Pauli strings.

The Candidate Scheme

• Key Generation: A key $k$ is sampled uniformly from a set of size $K = 2^\lambda$ (for even $\lambda$) or $K = 2^\lambda + 1$ (for odd $\lambda$).
• Encryption: The message $m \in \{0, 1\}$ is encoded into a quantum state $\rho_{m,k}$, which is the normalized projector onto the eigenvalue $(-1)^m$ of a specific Hermitian unitary $\Gamma_k$. The set $\{\Gamma_1, \dots, \Gamma_K\}$ consists of pairwise anti-commuting operators (e.g., specific Pauli strings) acting on a Hilbert space of dimension $d = 2^\lambda$.
  $$\rho_{m,k} = \frac{I + (-1)^m \Gamma_k}{2}$$
• Decryption: The receiver measures the state in the eigenbasis of $\Gamma_k$ corresponding to the key $k$.

Analytical Framework

The security analysis reduces the no-cloning game to an optimization problem over the operator norm of a specific operator $W_K$. The winning probability is upper-bounded by:
$$\Pr[\text{win}] \leq \frac{1}{2} + \frac{1}{2K} \sup_{\{U_k\}} \left\| \sum_{k=1}^K \left( \Gamma_k \otimes (U_k \otimes I + I \otimes U_k) + I \otimes U_k \otimes U_k \right) \right\|_{\text{op}}$$
where $U_k$ are Hermitian unitaries representing the adversaries' measurement strategies.

The authors formulate Conjecture 1, positing that for any set of pairwise anti-commuting Hermitian unitaries $\Gamma_k$ and any Hermitian unitaries $U_k$:
$$\left\| \sum_{k=1}^K \left( \Gamma_k \otimes (U_k \otimes I + I \otimes U_k) + I \otimes U_k \otimes U_k \right) \right\|_{\text{op}} \leq K + 2\sqrt{K}$$
If true, this implies a winning probability upper bound of $1/2 + \frac{1}{2\sqrt{K}}$, demonstrating weak security.

To verify this conjecture, the authors employ:

1. Sum-of-Squares (SoS) Decompositions: Constructing explicit polynomial certificates to prove the non-negativity of the operator $P_K = (K + 2\sqrt{K})I - W_K$.
2. NPA Hierarchy (Navascués-Pironio-Acín): Utilizing the first and second levels of this hierarchy (dual to SoS) to formulate Semidefinite Programs (SDPs) that provide upper bounds on the operator norm.
3. Seesaw (Alternating Optimization): A heuristic numerical algorithm to find lower bounds on the maximum eigenvalue of $W_K$ by iteratively optimizing over the state vector and measurement operators.

3. Key Contributions and Results

Analytical Proofs

• Small $K$ Verification: The authors provide explicit SoS decompositions and analytical proofs confirming Conjecture 1 for $K \leq 7$.
• Asymptotic Bound: Using the analytical solution of the first level of the NPA hierarchy, they derive an asymptotic upper bound for the winning probability. For $K > 7$, the bound is $5/8 + \frac{1}{2(K-2)} - \frac{1}{4K}$, which converges to $5/8$ as $K \to \infty$. This is a significant improvement over the trivial bound of 1.

Numerical Evidence

• NPA Level 2: The authors extend the analysis to the second level of the NPA hierarchy, solving the resulting SDPs numerically. They confirm the conjecture holds for $K \leq 17$.
• Best Known Bound: For $K=35$, the NPA level 2 optimization yields a numerical upper bound of approximately 0.5980. The authors state this is, to their knowledge, the best-known unconditional upper bound for uncloneable encryption security.
• Seesaw Method: For $K=18$, the alternating optimization algorithm found no instances violating the conjecture, providing heuristic evidence that the bound holds even for larger $K$.

Indistinguishability

The paper proves that the candidate scheme satisfies a relaxed form of indistinguishability security. Specifically, the probability of an adversary distinguishing between the encryption of a random bit and a fixed bit converges to $1/2$ at a rate of $O(1/\sqrt{K})$.

4. Significance and Claims

The paper presents a candidate scheme for unconditional uncloneable encryption, addressing a fundamental open problem in quantum cryptography. While the authors do not claim to have proven the security for all $K$, they provide:

1. Strong Evidence: A combination of rigorous analytical proofs for small parameters and extensive numerical verification up to $K=17$ (and heuristic checks for $K=18$).
2. Improved Bounds: The derivation of an asymptotic upper bound of $5/8$ and a numerical bound of $\sim 0.5980$, which are the tightest known unconditional bounds for this primitive.
3. Foundation for Future Work: The work establishes a concrete framework (based on Clifford algebras and operator norm optimization) for investigating unconditional uncloneability, moving beyond the limitations of the QROM or computational assumptions.

The authors explicitly note that proving the conjecture for arbitrarily large $K$ remains an open challenge, which would constitute the first unconditional proof of uncloneable encryption in the plain model. They also acknowledge that their scheme achieves "weak" security (quadratic convergence) rather than the "strong" security (exponential decay) defined in earlier works, leaving the construction of a strongly secure scheme as a future objective.