Code-based Cryptography

Abstract

Large enough quantum computers could run Shor’s algorithm to solve problems such as the integer factorization problem or the discrete logarithm problem in time frames unattainable by conventional computers. Popular implementations of public-key cryptography rely on brute force computations for such problems being inefficient.This threat has motivated the research of post-quantum cryptography, in which code-based cryptography, making use of error-correcting codes, is one promising research direction. The underlying hard problem in code-based cryptography is the syndrome decoding problem, which is known to be NP-complete and believed to resist brute force attack from quantum computers. The original code-based cryptosystem was suggested in 1978 by Robert McEliece and since then extensive analysis on it and later variants has been covered in the literature. Many of the proposed variants have been shown to be insecure due to lack of sufficient concealment of the code structure, which enables attackers to bypass the hard problem and exploit structural vulnerabilities instead. Twisted codes are a relatively new family of codes, with certain explicit constructions potentially being viable for implementation to code-based cryptography, since previously deployed attack are not directly applicable to them. This thesis surveys the literature on linear codes to present concepts necessary to describe twisted codes in their cryptographic environment. The feasibility of twisted codes in code-based cryptography is then discussed through experimental simulation results.

Riittävän suurella kvanttitietokoneella on teoriassa kyky hyödyntää Shorin algoritmia ja laskea nopeasti tiettyjä vaikeita ongelmia, kuten kokonaislukujen tekijöihinjako ja diskreetti logaritmi. Suositut julkisen avaimen salausmenetelmät nojaavat näiden ongelmien vaikeuteen ja ovat siksi alttiita kvanttilaskennalle. Tästä lähtökohdasta on tutkittu useita vaihtoehtoisia kvanttilaskennan kestäviä salausmenetelmiä. Yksi lupaavimmista tutkimussuunnista on virheenkorjauskoodeihin pohjautuva kryptografia, jossa perustana on laskettavuusteoriassa tunnettu NP-täydellinen ongelma: satunnaisen koodisyndrooman dekoodaus. Tämän ongelman uskotaan olevan vaativa myös kvanttitietokoneille. Robert McEliecen vuonna 1978 esittämää alkuperäistä koodipohjaista salausjärjestelmää on tutkittu paljon ja sille on esitetty lukuisia muunnelmia. Näissä puutteellinen peite esitettyjen muunnelmien koodirakenteille on osoittautunut yleiseksi haasteeksi. Salaisen koodirakenteen avulla voidaan ohittaa kryptografinen vaativa ongelma ja purkaa salattu viesti suoraan hyödyntämällä näitä rakenteellisia heikkouksia. Twist-koodit ovat tutkimuksessa suhteellisen uusi koodiluokka ja niistä on ehdotettu tiettyjä rakennelmia tarkasteltavaksi myös kryptografian suhteen. Näihin esiteltyihin rakennelmiin ei voida suoraan käyttää mitään olemassa olevia hyökkäyksiä. Tässä työssä käydään aluksi läpi alan kirjallisuutta liittyen koodipohjaiseen kryptografiaan. Tarkoituksena on kattaa riittävästi taustateoriaa, jotta voidaan kuvata sen avulla twist-koodien käyttö kryptografisessa salauksessa. Lopuksi tarkastellaa twist-koodien soveltuvuutta kokeellisten tulosten valossa.