Pregled post-kvantnih kriptografskih sustava

master's thesis

• Author: Kristian Čurla
• Mentor: Matija Kazalicki (mentor)
• Committee member: Matija Kazalicki (predsjednik povjerenstva)
• Committee member: Igor Ciganović (član povjerenstva)
• Committee member: Marcela Hanzer (član povjerenstva)
• Committee member: Dražen Adamović (član povjerenstva)
• Granter: University of Zagreb; Faculty of Science; (Department of Mathematics); Zagreb
• Defense date and country: 2019-07-16, Croatia
• Scientific / art field, discipline and subdiscipline: NATURAL SCIENCES; Mathematics

Abstract

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.

Abstract (english)

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.

• Keywords: kriptosustav; kvantno računalo; kriptografija; Shorov algoritam; GGH kriptosustav; Mceliecev kriptosustav
• Keywords (english): cryptosystem; quantum computer; cryptography; Shor’s algorithm; GGH cryptosystem; Mceliece cryptosystem
• Language: croatian
• URN:NBN: urn:nbn:hr:217:832020
• Study programme: Title: Computer Science and Mathematics; Study programme type: university; Study level: graduate; Academic / professional title: magistar/magistra računarstva i matematike (magistar/magistra računarstva i matematike)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Open access
• Created on: 2019-09-17 10:38:24