velikost textu

Problém LWE a bezpečnost schémat pro výměnu klíče

Upozornění: Informace získané z popisných dat či souborů uložených v Repozitáři závěrečných prací nemohou být použity k výdělečným účelům nebo vydávány za studijní, vědeckou nebo jinou tvůrčí činnost jiné osoby než autora.
Název:
Problém LWE a bezpečnost schémat pro výměnu klíče
Název v angličtině:
LWE and provably secure key exchange schemes
Typ:
Bakalářská práce
Autor:
Bc. Jan Václavek
Vedoucí:
Mgr. Pavel Příhoda, Ph.D.
Oponent:
Mgr. Jan Žemlička, Ph.D.
Id práce:
212059
Fakulta:
Matematicko-fyzikální fakulta (MFF)
Pracoviště:
Katedra algebry (32-KA)
Program studia:
Matematika (B1101)
Obor studia:
Obecná matematika (MOM)
Přidělovaný titul:
Bc.
Datum obhajoby:
21. 6. 2019
Výsledek obhajoby:
Výborně
Jazyk práce:
Čeština
Klíčová slova:
LWE problém, mříž, výměna klíče
Klíčová slova v angličtině:
LWE problem, lattice, key exchange
Abstrakt:
Hrozba silného kvantového počítače vede ke snaze založit kryptosystémy na problémech, které budou těžké i pro kvantový počítač. V této práci si předsta- víme problém LWE, o kterém se předpokládá, že by takovým problémem mohl být. Nejprve si představíme mříže, které s problémem LWE úzce souvisí. Zave- deme základní pojmy, popíšeme mřížové problémy a vyřešíme cvičení týkající se pokrývajícího poloměru mříže. Poté definujeme problém LWE, představíme jeho varianty a ukážeme redukce dvou mřížových problémů na vhodnou variantu pro- blému LWE. K tomuto účelu definujeme pojem statistické vzdálenosti a dokážeme o něm tvrzení, která potřebujeme pro redukci. Nakonec ukážeme konkrétní vyu- žití problému LWE. Popíšeme schéma na výměnu klíče a naznačíme, jak dokázat jeho bezpečnost za předpokladu, že problém LWE je těžký. 1
Abstract v angličtině:
The threat of large-scale quantum computers motivates cryptographers to base cryptosystems on problems believed to be resistant against quantum computers. In this thesis, we focus on the LWE problem which is believed to be resistant against quantum computers. First, we describe lattices which are closely related to the LWE problem. We introduce basic notions, describe lattice problems and solve exercises related to the covering radius of lattice. After that, we introduce the LWE problem and its variants. We prove reductions from two lattice problems to certain variant of the LWE problem. We define the notion of statistical distance and prove some lemmata about it which we need within reductions. Moreover, we show concrete application of the LWE problem. We describe a scheme for key exchange and briefly prove its security under the assumption that the LWE problem is hard. 1
Dokumenty
Stáhnout Dokument Autor Typ Velikost
Stáhnout Text práce Bc. Jan Václavek 781 kB
Stáhnout Abstrakt v českém jazyce Bc. Jan Václavek 45 kB
Stáhnout Abstrakt anglicky Bc. Jan Václavek 44 kB
Stáhnout Posudek vedoucího Mgr. Pavel Příhoda, Ph.D. 49 kB
Stáhnout Posudek oponenta Mgr. Jan Žemlička, Ph.D. 100 kB
Stáhnout Záznam o průběhu obhajoby prof. RNDr. Jan Rataj, CSc. 152 kB