Kvantkryptografi, en överblick
I denna bloggpost kommer jag berätta övergripande om kvantdator och de utmaningar som förväntas komma med deras intåg för hur vi håller vår data och informationsflöde säkert.
Vad är en kvantdator?
Kvantdatorer är en form av datorer där man utnyttjar kvantmekaniska fenomen för att för utföra beräkningar. Den mest grundläggande egenskapen hos en kvantdator är att data representeras av “qubits” istället för de vanliga “bits” som vi är vana vid. Qubits har egenskapen att de kan vara i två tillstånden samtidigt, DVS en qubit kan vara både ‘0’ och ‘1’, samtidigt. Detta är typiskt kodat i kvanttillstånd hos enskilda partiklar, såsom en fotons polarisation. Detta kvantmekaniska beteende kommer från en grundläggande egenskap inom kvantmekaniken; superposition, vilken innebär att partiklar kan befinna sig i flera tillstånd samtidigt. När värdet på en qubits mäts kollapsar denna superposition och man får då antingen ett värde på 0 eller 1, med viss sannolikhetsfördelning för vilket svar som ges.
Denna egenskap hos qubits är grunden för varför kvantdatorer har potential till väldigt kraftfull beräkningsförmåga. Genom att qubits kan representera flera värden kan parallella beräkningar utföras; samtidigt på samma qubits. Detta gör kvantdatorer väldigt kraftfulla för en vissa typer av beräkningar, som till exempel genomsökning av databaser, simulering av fysiska system som molekylstrukturer, eller dekryptering. Men svårigheter med att konstruera algoritmer som faktiskt ger de svar man är ute efter (istället för viss sannolikhet att det var svaret man var ute efter) gör det svårt att föreställa sig att kvantdatorer kommer ersätta dagens klassiska datorer inom en överskådlig framtid.
Kvantdatorer lider även av problem relaterat till vår brusiga omgivning. Superposition av qubits är ett väldigt skört tillstånd och små störningar kan förstöra superpositionen. Trots dessa svårigheter läggs mycket energi och pengar på utveckling av kvantdatorer, både inom den privata och offentliga sektorn.
Kodbrytning med kvantdatorer
Som nämnts ovan kan kvantdatorer ge stora förbättringar för beräkningstid för vissa typer av problem som klassiska datorer har svårt för. Ett av dessa är relaterad till hur vi idag gör nyckelutbyten för att kunna kryptera och signera digitala meddelanden. De algoritmer vi använder idag för detta (RSA, ECDH osv) bygger på att en publik nyckel delas öppet med partner, och att denna är kopplad till en privat nyckel som hemlighålls. Denna privata nyckel går i teorin att beräkna från den publika, men det är extremt långsamt process med klassiska datorer då det inte finns några genvägar. Man behöver testa alla möjliga alternativ tills man hittar rätt lösning. Med tillräckligt stor mängd potentiella lösningar som måste testas kan man enkelt göra det praktiskt omöjligt att beräkna den privata nyckeln.
Kodbrytning med kvantdatorer
Med kvantdatorer kan man till stor del komma runt detta. Det existerar redan idag i algoritmer som i teorin gör det möjligt för kvantdatorer att beräkna en privat nyckel från en publik nyckel i en bråkdel av den tid som en det skulle ta för en klassisk dator. Shors algoritm, namngiven efter sin skapare Peter Shor, är den mest välkända, och i ett framtida blogginlägg ska jag gå igenom denna algoritm, men för diskussionen idag räcker det med att veta att kvantdatorer av tillräcklig storlek (mycket större än vad som existerar idag) enkelt kan bryta de krypteringsalgoritmer vi använder till all vår kommunikation över internet, som till exempel banktransaktioner, webbtrafik, fjärranslutningar, epost, osv.
Det pågår för närvarande aktiv forskning på alternativa metoder för nyckelutbyten som är säkra även efter kvantdatorernas infart.
Nyckelar kodade i kvanttillstånd
Lösningar på problemet med dagens algoritmer med nyckelutbyte kan delas upp i två typer metoder. Den första är metoder där kvantmekaniska fenomen används för att dela nycklar. Ett exempel är BB84 protokollet. En detaljerad beskrivning av detta är för en framtida blogg, men enkelt kan man säga att nyckeln kodas i kvanttillstånd hos fotoner (ljuspartiklar) som skickas genom optiska fiber. Det faktum att det inom kvantmekanik är omöjligt att observera något utan att påverka det används för att detektera om någon avlyssnar.
I teorin är denna metod oerhört säker då den använder fysikens lagar för att säkra informationen istället för som dagens algoritmer; begränsningar i beräkningskraft hos våra datorer. Den kommer dock med en stor nackdel i form av krav på tekniska framsteg och ekonomisk investering i både hårdvara och infrastruktur. Det behövs dedikerad fiberoptik för att skicka signalerna, samt hårdvara som kan mäta och producera signalerna. Det pågår forskning för att undersöka möjligheterna att använda laser och satelliter för att skicka detta genom luften och över långa avstånd. Gitterbaserad kryptografi kan vara lösningen på post-kvantdator kryptografi, så kallad kvantsäker kryptografi.
Kvantsäkra kryptografiska algoritmer
Ett annat, kanske mer realistiskt, tillvägagångssätt för att motverka att kvantdatorer kan knäcka all vår kommunikation är så kallad kvantsäker kryptografi. Detta bygger på mer klassiska krypteringsalgoritmer för nyckelutbyte, men där de matematiska problemen som används inte är enklare att tackla med kvantdatorer än för klassiska datorer. Det finns en rad alternativ för kvantsäkra algoritmer som studeras, såsom gitter-, hash-, eller flervariabel-baserad kryptografi. Man kan visa att dessa är motståndskraftiga mot attacker med Shors algoritm, men det är svårt att visa att det inte går att konstruera andra algoritmer för kvantdatorer som kan knäcka dem.
Den största fördelen med kvantsäkra algoritmer är att implementeringen av dessa skulle kunna göras väldigt enkelt utan krav på ny hårdvara eller infrastruktur. Det skulle i princip kunna vara så enkelt som att utveckla uppdateringar för nuvarande protokoll såsom Transport Layer Security (TLS). på grund av detta anser de flesta att detta är den mest troliga vägen framåt för att säkra vår kommunikation i framtiden.