Evaluating Post-Quantum Group Key Exchange

Abstract

Offentlig nøkkelkryptografi er grunnlaget som sikkerheten til mange populære tjenester er bygget på. Nyere innovasjoner innen kvantedatamaskiner kan utgjøre en risiko for dette nåværende paradigmet. Kvantesikker kryptografi er løsningen på denne trusselen, men medfører en mengde utfordringer hva gjelder effektivitet, brukbarhet og kompleksitet.

I denne oppgaven utforsker vi protokoller for kvantesikker gruppenøkkelutveksling basert på et matematisk problem som antas å være vanskelig å løse effektivt, selv ved bruk av kvantedatamaskiner: Ringlæring med feil (RLWE). Spesifikt instansierer vi to protokoller med anslagsvis 105 biters sikkerhet, og gir effektive implementasjoner ved bruk av den tall-teoretiske transformasjonen (NTT) og Barrett-reduksjon for gruppenøkkelutvekslingsprotokollene samt autentiserte versjoner. Til slutt gir vi en prototype for en virkelighetsnær applikasjon: en interaktiv tekst-basert gruppesamtaleapplikasjon.

Informasjon samlet i prosessen indikerer at spesifikke kvantesikre gruppenøkkelutvekslingsprotokoller fungerer i visse situasjoner, for eksempel på stasjonære datamaskiner og servere. Vi oppnår en ytelse som kan sammenlignes med flere kvantesikre nøkkelutvekslingsprotokoller mellom to parter. Til slutt bemerker vi at det kreves ytterligere arbeid på et protokollnivå for å oppnå ikke-interaktive protokoller med tilleggsegenskaper, slik som fornektbarhet.

Public key cryptography is the foundation on which the security of many popular services are built. Recent innovations in the field of quantum computing could pose a risk to this current paradigm. Post-quantum cryptography is the solution to this threat, but with it comes a set of challenges in terms of efficiency, usability, and complexity.

In this thesis, we explore protocols for post-quantum group key exchange based on a mathematical problem that is believed to be hard to solve efficiently, even using quantum computers: Ring-learning with errors (RLWE). Specifically, we instantiate two protocols with an estimated 105 bits of security, and provide efficient implementations using the number-theoretic transform (NTT) and Barrett reduction for the group key exchange protocols and authenticated versions. Finally, we provide a prototype for a real-world application: interactive group messaging.

Information gathered in the process indicates that specific post-quantum group key exchange protocols are feasible in certain situations, such as on desktop and server computers. We achieve a performance comparable to several post-quantum two-party key exchange protocols. Finally, we note that further work on a protocol level is required to attain non-interactive protocols with auxiliary properties such as deniability.