text size

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.
Title:
Problém LWE a bezpečnost schémat pro výměnu klíče
Titile (in english):
LWE and provably secure key exchange schemes
Type:
Bachelor's thesis
Author:
Bc. Jan Václavek
Supervisor:
Mgr. Pavel Příhoda, Ph.D.
Opponent:
Mgr. Jan Žemlička, Ph.D.
Thesis Id:
212059
Faculty:
Faculty of Mathematics and Physics (MFF)
Department:
Department of Algebra (32-KA)
Study programm:
Mathematics (B1101)
Study branch:
General Mathematics (MOM)
Degree granted:
Bc.
Defence date:
21/06/2019
Defence result:
Excellent
Language:
Czech
Keywords (in czech):
LWE problém, mříž, výměna klíče
Keywords:
LWE problem, lattice, key exchange
Abstract (in czech):
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:
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
Documents
Download Document Author Type File size
Download Text of the thesis Bc. Jan Václavek 781 kB
Download Abstract in czech Bc. Jan Václavek 45 kB
Download Abstract in english Bc. Jan Václavek 44 kB
Download Supervisor's review Mgr. Pavel Příhoda, Ph.D. 49 kB
Download Opponent's review Mgr. Jan Žemlička, Ph.D. 100 kB
Download Defence's report prof. RNDr. Jan Rataj, CSc. 152 kB