Kriptografija bazirana na rešetkama

diplomski rad

• Naslov (engleski): Lattice-based cryptography
• Autor: Martina Radenić
• Mentor: Filip Najman (mentor)
• Član povjerenstva: Filip Najman (predsjednik povjerenstva)
• Član povjerenstva: Zrinka Franušić (član povjerenstva)
• Član povjerenstva: Goran Igaly (član povjerenstva)
• Član povjerenstva: Hrvoje Planinić (č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: 2023-03-06, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: PRIRODNE ZNANOSTI; Matematika

Sažetak

Pojavom LLL algoritma za redukciju baze rešetke, one postaju bitan čimbenik u razvoju kriptografskih sustava. Kriptografija bazirana na rešetkama temelji se na složenosti problema rešetki, čija je osnova problem najkraćeg vektora. Ovdje nam je kao ulaz dana rešetka zadana svojom bazom, a cilj nam je pronaći najkraći vektor rešetke različit od nule. Ovakvi sustavi pružaju obećavajuće rješenje za post-kvantnu kriptografiju jer se vjeruje da su upravo problemi nad rešetkama NP-teški čak i za kvantna računala. Začetnikom ideje o kriptosustavima baziranim na rešetkama smatra se Ajtai-Dwork kriptosustav. Ima veliku teoretsku važnost te svojim idejama i rezultatima složenosti služi kao preteča mnogih drugih kriptosustava. Njegovim stopama idu sustavi poput GGH i NTRU sustava koji uz odlične rezultate složenosti imaju i bolju efikasnost. Veliku većinu NIST-ovih finalista čine upravo sustavi temeljeni na problemima vezanim uz rešetke. čak tri takva algoritma (CRYSTALS-Kyber, NTRU i SABER) proglašena su finalistima za mehanizme enkapsulacije ključa. Upravo CRYSTALS-Kyber je u srpnju 2022. godine i standardiziran od strane NIST-a. Uzevši u obzir složenost problema rešetki i vremenske i prostorne složenosti algoritama baziranih na njoj, da se naslutiti da će uloga rešetki u kriptografiji samo dobivati na značajnosti. Možemo pretpostaviti da u rešetkama leži naša sigurna budućnost, barem dok se ne dokaže suprotno.

Sažetak (engleski)

With the emergence of the LLL algorithm for lattice basis reduction, lattices became an important factor in the development of cryptographic systems. Lattice-based cryptography is based on the complexity of the lattice problem, the basis of which is the shortest vector problem. Here, we are given a lattice with its base as input, and our goal is to find the shor- test non-zero lattice vector. Such systems provide a promising solution for post-quantum cryptography because it is believed that problems concerning lattices are NP-hard even for quantum computers. The initial idea of lattice-based cryptosystems is considered to be introduced in the Ajtai-Dwork cryptosystem. It has great theoretical importance and with its ideas and com- plexity results serves as inspiration for many others. Following in its footsteps are systems like the GGH and NTRU, which, in addition to excellent complexity results, also have better efficiency. The vast majority of NIST’s finalists are systems based on lattice problems. As many as three such algorithms (CRYSTALS-Kyber, NTRU and SABER) were declared finalists for key encapsulation mechanisms. It was CRYSTALS-Kyber that was standardized by NIST in July of 2022. Taking into account the complexity of the problem of lattices and the temporal and spatial complexity of algorithms based on it, one can guess that the role of lattices in cryptography will only gain more importance. It is reasonable to assume that the future of cybersecurity lies in the use of lattices, at least until proven otherwise.

• Ključne riječi: LLL algoritam; kriptografski sustavi; problem najkraćeg vektora; post-kvantna kriptografija; Ajtai-Dwork kriptosustav; GGH; NTRU; CRYSTALS-Kyber; SABER
• Ključne riječi (engleski): LLL algorithm; cryptographic systems; shortest vector problem; post-quantum cryptography; Ajtai-Dwork cryptosystem; GGH; NTRU; CRYSTALS-Kyber; SABER
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:217:750030
• 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: 2023-08-18 09:00:13