Varna primerjava števil

diplomsko delo

Andraž Strgar (Avtor), Arjana Žitnik (Mentor)

Povzetek

V diplomski nalogi predstavimo učinkovito rešitev za Yaov problem milijonarjev. Problem govori o dveh milijonarjih, ki želita izvedeti, kdo od njiju je bogatejši, ne da bi razkrila svoje premoženje. Za problem obstaja več rešitev, a starejše rešitve niso učinkovite, saj števili primerjajo po bitih, kar pomeni, da je potrebno šifrirati in dešifrirati vsak bit posebej. Namesto tega opisani protokol primerja celotni števili, kar pomeni, da potrebujemo le eno šifriranje, če le nista števili preveliki. Najprej opišemo homomorfen kriptosistem, katerega lastnosti nam omogočajo, da primerjamo dve števili, ne da bi ju dešifrirali. Dokažemo tudi semantično varnost tega kriptosistema. Nato predstavimo protokol za varno primerjavo števil. Opazimo, da opisani homomorfni kriptosistem ni dovolj za varno primerjavo števil, saj v določenem primeru razkrije razliko med števili udeležencev. Zato v protokolu dodamo še en krog šifriranja, za kar uporabimo eksponentno varianto ElGamalovega kriptosistema. Na koncu dokažemo še pravilnost in varnost opisanega protokola.

Ključne besede

varna primerjava števil;homomorfen kriptosistem;ElGamalov kriptosistem;varnost;protokol;interdisciplinarni študij;univerzitetni študij;diplomske naloge;

Podatki

Jezik:	Slovenski jezik
Leto izida:	2022
Tipologija:	2.11 - Diplomsko delo
Organizacija:	UL FRI - Fakulteta za računalništvo in informatiko
Založnik:	[A. Strgar]
UDK:	004:51(043.2)
COBISS:	102572291
Št. ogledov:	505
Št. prenosov:	97
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Angleški jezik
Sekundarni naslov:	Secure integer comparison
Sekundarni povzetek:	In this thesis we present an efficient solution to Yao's millionaires' problem. The problem describes two millionaires who want to know which of them is richer without revealing their actual wealth. The problem has many solutions, but older ones are inefficient, as they compare the integers bit by bit, which means each bit has to be encrypted and decrypted separately. On the contrary, our protocol compares the entire integers, which means we only need one encryption, if only the integers are not too big. We begin by describing a homomorphic cryptosystem, whose properties allow us to compare two integers without decrypting them. We also prove semantic security of the described cryptosystem. We continue by describing a protocol for secure integer comparison. We notice the aforementioned homomorphic cryptosystem is not enough for secure integer comparison, as it exposes the difference between the integers in some cases. That is why we add another round of encryption to our protocol. For that purpose we use the exponential version of ElGamal cryptosystem. At the end we prove the protocol works correctly and prove its security.
Sekundarne ključne besede:	secure integer comparison;homomrphic cryptosystem;ElGamal cryptosystem;security;protocol;computer science;computer and information science;computer science and mathematics;interdisciplinary studies;diploma;Vizualna kriptografija;Računalništvo;Univerzitetna in visokošolska dela;
Vrsta dela (COBISS):	Diplomsko delo/naloga
Študijski program:	1000407
Konec prepovedi (OpenAIRE):	1970-01-01
Komentar na gradivo:	Univ. v Ljubljani, Fak. za računalništvo in informatiko
Strani:	47 str.
ID:	14785369