Vi beskriver ett fungerande genomförande av en variant av Gentrys helt homomorfiska krypteringssystem (STOC 2009), liknande den variant som användes i ett tidigare genomförandearbete av Smart och Vercauteren (PKC 2010). Smart och Vercauteren implementerade det underliggande "något homomorphic" systemet, men kunde inte genomföra bootstrappning funktionalitet som behövs för att få hela systemet att fungera. Vi visar ett antal optimeringar som gör att vi kan genomföra alla aspekter av programmet, inklusive bootstrappa funktionalitet. Vår huvudsakliga optimering är en nyckelgeneration metod för den underliggande något homomorfisk kryptering, som inte kräver full polynom inversion. Detta minskar den asymtomotiska komplexiteten från Õ(n 2.5 ) till Õ (n 1.5 ) när man arbetar med dimension-n gitter (och praktiskt taget minskar tiden från många timmar/dagar till några sekunder/minuter). Andra optimeringar inkluderar en batching teknik för kryptering, en noggrann analys av graden av dekryptering polynomial, och vissa utrymme / tid kompromisser för den helt-homomorphic schema. Vi testade vårt genomförande med gitter av flera dimensioner, motsvarande flera säkerhetsnivåer. Från en leksaksinställning i dimension 512 till "liten", "medium" och "stora" inställningar i dimensionerna 2048, 8192 respektive 32768. Den allmänna nyckelstorleken varierar i storlek från 70 megabyte för den "små" inställningen till 2,3 gigabyte för den "stora" inställningen. Tiden att köra en bootstrappning (på en 1-CPU 64-bitars maskin med stort minne) sträcker sig från 30 sekunder för den "små" inställningen till 30 minuter för den "stora" inställningen.
Till exempel tar nyckelgenerationen i Gentrys FHE-system från 2,5 sekunder till 2,2 timmar REF.
Implementing Gentry’s fully-homomorphic encryption scheme
{'venue': 'of Lecture Notes in Computer Science', 'journal': None, 'mag_field_of_study': ['Computer Science']}