Varna primerjava števil

diplomsko delo

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

Abstract

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.

Keywords

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

Data

Language:	Slovenian
Year of publishing:	2022
Typology:	2.11 - Undergraduate Thesis
Organization:	UL FRI - Faculty of Computer and Information Science
Publisher:	[A. Strgar]
UDC:	004:51(043.2)
COBISS:	102572291
Views:	505
Downloads:	97
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	English
Secondary title:	Secure integer comparison
Secondary abstract:	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.
Secondary keywords:	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;
Type (COBISS):	Bachelor thesis/paper
Study programme:	1000407
Embargo end date (OpenAIRE):	1970-01-01
Thesis comment:	Univ. v Ljubljani, Fak. za računalništvo in informatiko
Pages:	47 str.
ID:	14785369