Varna primerjava številSTRGAR, ANDRAŽ (Avtor) Žitnik, Arjana (Mentor) varna primerjava številhomomorfen kriptosistemElGamalov kriptosistemvarnostprotokolV 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.20222022-03-17 12:00:00Diplomsko delo/naloga135530VisID: 31981COBISS_ID: 102572291sl