Pregled post-kvantnih kriptografskih sustava

diplomski rad

• Autor: Kristian Čurla
• Mentor: Matija Kazalicki (mentor)
• Član povjerenstva: Matija Kazalicki (predsjednik povjerenstva)
• Član povjerenstva: Igor Ciganović (član povjerenstva)
• Član povjerenstva: Marcela Hanzer (član povjerenstva)
• Član povjerenstva: Dražen Adamović (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Prirodoslovno-matematički fakultet; (Matematički odsjek); Zagreb
• Datum i država obrane: 2019-07-16, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: PRIRODNE ZNANOSTI; Matematika

Sažetak

Ovaj rad bavi se alternativnim kriptosustavima koji odolijevaju napadima kvantnih računala. Rad je podijeljen u 3 poglavlja. U prvom poglavlju dajemo motivaciju za promatranje takvih sustava. Objašnjavamo neke osnovne pojmove iz kriptografije te ističemo neke ključne karakteristike koje čine neki kriptosustav dobrim. Zatim provodimo kratki uvod u kvantno računanje, gdje objašnjavamo razliku između klasičnog i kvantnog računala te pokazujemo kako funkcionira računanje u kvantnom okruženju. Za kraj prvog poglavlja ukratko objašnjavamo najbitniji kvantni algoritam: Shorov algoritam. Shorov algoritam nam omogućuje da lako faktoriziramo brojeve i time probijemo većinu danas korištenih kriptosustava. Upravo iz tog razloga pojavljuje se potreba za kriptosustavima koji se baziraju na drugačijoj klasi problema. U drugom poglavlju prezentiramo prvu klasu takvih problema, problemi definirani nad rešetkama, te objašnjavamo primjer jednog kriptosustava baziranog na tim problemima, GGH kriptosustav s javnim ključem. U tom poglavlju definiramo rešetke te pokazujemo neka ključna svojstva. Zatim opisujemo većinu bitnih problema nad rešetkama poput SVP-a i CVP-a. Za kraj, definiramo GGH kriptosustav, objašnjavamo kako radi i koje su mu mane i prednosti. U zadnjem, trećem poglavlju, prezentiramo drugu klasu problema koji trenutačno odolijevaju kvantnim napadima, problemi definirani nad kodovima. Prvo objašnjavamo što su kodovi i kroz primjer objašnjavamo njihova bitna svojstva. Ključno od svih tih svojstava je mogućnost korekcije pogreške i upravo oko tog svojstva je Mceliece dizajnirao svoj kriptosustav. Pred kraj poglavlja objašnjavamo ideju Mceliecevog kriptosustava te komentiramo njegove kvalitete za praktičnu primjenu.

Sažetak (engleski)

This paper deals with alternative cryptosystems which resist the attacks of quantum computers. The work is divided into 3 chapters. In the first chapter we give the motivation to observe such systems. We explain some basic concepts from cryptography and point out some key features that make a given cryptosystem good. Then we give a short introduction to quantum computing, explaining the difference between a classical and a quantum computer, in addition to showing how computation works in a quantum environment. For the end of the first chapter we briefly explain the most important quantum algorithm: Shor’s algorithm. Shor’s algorithm allows us to easily factorize numbers and thus break most of the cryptosystems used today. For this reason, there is a need for cryptosystems based on a different class of problems. In the second chapter we present the first class of such problems, the problems defined over lattices, and we explain an example of a cryptosystem based on these problems, the GGH cryptosystem with a public key. At the beginning this chapter, we define lattices and show some key features. Then we describe most of the major problems on lattices such as SVP and CVP. To conclude, we define the GGH cryptosystem, explain how it works and what are the drawbacks and advantages. In the last, third chapter, we present another class of problems that are currently resisting quantum attacks, code based problems. First we explain what the codes are and using an example code explain their essential properties. The most important of all these features is the ability to correct errors and precisely around this feature has Mceliece designed his cryptosystem. At the end of the chapter, we explain the idea of the Mceliece cryptosystem and comment on its quality for practical application.

• Ključne riječi: kriptosustav; kvantno računalo; kriptografija; Shorov algoritam; GGH kriptosustav; Mceliecev kriptosustav
• Ključne riječi (engleski): cryptosystem; quantum computer; cryptography; Shor’s algorithm; GGH cryptosystem; Mceliece cryptosystem
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:217:832020
• Studijski program: Naziv: Računarstvo i matematika; Vrsta studija: sveučilišni; Stupanj studija: diplomski; Akademski / stručni naziv: magistar/magistra računarstva i matematike (mag. inf. et math.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Otvoreni pristup
• Datum i vrijeme pohrane: 2019-09-17 10:38:24