Vi gör en teoretisk och praktisk jämförelse av två Ring-LWE-baserade, skalinvarianta, jämnade homomorfa krypteringssystem -Fan och Vercauterens anpassning av BGV och YASHE-systemet som föreslås av Bos, Lauter, Loftus och Naehrig. I synnerhet förklarar vi hur man väljer parametrar för att säkerställa korrekthet och säkerhet mot latticeattacker. Vårt parameterval förbättrar van de Pols och Smarts tillvägagångssätt att välja parametrar för system baserade på Ring-LWE-problemet genom att använda simuleringsalgoritmen BKZ-2.0. Vi implementerade både krypteringssystem i C++, med hjälp av det aritmetiska biblioteket FLINT, och jämförde dem i praktiken för att bedöma deras respektive styrkor och svagheter. I synnerhet gjorde vi en homomorf utvärdering av den lätta block chiffer SIMON. Kombinera block chiffer med homomorphic kryptering gör det möjligt att lösa Gargantuan chiffertext expansion i molnprogram. Detta arbete startades när den första författaren var praktikant i Cryptography Forskargruppen vid Microsoft Research. Tillväxt, Brakerski, Gentry och Vaikuntanathan införde begreppet planade homomorfa krypteringssystem [BGV12]. I ett sådant system, buller växer endast linjärt med den multiplikativa djupet av kretsen utvärderas. Därför kan man för en given krets av rimligt djup välja parametrarna i systemet för att homomorfiskt utvärdera kretsen i en rimlig tid. De beskriver ett planat homomorphic krypteringssystem som kallas BGV med hjälp av en modulus switching teknik. Dessutom gör detta system och andra ringbaserade homomorfa krypteringssystem det möjligt att använda större mellanslag, där bitar ersätts av polynom med koefficienter modulo a simpletext modulus möjligen skiljer sig från 2. Sådana utrymmen för klartext tillåter kryptering av mer information i en enda chiffertext, till exempel genom batchning av bitar av klartext. BGV-systemet genomfördes därefter och användes för att utföra en homomorf utvärdering av AES-kretsen i [GHS12b]. Tyvärr, för att homomorfiskt utvärdera en krets av multiplikativ djup d med hjälp av modulus switching teknik, måste den allmänna nyckeln innehålla d distinkta versioner av en så kallad utvärderingsnyckel. För att homomorft utvärdera AES krävde författarna till [GHS12b] en mycket stor minnesmaskin (256 GB RAM) för att lagra den allmänna nyckeln. På Crypto 2012 föreslog Brakerski det nya begreppet skalan-invarians [Bra12] för planade homomorfa krypteringssystem. I motsats till ett system som använder sig av modulbyte, behåller chiffertexterna för ett skalinvariantsystem samma moduler under hela den homomorfa utvärderingen och endast en kopia av den skalinvarianta utvärderingsnyckeln måste lagras. Denna teknik har anpassats till BGV-systemet [BGV12] av Fan och Vercauteren [FV12] och till López-Alt, Tromer och Vaikuntanatans system [LTV12] av Bos, Lauter, Loftus och Naehrig [BLLN13]. 3 De resulterande systemen kallas FV respektive YASHE. Ingen tillämpning av FV-systemet är känd (utom för en proof-of-concept-implementation i ett datoralgebra-system som används i [GLN12]. YASHE systemet [BLLN13] var den första (och enda) skalainvariant nivåed homomorphic krypteringssystem som genomförts hittills. Mycket tillfredsställande tidpunkter hävdas för en liten modul (som då endast kan hantera kretsar av multiplikativt djup högst 2) på en persondator. Tyvärr är genomförandet inte öppet tillgängligt för samhället. Skickar data till molnet. I typiska verklighetsscenarier för att använda FHE med molnapplikationer kommunicerar en eller flera kunder med en molntjänst. De laddar upp data krypterade med ett FHE-system under en specifik användares öppna nyckel. Molnet kan bearbeta denna data homomorfiskt och returnera ett krypterat resultat. Tyvärr, chiffertextexpansion (dvs. De nuvarande FHE-systemens chiffertextstorlek dividerad med den enkla textstorleken är oöverkomlig (tusentals till miljoner). Till exempel att använda tekniker i [CNT12] (för 72 bitar av påstådd säkerhet), skicka 4MB av data som molnet tillåts att fungera, skulle kräva att skicka mer än 73TB krypterade data över nätverket. Batching flera enkla texter till en enda chiffertext [GHS12a,CCK + 13] kan förbättras på den nödvändiga bandbredden; med [CCK + 13] till exempel skulle nätverkskommunikationen sänkas till cirka 280 GB. Detta är dock fortfarande helt opraktiskt. För att lösa detta problem föreslogs det i [NLV11] att i stället skicka uppgifterna krypterade med ett blockchiffer (särskilt AES). Molntjänsten krypterar sedan chiffertexterna med FHE-systemet och användarens öppna nyckel och dekrypterar dem homomorft innan de bearbetas. Därför sänks nätverkskommunikationen till datastorleken (som är optimal) plus en kostsam engångsinställning som består i att skicka den allmänna FHE-nyckeln och en FHE-kryptering av blockets hemliga nyckel (jfr. Fig. 1)................................................................................................... Detta förslag kräver en homomorf utvärdering av blocket chiffer dekryptering, som framgångsrikt genomfördes för AES i [GHS12b] och [CCK + 13,CLT14], baserat på två olika homomorphic system (resp. över gitter och över heltal). Författarna till de tidigare nämnda tidningarna använde bitslicing tekniker [Bih97, KS09] och batching. Partieringen tillåts utföra flera oberoende AES-dekrypteringsåtgärder parallellt (eller AES i räknarläge). Den resulterande homomorfa utvärderingen av AES tog 65 timmar 4 och bearbetade 720 block parallellt för [GHS12b] (det är en relativ tid på 5 minuter per block) och tog 102 timmar 5 och bearbetade 1875 block parallellt för [CLT14] (det är en relativ tid på 3 minuter per block). 3 Denna teknik anpassades också till homomorfa krypteringsschemat över heltalen [vDGHV10] av Coron, Lepoint och Tibouchi [CLT14]. 4 På en Intel Xeon-processor som körs på 2,0 GHz. 5 På en Intel Xeon E5-2690 på 2,9 GHz.
I REF genomförde Lepoint och Naehrig två utbildningsprogram, FV och YASHE, med hjälp av biblioteket FLINT.
A Comparison of the Homomorphic Encryption Schemes FV and YASHE
{'venue': 'IACR Cryptology ePrint Archive', 'journal': 'IACR Cryptology ePrint Archive', 'mag_field_of_study': ['Computer Science']}