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

Štrancar, Vid (author), 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.

• Language: Slovenian
• Keywords: kriptosistemi z javnim ključem, post-kvantna kriptografija, uče- nje z napakami (LWE), problemi na rešetkah, problem najkrajšega vektorja (SVP)
• Work type: Final seminar paper
• Typology: 2.11 - Undergraduate Thesis
• Organization: FMF - Faculty of Mathematics and Physics
• Year: 2022
• PID: 20.500.12556/RUL-143439
• UDC: 519.8
• COBISS.SI-ID: 135688451
• Publication date in RUL: 21.12.2022

Secondary language

• Language: English
• Title: Lattice problems, learning with errors and post-quantum cryptography

Abstract

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.

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