Problemi na rešetkah, učenje z napakami in postkvantna kriptografija : delo diplomskega seminarja

Štrancar, Vid (avtor), Marc, Tilen (mentor)

V diplomski nalogi predstavimo problem LWE in šifrirno shemo osnovano na tem problemu. Pokažemo pravilnost in delno tudi varnost sheme pred napadi s klasičnimi računalniki. Opišemo napad s prevodom iskalnega problema LWE na problem najkrajšega vektorja na rešetkah in uporabo algoritma za reševanje tega problema.

• Jezik: Slovenski jezik
• Ključne besede: kriptosistemi z javnim ključem, post-kvantna kriptografija, uče- nje z napakami (LWE), problemi na rešetkah, problem najkrajšega vektorja (SVP)
• Vrsta gradiva: Delo diplomskega seminarja/zaključno seminarsko delo/naloga
• Tipologija: 2.11 - Diplomsko delo
• Organizacija: FMF - Fakulteta za matematiko in fiziko
• Leto izida: 2022
• PID: 20.500.12556/RUL-143439
• UDK: 519.8
• COBISS.SI-ID: 135688451
• Datum objave v RUL: 21.12.2022

Sekundarni jezik

• Jezik: Angleški jezik
• Naslov: Lattice problems, learning with errors and post-quantum cryptography

Izvleček

We define LWE search problem and describe public key-cryptosystem based on such problem, for which we prove correctness and partially prove security against attacks with classical computers. We also describe an attack on such cryptosystem by reducing it to shortest vector problem on lattices and describing an algorithm for solving it.

• Ključne besede: public key cryptosystem, post-quantum cryptography, learning with errors (LWE), lattice problems, shortest vector problem (SVP)