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

Technische Samenvatting: Malleability van Transformaties op het Ciphertekst in Noisy Quantum Public Key Encryption

Probleemstelling
Dit artikel behandelt de uitdaging om een rigoureuze formulering van "everlasting security" (eeuwige veiligheid) te ontwikkelen voor Quantum Public Key Encryption (QPKE) en Quantum Key Distribution (QKD) in aanwezigheid van ruis. Terwijl eerder werk door Malavolta en Walter [3] een raamwerk voor everlasting security in een ruisloze setting vestigde—waarbij werd aangetoond dat veiligheid kan worden bereikt na slechts twee rondes van interactie tussen Alice en Bob—onderzoekt dit werk hoe de introductie van ruis de beveiligingsdrempels van het protocol beïnvloedt. Specifiek onderzoekt het artikel de relatie tussen de malleability (vervormbaarheid) van ciphertekst-transformaties en de veiligheid van het protocol wanneer ruis wordt geïnjecteerd in de cryptografische operaties. De kern van het probleem is het generaliseren van de negligibility-functie (die het voordeel van de tegenstander kwantificeert) van de ideale ruisloze casus naar een ruisende setting, gebruikmakend van aannames over de malleability van plaintext- en ciphertekst-transformaties.

Methodologie
De auteurs maken gebruik van een combinatie van Quantum Informatietheorie en Abstracte Cryptografie om het noisy QPKE-QKD protocol te analyseren. De methodologie is gestructureerd rond de volgende sleutelcomponenten:

1. Ruisinjectie via Malleability: Het artikel past het concept van malleability aan, oorspronkelijk geïntroduceerd door Maurer en Tackmann [9] voor het vergelijken van "authenticate then encrypt" en "encrypt then authenticate" protocollen. De auteurs definiëren noisy transformaties op de plaintext-ruimte, gekenmerkt door drie foutkansen: forwarding error, deleting error en reconstruction error. Deze fouten worden gebruikt om de impact van ruis op de ciphertekst te modelleren.
2. Trace Distance en Gentle Measurement Lemma (GML): Een centraal technisch instrument is de adaptatie van de Gentle Measurement Lemma uit de Quantum Informatietheorie [18]. De auteurs gebruiken deze lemma om een bovengrens vast te stellen op de trace distance tussen twee kwantumtoestanden (die de reële en ideale experimenten vertegenwoordigen) op basis van een ondergrens van de trace van een specifieke operator. Dit maakt de generalisatie van de negligibility-functie in aanwezigheid van ruis mogelijk.
3. Noisy Quantum Polynomial-Time (NQPT) Machines: Het artikel formaliseert de noisy setting door Noisy Quantum Polynomial-Time (NQPT) machines en Noisy Completely Positive Trace Preserving (CPTP) maps te definiëren. Deze objecten vervangen hun ruisloze tegenhangers om het gedrag van Alice, Bob en de tegenstander (Eve) onder ruisige omstandigheden te modelleren.
4. Projectie-operatoren en State Decompositie: De analyse omvat het construeren van noisy projectie-operatoren ($\tilde{\Pi}$) die ruistermen (bijv. $|\sigma + \text{noise}\rangle$) integreren in de standaard projectie-operator $\Pi$ die wordt gebruikt in het ruisloze QPKE-QKD protocol. De auteurs leiden bovengrenzen af voor de trace distance door de ratio's van ruisloze en noisy projectie-operatoren, trace-operaties, en ket/bra-toestanden te vergelijken.
5. Resource-Theoretische Benadering: Het artikel maakt gebruik van het resource-theoretische raamwerk uit [9], waarbij veiligheid en beschikbaarheid worden gedefinieerd in termen van de ononderscheidbaarheid van resources geconstrueerd door protocollen. Dit omvat de analyse van de compositie van protocollen en de ononderscheidbaarheid van hybride experimenten.

Belangrijkste Bijdragen

• Formalisering van Noisy Everlasting Security: Het artikel definieert "everlasting security" voor een noisy QPKE-protocol (Definitie 37), waarbij wordt vastgesteld dat de trace distance tussen noisy hybride experimenten begrensd wordt door een negligibility-functie afhankelijk van de noisy security parameter $\lambda'$.
• Generalisatie van de Negligibility-functie: De auteurs leiden een relatie af tussen de trace distance in de noisy setting en de negligibility-functie $NEGL(\lambda')$. Ze demonstreren dat onder specifieke aannames over de ruis, de negligibility-functie in de noisy setting gerelateerd is aan een hogere veiligheidsdrempel vergeleken met het ruisloze geval.
• Trace Distance Bounds via GML: Een primaire technische bijdrage is de afleiding van een bovengrens op de trace distance met behulp van de Gentle Measurement Lemma. De auteurs tonen aan dat:
  $$Td(\tilde{Exp}, Exp) \lesssim \sqrt{NEGL(\lambda' - \lambda)}$$
  Dit wordt bereikt door een ondergrens te bewijzen voor de trace van een specifieke operator die de verschil tussen noisy en ruisloze toestanden ($\tilde{\rho} - \tau$) betreft.
• Malleability Aannames: Het werk koppelt de veiligheid van het protocol expliciet aan de malleability van ciphertekst-transformaties. Het kwantificeert hoe de forwarding, deleting en reconstruction error-kansen van noisy transformaties zich verhouden tot de veiligheidsdrempel-gap tussen de ruisloze ($\lambda$) en noisy ($\lambda'$) protocollen.
• Computationele Runtime Trade-offs: Het artikel analyseert de trade-offs tussen de computationele runtime van noisy versus ruisloze protocollen (encoding, decoding en key generation). Het suggereert dat als de runtime van het noisy protocol significant groter is, de veiligheidsdrempel-gap $\lambda' - \lambda$ op een specifieke wijze schaalt, potentieel gerelateerd aan exponentiële of polynomiale functies van het runtime-verschil.

Resultaten

• Hoofdtheorema: Het artikel bewijst dat voor een noisy QPKE-QKD protocol dat voldoet aan correctheidvoorwaarden, de trace distance tussen de noisy hybride experimenten (geïnitialiseerd met bits 0 en 1) begrensd wordt door de negligibility-functie van de noisy security parameter:
  $$Td(\tilde{Exp}_{A_{\lambda'}}(1^{\lambda'}, 1), \tilde{Exp}_{A_{\lambda'}}(1^{\lambda'}, 0)) \lesssim NEGL(\lambda')$$
• Corollary over Advantage Functions: De auteurs tonen aan dat de noisy advantage functies voor verschillende hybride experimenten ($\tilde{Adv}(0), \tilde{Adv}(1), \tilde{Adv}(2)$) allemaal begrensd worden door dezelfde negligibility-functie $NEGL(\lambda')$, wat de consistentie van de veiligheidsdefinitie over verschillende experimentele opstellingen bevestigt.
• Ondergrens op de Trace: Het artikel biedt een gedetailleerde afleiding die aantoont dat de trace van een specifieke operator die het verschil tussen noisy en ruisloze toestanden betreft, begrensd wordt van onderaf door een constante maal de inverse van de negligibility-functie, wat een vereiste is voor het toepassen van de Gentle Measurement Lemma.

Betekenis en Claims
Het artikel claimt een rigoureus wiskundig raamwerk te bieden voor het uitbreiden van het concept van everlasting security naar noisy Quantum Public Key Encryption. Door de Gentle Measurement Lemma aan te passen, demonstreren de auteurs dat de veiligheidsgaranties van het ruisloze protocol kunnen worden gegeneraliseerd naar de noisy setting, mits de ruis wordt gekarakteriseerd via malleability-aannames op de ciphertekst-transformaties.

De auteurs benadrukken dat hoewel de introductie van ruis over het algemeen leidt tot een hogere veiligheidsdrempel (wat een potentieel zwakkere veiligheidsgarantie impliceert in termen van de parameter $\lambda'$), de afgeleide grenzen een kwantitatieve vergelijking tussen noisy en ruisloze protocollen mogelijk maken. Het werk wordt gepresenteerd als een theoretische tussenstap, waarbij wordt opgemerkt dat hoewel de vereisten voor onvoorwaardelijke en everlasting security moeilijk experimenteel te realiseren zijn, het voorgestelde raamwerk een waardevolle start biedt voor het analyseren van de beperkingen van noisy quantum computation in cryptografische contexten. Het artikel concludeert door te suggereren dat de afgeleide berekeningen voor het begrenzen van de trace distance verder onderzocht kunnen worden in settings die gecentreerd zijn rond game-theoretic benaderingen, hoewel het geen specifieke experimentele implementaties of directe toepassingen voorbij de theoretische analyse voorstelt.