Název:
Problém LWE a bezpečnost schémat pro výměnu klíče
Překlad názvu:
LWE and provably secure key exchange schemes
Autoři:
Václavek, Jan ; Příhoda, Pavel (vedoucí práce) ; Žemlička, Jan (oponent) Typ dokumentu: Bakalářské práce
Rok:
2019
Jazyk:
cze
Abstrakt: [cze][eng] 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ý. 1The 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
Klíčová slova:
LWE problém; mříž; výměna klíče; key exchange; lattice; LWE problem