Homomorfno šifriranje in problem učenja z napakami

magistrsko delo

Andraž Jelenc (Author), Tilen Marc (Mentor)

Abstract

Moč kvantnih računalnikov se iz leta v leto povečuje. Če bo razvit dovolj zmogljiv, bo z njim mogoče razbiti kriptosisteme, ki so danes v množični uporabi. Da bomo kljub temu lahko še vedno varno komunicirali, je potrebno namesto obstoječih vpeljati nove kriptosisteme, ki bodo odporni na napade s kvantnim računalnikom. Ti kriptosistemi morajo temeljiti na problemih, ki veljajo za težke tako na klasičnih, kot tudi na kvantnih računalnikih. Eden izmed takih problemov je problem učenja z napakami. V tem delu predstavimo kriptosistem, ki temelji na posplošitvi tega problema na polinomske kolobarje nad končnimi obsegi. Pokažemo, da ta kriptosistem omogoča polno homomorfno šifriranje. To pomeni, da lahko na kriptogramih izračunamo poljubno funkcijo in dobimo enak šifriran rezultat, kot če bi to funkcijo izvedli na nešifriranih podatkih. Homomorfno šifriranje tako odpira široke možnosti uporabe. Kot primer predstavimo algoritem za zaseben izračun preseka množic, ki ga tudi implementiramo s knjižnico SEAL.

Keywords

kriptografija;kriptosistem;homomorfno šifriranje;polinomski kolobar;

Data

Language:	Slovenian
Year of publishing:	2021
Typology:	2.09 - Master's Thesis
Organization:	UL FMF - Faculty of Mathematics and Physics
Publisher:	[A. Jelenc]
UDC:	519.8
COBISS:	67512323
Views:	1231
Downloads:	142
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	English
Secondary title:	Homomorphic encryption and learning with errors
Secondary abstract:	The power of quantum computers is increasing from year to year. If a sufficiently powerful quantum computer is developed, it will be possible to break the cryptosystems that are massively used today. If we still want to communicate securely, it is necessary to introduce new cryptosystems that will be resistant to quantum computer attacks. These cryptosystems must be based on problems that are considered difficult on both classical and quantum computers. Learning with errors is one of those problems. We present a cryptosystem that is based on generalization of this problem to polynomial rings over finite fields. This cryptosystem supports fully homomorphic encryption. This means that we can compute any function on cryptograms and get the same encrypted result as if we performed this function on unencrypted data. Homomorphic encryption opens up wide possibilities of usage. As an example, we present an algorithm for private set intersection, which we also implement with the SEAL library.
Secondary keywords:	cryptography;cryptosystem;homomorphic encryption;polynomial ring;
Type (COBISS):	Master's thesis/paper
Study programme:	0
Embargo end date (OpenAIRE):	1970-01-01
Thesis comment:	Univ. v Ljubljani, Fak. za matematiko in fiziko, Oddelek za matematiko, Računalništvo in matematika - 2. stopnja
Pages:	VII, 55 str.
ID:	13059382