Kvant digital signatur

En Quantum Digital Signature (QDS) hänvisar till den kvantmekaniska motsvarigheten till antingen en klassisk digital signatur eller, mer allmänt, en handskriven signatur på ett pappersdokument. Liksom en handskriven signatur används en digital signatur för att skydda ett dokument, till exempel ett digitalt kontrakt, mot förfalskning av en annan part eller av någon av de deltagande parterna.

I takt med att e-handel har blivit viktigare i samhället har behovet av att intyga ursprunget till utbytt information uppstått. Moderna digitala signaturer förbättrar säkerheten baserat på svårigheten att lösa ett matematiskt problem, som att hitta faktorer för stora tal (som används i RSA-algoritmen ). Tyvärr blir uppgiften att lösa dessa problem genomförbar när en kvantdator är tillgänglig (se Shors algoritm ) . För att möta detta nya problem är nya kvantdigitala signatursystem under utveckling för att ge skydd mot manipulering, även från parter som har kvantdatorer och använder kraftfulla kvantfuskstrategier.

Klassisk public-key-metod

Den offentliga nyckelmetoden för kryptografi tillåter en avsändare att signera ett meddelande (ofta endast meddelandets kryptografiska hash ) med en teckennyckel på ett sådant sätt att vilken mottagare som helst kan, med hjälp av motsvarande offentliga nyckel, kontrollera meddelandets äkthet. För att tillåta detta görs den publika nyckeln brett tillgänglig för alla potentiella mottagare. För att säkerställa att endast den juridiska författaren av meddelandet kan signera meddelandet på ett giltigt sätt, skapas den publika nyckeln från en slumpmässig, privat signeringsnyckel, med en enkelriktad funktion . Det här är en funktion som är utformad så att det är mycket enkelt att beräkna resultatet givet ingången, men att beräkna indata givet resultatet är mycket svårt. Ett klassiskt exempel är multiplikation av två mycket stora primtal: Multiplikationen är lätt, men att faktorisera produkten utan att känna till primtal anses normalt vara omöjligt.

$x\mapsto f(x)$ lätt

$f(x)\mapsto x$ mycket svårt

Kvantdigital signatur

Liksom klassiska digitala signaturer använder kvantdigitala signaturer asymmetriska nycklar. Således skapar en person som vill signera ett meddelande ett eller flera par av tecken och motsvarande publika nycklar. I allmänhet kan vi dela upp kvantdigitala signatursystem i två grupper:

1. Ett schema som skapar en publik kvantbitnyckel av en privat klassisk bitsträng: $k\mapsto |f_{k}\rangle$
2. Ett schema som skapar en offentlig kvantbitsnyckel av en privat kvantbitsträng : $|k\rangle \mapsto |f_{k}\rangle$

I båda fallen är f en envägs kvantfunktion som har samma egenskaper som en klassisk envägsfunktion. Det vill säga resultatet är lätt att beräkna, men i motsats till det klassiska schemat är funktionen omöjlig att invertera, även om man använder kraftfulla kvantfuskstrategier.

Det mest kända schemat för den första metoden ovan tillhandahålls av Gottesman och Chuang

Krav på ett bra och användbart signaturschema

De flesta av kraven för ett klassiskt digitalt signatursystem gäller även för det kvantdigitala signatursystemet.

I detalj

1. Systemet måste ge säkerhet mot manipulering
   1. Avsändaren efter att meddelandet signerades (se bit engagemang )
   2. Mottagaren
   3. En tredje part
2. Det måste vara enkelt att skapa ett signerat meddelande
3. Varje mottagare måste få samma svar när meddelandet testas för giltighet (Giltigt, Ej giltigt)

Skillnader mellan klassiska och kvanta envägsfunktioner

Envägsfunktionens karaktär

En klassisk envägsfunktion som nämnts ovan är baserad på en klassisk omöjlig matematisk uppgift, medan en kvantenvägsfunktion utnyttjar osäkerhetsprincipen som gör det omöjligt även för en kvantdator att beräkna inversen. Detta görs genom att tillhandahålla ett kvantutdatatillstånd, med vilket man inte kan lära sig tillräckligt mycket om ingångssträngen för att reproducera den. I fallet med den första gruppen av scheman visas detta av Holevos sats, som säger att man från ett givet n-qubit kvanttillstånd inte kan extrahera mer än n klassiska informationsbitar. En möjlighet att säkerställa att schemat använder mindre qubits för en bitsträng av en viss längd är att använda nästan ortogonala tillstånd

$|\langle f_{k}|f_{k}'\rangle |<\delta \qquad {\text{ för }}k\neq k'\land 0\leq \delta \leq 1$

Det ger oss möjligheten att inducera en grund med mer än två stater. Så för att beskriva en information på $2^{n}$ bitar kan vi använda mindre än n qubits. Ett exempel med 3 qubit-basis

• $|0\rangle$
• $|1\rangle$
• ${\frac {1}{\sqrt {2}}}(|0\rangle +|1\rangle )$

Endast m qubits behövs för att beskriva n klassiska bitar när $3^{m}=2^{n}$ gäller.

På grund av Holevos teorem och det faktum att m kan vara mycket mindre än n, kan vi bara få ut m bitar ur n bitars meddelandet. Mer generellt, om man får T kopior av den publika nyckeln kan han extrahera högst Tm bitar av den privata nyckeln. Om $\delta$ är stor blir $n-Tm$ mycket stor, vilket gör det omöjligt för en oärlig person att gissa teckennyckeln.

Obs: Du kan inte skilja mellan icke-ortogonala tillstånd om du bara har en liten mängd identiska tillstånd. Det är så kvantenvägsfunktionerna fungerar. Ändå $|f_{k}\rangle$ läcker information om den privata nyckeln, i motsats till den klassiska publika nyckeln, som tvingar en att få ingenting eller allt om den privata nyckeln.

Kopierar den publika nyckeln

I det klassiska fallet skapar vi en klassisk publik nyckel av en klassisk teckennyckel, så det är lätt att förse varje potentiell mottagare med en kopia av den publika nyckeln. Den publika nyckeln kan distribueras fritt. Detta blir svårare i kvantfallet, eftersom kopiering av ett kvanttillstånd är förbjudet av no cloning theoremet, så länge tillståndet i sig är okänd. Så offentliga nycklar kan bara skapas och distribueras av en person som känner till det exakta kvanttillstånd han vill skapa, alltså vem som känner till teckennyckeln (Detta kan vara avsändaren eller mer generellt en pålitlig institution). I motsats till den klassiska publika nyckeln finns det dock en övre gräns för antalet publika kvantnycklar T som kan skapas, utan att göra det möjligt för en att gissa teckennyckeln och därmed äventyra schemats säkerhet ( ${\ displaystyle n-Tm}$ måste vara stor)

Public Key bör vara densamma för alla mottagare (Swap Test)

För att säkerställa att alla mottagare får identiska resultat när de testar ett meddelandes äkthet, måste de offentliga nycklar som distribueras vara desamma. Detta är enkelt i det klassiska fallet, eftersom man enkelt kan jämföra två klassiska bitsträngar och se om de matchar. Ändå är det mer komplicerat i kvanttillståndet. För att testa, om två offentliga kvanttillstånd är samma måste man jämföra följande

$|f_{k}'\rangle =|f_{k}\rangle$

Byt test mot qubits

Detta görs med följande kvantkrets som använder en Fredkin gate F , en Hadamard gate H och en ancilla qubit a . Först och främst är ancilla qubit satt till ett symmetriskt tillstånd $|a\rangle ={\frac {1}{\sqrt {2}}}(|0\rangle +|1\rangle )$ .

Direkt efter ancilla qubit används som en kontroll på målen $|f_{k}\rangle \$ och $\ |f_{k}'\rangle$ i en Fredkin Gate.

Dessutom appliceras en Hadamard-grind på ancilla-qubiten och slutligen mäts den första qubiten. Om båda tillstånden är samma, resultatet $|0\rangle$ mäts. Om båda tillstånden är nästan ortogonala kan resultatet bli antingen $|0\rangle \$ eller $\ |1\rangle$ .

Beräkningen av swaptestet mer detaljerat:

Den övergripande staten

$|\psi _{0}\rangle =|a\rangle |f_{k}\rangle |f_{k}'\rangle$

$|\psi _{0}\rangle ={\frac {1}{\sqrt {2}}}{\bigg (}|0\rangle +|1\rangle {\bigg )} |f_{k}\rangle |f_{k}'\rangle$

$|\psi _{0}\rangle ={\frac {1} {\sqrt {2}}}{\bigg (}|0\rangle |f_{k}\rangle |f_{k}'\rangle +|1\rangle |f_{k}\rangle |f_{k}' \rangle {\bigg )}$

Efter att Fredkin- porten appliceras

$\Rightarrow {\frac {1}{\sqrt {2}}}{\ bigg (}|0\rangle |f_{k}\rangle |f_{k}'\rangle +|1\rangle \mathbf {|f_{k}'\rangle |f_{k}\rangle } {\bigg ) }$

Efter att Hadamard- porten appliceras på den första qubiten

$\Rightarrow {\frac {1}{2}}{\bigg [}{\bigg (}|0\rangle +|1\rangle {\bigg )}|f_{k}\rangle |f_{k}'\rangle +{\bigg (}|0\rangle -|1\rangle {\bigg )}|f_{k}'\rangle |f_{k}\rangle {\bigg ]}$

Efter sortering för $|0\rangle {\text{ och }}|1\rangle$

$\Rightarrow |\psi \rangle ={\frac {1}{2}}{\bigg [} |0\rangle {\bigg (}|f_{k}\rangle |f_{k}'\rangle +|f_{k}'\rangle |f_{k}\rangle {\bigg )}+|1\rangle {\bigg (}|f_{k}\rangle |f_{k}'\rangle -|f_{k}'\rangle |f_{k}\rangle {\bigg )}{\bigg ]}$

Nu är det lätt att se, om staterna $|f_{k}\rangle =|f_{k}'\rangle \$ sedan ${\displaystyle \ |\psi \rangle =|0\rangle |f_{k}\rangle |f_{k}\rangle } ,$ vilket ger oss en 0 när den mäts.

Ett exempel på en signeringsvalideringsprocess som använder ett förenklat Gottesman-Chuang-schema

Signeringsprocess

Ett signeringsprocessexempel för en meddelandebit b = 0 med Gottesman-Chuang-schema

Låt person A (Alice) vilja skicka ett meddelande till person B (Bob). Hashalgoritmer kommer inte att övervägas, så Alice måste signera varenda del av sitt meddelande. Message-Bit b $\in \{0,1\}$ .

Alice väljer M par privata nycklar $\{k_{0}^{i},k_{1}^{i}\}\quad 1\leq i \leq M$

• Alla $k_{0}$ -nycklar kommer att användas för att signera meddelandebiten om b = 0.
• Alla $k_{1}$ nycklar kommer att användas för att signera meddelandebiten om b = 1.

Funktionen som mappar $k\mapsto |f_{k}\rangle$ är känd för alla parter. Alice beräknar nu motsvarande publika nycklar ${\displaystyle \{|f_{k_{0}}^{i}\rangle ,|f_{k_{1}}^{i}\rangle \}} och ger dem alla$ till mottagare. Hon kan göra så många kopior hon behöver, men måste passa på att inte äventyra säkerheten $\left(n\gg Tm{\text{ måste hålla }}\ höger)$ .

Hennes säkerhetsnivå begränsar antalet identiska publika nycklar hon kan skapa

Om

• meddelande-bit b = 0 , hon skickar alla sina privata nycklar $k_{0}$ tillsammans med meddelande-biten b till Bob
• meddelande-bit b = 1 , hon skickar alla sina privata nycklar $k_{1}$ tillsammans med meddelande-biten b till Bob

Kom ihåg: I det här exemplet väljer Alice bara en bit b och signerar den. Det måste hon göra för varje bit i sitt meddelande

Valideringsprocess

Ett valideringsexempel med Gottesman-Chuang-schema. Endast en tröskel beaktas

Bob äger nu

• Meddelandebiten b
• Motsvarande privata nycklar $k_{0}{\text{ eller }}k_{1}$
• Alla publika nycklar $\{|f_{k_{0}}\rangle ,|f_{k_{1}}\rangle \}$

Nu räknar Bob $|f_{k_{b}}\rangle$ för alla mottagna privata nycklar (antingen ${\displaystyle k_{0}{\text{ eller }}k_{1}} )$ .

Efter att han har gjort det använder han swaptestet för att jämföra de beräknade tillstånden med de mottagna publika nycklarna. Eftersom swaptestet har en viss sannolikhet att ge fel svar måste han göra det för alla M- nycklar och räknar hur många felaktiga nycklar han får r . Det är uppenbart att M är någon slags säkerhetsparameter. Det är mer osannolikt att validera lite fel för större M .

• Om han bara får några felaktiga nycklar, så är biten med största sannolikhet giltig, eftersom hans beräknade nycklar och de publika nycklarna verkar vara desamma.
• Om han får många felaktiga nycklar, så fejkade någon meddelandet med stor sannolikhet.

Undvik att ett meddelande ska valideras annorlunda

Ett problem som uppstår speciellt för litet M är att antalet felaktiga nycklar som olika mottagare mäter varierar med sannolikhet. Så att definiera endast en tröskel är inte tillräckligt, eftersom det skulle göra att ett meddelande valideras annorlunda, när antalet felaktiga nycklar r är mycket nära den definierade tröskeln.

Detta kan förhindras genom att definiera mer än en tröskel. Eftersom antalet fel ökar proportionellt med M, definieras tröskelvärdena som

Acceptans $T_{a}=c_{1}M$

Avslag $T_{r}=c_{2}M$

• Om antalet felaktiga nycklar r är under $T_{a}$ är biten giltig med hög sannolikhet
• Om antalet felaktiga nycklar r är över $T_{r}$ så är biten falsk med hög sannolikhet
• Om antalet felaktiga nycklar r ligger mellan båda tröskelvärdena kan mottagaren inte vara säker på om en annan mottagare får samma utfall när biten valideras. Dessutom kan han inte ens vara säker på om han validerade meddelandet rätt.

Om vi ​​antar perfekta kanaler utan brus, så att biten inte kan ändras på grund av överföringen, kan tröskelvärdet $T_{a}$ ställas in på noll, eftersom växlingstestet alltid godkänns, när det stater är desamma

Meddelandeautentisering

Meddelandeautentiseringskoder (MAC) syftar huvudsakligen till dataursprungsautentisering, men de kan också ge icke-avvisning i vissa realistiska scenarier när en betrodd tredje part är inblandad. I princip kan samma idé utnyttjas inom ramen för kvant-MAC. En bred klass av kvant-MAC verkar dock inte erbjuda några fördelar jämfört med sina klassiska motsvarigheter.

Se även

• Lamport-signatur - En praktisk digital signaturmetod som uppfanns på 1970-talet och ansågs vara säker även mot kvantdatorattacker.
• Kvantkryptografi
• Kvantfingeravtryck