| dc.description.abstract | I 2009 presenterte Craig Gentry det første krypteringssystemet som klarte å utføre vilkårlig mange homomorfe operasjoner, og i prosessen lagde han også en framgangsmåte på hvordan man konstruerer et slikt system. I denne masteroppgaven skal vi se nærmer på tre av disse homomorfiske systemene, analysere dem og se på forskjellene dem i mellom.
Det første systemet som vi vil presentere er Gentrys konstruksjon som er basert på ideale lattices, hvor vi vil se på hans framgangsmåte på hvordan man lager et fult homomorft krypteringssystem. Vi ønsker et system som klarer å utføre noen homomorfe operasjoner, før vi ender opp med dekryptering feil. Hvert nye siffertekst kommer med noe støy, som gjemmer meldingen. Når vi utfører homomorfe operasjoner vil denne støyen øke i størrelse og forårsake dekryptering feilene. Det å lage et delvis homomorft krypteringssystem er ikke det største problemet, støyen er. Den geniale ideen til Gentrys konstruksjon er hvordan man kan reduserer støyen i siffertekster uten å avsløre informasjon om meldingene. Alle tre krypteringssystemene som vi skal se på følger Gentrys konstruksjon, men de bruker ikke den samme metoden for å redusere støy.
I Gentrys konstruksjon heter støyreduksjons metoden 'bootstrapping', hvor vi re-krypterer siffertekster under en ny nøkkel og dekrypterer den gamle homomorfiskt, dvs., dekrypteringen er gjort på et 'dobbelt' kryptert siffertekst hvor vi bare fjerner den gamle nøkkelen.
I det andre systemen som vi skal se på, av Brakerski, Gentry, og Vaikuntanathan, baserer sikkerheten på maskinfeil problemet 'learning with errors'. Systemet bruker en annen støyreduksjons metode kalt 'modulo bytting'. Denne metoden reduserer siffertekstene og runder dem av hensiktsmessig, hvor avrundingen må gjøres med litt forsiktighet. Det tredje, og siste, systemet vi skal presentere, av López-Alt, Tromer, og Vaikuntanathan, er konstruert fra krypteringssystemet NTRU, en av de tidligste lattice baserte systemene. Støyreduksjons metoden i dette systemet er det samme som i det andre, det vil si, modulo bytting.
Når vi reduserer støyen og lager nye siffertekster, gir vi de en ny offentlig nøkkel som den er kryptert under. I Gentrys bootstrapping skjer det naturlig når vi re-krypterer siffertesktene. I det andre systemet må vi bytte nøklene for å unngå å måtte anta at systemet er sirkulært sikkert. I det tredje systemet må vi bytte nøklene for å forsikre oss at vi kan klare å dekryptere siffertekstene. Det å måtte bytte nøkler etter (nesten) alle homomorfe operasjoner lager et system som er bygd opp av flere nivåer, hvor vært nivå har sin menge med nøkler. | nb_NO |
