Malleability of transformations on the ciphertext in noisy Quantum public key encryption

Technical Summary: Malleability of Transformations on the Ciphertext in Noisy Quantum Public Key Encryption

Problem Statement
This paper addresses the challenge of rigorously formulating "everlasting security" for Quantum Public Key Encryption (QPKE) and Quantum Key Distribution (QKD) in the presence of noise. While previous work by Malavolta and Walter [3] established a framework for everlasting security in a noiseless setting—demonstrating that security can be achieved after only two rounds of interaction between Alice and Bob—this work investigates how the introduction of noise affects the protocol's security thresholds. Specifically, the paper explores the relationship between the malleability of ciphertext transformations and the security of the protocol when noise is injected into the cryptographic operations. The core problem is to generalize the negligibility function (which quantifies the adversary's advantage) from the ideal noiseless case to a noisy setting, utilizing assumptions regarding the malleability of plaintext and ciphertext transformations.

Methodology
The authors employ a combination of Quantum Information Theory and Abstract Cryptography to analyze the noisy QPKE-QKD protocol. The methodology is structured around the following key components:

1. Noise Injection via Malleability: The paper adapts the concept of malleability, originally introduced by Maurer and Tackmann [9] for comparing "authenticate then encrypt" and "encrypt then authenticate" protocols. The authors define noisy transformations on the plaintext space characterized by three error probabilities: forwarding error, deleting error, and reconstruction error. These errors are used to model the impact of noise on the ciphertext.
2. Trace Distance and Gentle Measurement Lemma (GML): A central technical tool is the adaptation of the Gentle Measurement Lemma from Quantum Information Theory [18]. The authors use this lemma to establish an upper bound on the trace distance between two quantum states (representing the real and ideal experiments) based on a lower bound of the trace of a specific operator. This allows for the generalization of the negligibility function in the presence of noise.
3. Noisy Quantum Polynomial-Time (NQPT) Machines: The paper formalizes the noisy setting by defining Noisy Quantum Polynomial-Time (NQPT) machines and Noisy Completely Positive Trace Preserving (CPTP) maps. These objects replace their noiseless counterparts to model the behavior of Alice, Bob, and the adversary (Eve) under noisy conditions.
4. Projection Operators and State Decomposition: The analysis involves constructing noisy projection operators ($\tilde{\Pi}$) that incorporate noise terms (e.g., $|\sigma + \text{noise}\rangle$) into the standard projection operator $\Pi$ used in the noiseless QPKE-QKD protocol. The authors derive upper bounds on the trace distance by comparing the ratios of noiseless and noisy projection operators, trace operations, and ket/bra states.
5. Resource-Theoretic Approach: The paper utilizes the resource-theoretic framework from [9], defining security and availability in terms of the indistinguishability of resources constructed by protocols. This includes analyzing the composition of protocols and the indistinguishability of hybrid experiments.

Key Contributions

• Formalization of Noisy Everlasting Security: The paper defines "everlasting security" for a noisy QPKE protocol (Definition 37), establishing that the trace distance between noisy hybrid experiments is bounded by a negligibility function dependent on the noisy security parameter $\lambda'$.
• Generalization of the Negligibility Function: The authors derive a relationship between the trace distance in the noisy setting and the negligibility function $NEGL(\lambda')$. They demonstrate that under specific assumptions on the noise, the negligibility function in the noisy setting relates to a higher security threshold compared to the noiseless case.
• Trace Distance Bounds via GML: A primary technical contribution is the derivation of an upper bound on the trace distance using the Gentle Measurement Lemma. The authors show that:
  $$Td(\tilde{Exp}, Exp) \lesssim \sqrt{NEGL(\lambda' - \lambda)}$$
  This is achieved by proving a lower bound on the trace of a specific operator involving the difference between noisy and noiseless states ($\tilde{\rho} - \tau$).
• Malleability Assumptions: The work explicitly links the security of the protocol to the malleability of ciphertext transformations. It quantifies how the forwarding, deleting, and reconstruction error probabilities of noisy transformations relate to the security threshold gap between the noiseless ($\lambda$) and noisy ($\lambda'$) protocols.
• Computational Runtime Trade-offs: The paper analyzes the trade-offs between the computational runtime of noisy versus noiseless protocols (encoding, decoding, and key generation). It suggests that if the runtime of the noisy protocol is significantly larger, the security threshold gap $\lambda' - \lambda$ scales in a specific manner, potentially related to exponential or polynomial functions of the runtime difference.

Results

• Main Theorem: The paper proves that for a noisy QPKE-QKD protocol satisfying correctness conditions, the trace distance between the noisy hybrid experiments (initialized with bits 0 and 1) is bounded by the negligibility function of the noisy security parameter:
  $$Td(\tilde{Exp}_{A_{\lambda'}}(1^{\lambda'}, 1), \tilde{Exp}_{A_{\lambda'}}(1^{\lambda'}, 0)) \lesssim NEGL(\lambda')$$
• Corollary on Advantage Functions: The authors show that the noisy advantage functions for different hybrid experiments ($\tilde{Adv}(0), \tilde{Adv}(1), \tilde{Adv}(2)$) are all bounded by the same negligibility function $NEGL(\lambda')$, confirming the consistency of the security definition across different experimental setups.
• Lower Bound on Trace: The paper provides a detailed derivation showing that the trace of a specific operator involving the difference of noisy and noiseless states is bounded from below by a constant times the inverse of the negligibility function, which is a prerequisite for applying the Gentle Measurement Lemma.

Significance and Claims
The paper claims to provide a rigorous mathematical framework for extending the notion of everlasting security to noisy Quantum Public Key Encryption. By adapting the Gentle Measurement Lemma, the authors demonstrate that the security guarantees of the noiseless protocol can be generalized to the noisy setting, provided that the noise is characterized through malleability assumptions on ciphertext transformations.

The authors emphasize that while the introduction of noise generally leads to a higher security threshold (implying a potentially weaker security guarantee in terms of the parameter $\lambda'$), the derived bounds allow for a quantitative comparison between noisy and noiseless protocols. The work is presented as a theoretical stepping stone, noting that while the requirements for unconditional and everlasting security are difficult to realize experimentally, the proposed framework offers a valuable starting point for analyzing the limitations of noisy quantum computation in cryptographic contexts. The paper concludes by suggesting that the derived computations for bounding trace distance could be further examined in settings centered on game-theoretic approaches, though it does not propose specific experimental implementations or immediate applications beyond the theoretical analysis.