Laajenevat graafit ja hashfunktiot
Koskio, Maria (2020)
2020
Matematiikan maisteriohjelma - Master´s Programme in Mathematics
Informaatioteknologian ja viestinnän tiedekunta - Faculty of Information Technology and Communication Sciences
This publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited.
Hyväksymispäivämäärä
2020-12-11
Julkaisun pysyvä osoite on
https://urn.fi/URN:NBN:fi:tuni-202012078580
https://urn.fi/URN:NBN:fi:tuni-202012078580
Tiivistelmä
Tutkielmassa tarkastellaan laajenevia graafeja ja hashfunktioita. Aluksi käsitellään yleisesti hashfunktioita ja niiden tietoturvaominaisuuksia sekä graafi- ja spektraaligraafiteorian perusteita. Täten annetaan tarvittavat pohjatiedot varsinaisten aiheiden ymmärtämiseen. Tämän jälkeen siirrytään laajenevien graafien perheiden pariin, jotka määritellään kahdella eri tavalla; ensin laajenemissuhteiden perusteella ja sitten spektrien aukkojen kokoihin perustuen. Jälkimmäisen osoitetaan olevan ekvivalentti edeltävän kanssa. Lopuksi käsitellään laajenevia hashfunktioita keskittyen niiden tietoturvaominaisuuksiin sekä kokonaiskuvan hahmottamiseen. Yleisen tarkastelun jälkeen esitellään laajenevat ZT-, LPS- ja Pizerin hashfunktiot.