Volledig Homomorfe Encryptie Bart P.G. Van Parys
Thesis voorgedragen tot het behalen van de graad van Master in de ingenieurswetenschappen: wiskundige ingenieurstechnieken Promotor: Prof. Dr. Ir. Bart Preneel Assessoren: Prof. Dr. Ir. M. Van Barel Prof. Dr. Ir. J. Vandewalle Begeleiders: Dr. Ir. F. Vercauteren Ir. J. Hermans
Academiejaar 2010 – 2011
c Copyright K.U.Leuven
Zonder voorafgaande schriftelijke toestemming van zowel de promotor(en) als de auteur(s) is overnemen, kopiëren, gebruiken of realiseren van deze uitgave of gedeelten ervan verboden. Voor aanvragen tot of informatie i.v.m. het overnemen en/of gebruik en/of realisatie van gedeelten uit deze publicatie, wend u tot het Departement Computerwetenschappen, Celestijnenlaan 200A bus 2402, B-3001 Heverlee, +32-16-327700 of via e-mail
[email protected]. Voorafgaande schriftelijke toestemming van de promotor(en) is eveneens vereist voor het aanwenden van de in deze masterproef beschreven (originele) methoden, producten, schakelingen en programma’s voor industrieel of commercieel nut en voor de inzending van deze publicatie ter deelname aan wetenschappelijke prijzen of wedstrijden.
Voorwoord Teneerste zou ik mijn promotor Prof. Dr. Ir. Bart Preneel en begeleiders Dr. Ir. Frederik Vercauteren en Ir. Jens Hermans willen bedanken om mij de kans te geven mijn masterproef in een stimulerende en hulpvolle omgeving af te werken. Het maken van een masterproef is een taak, die de student soms als onbegonnen werk bestempelt. Ik wil daarom mijn kotgenoten bedanken voor het creëren van een aangename omgeving en het aanreiken van een relativerende blik, waardoor het harde werk toch net iets dragelijker werd. Tenslotte wil ik met veel overtuiging al mijn vrienden en familieleden hartelijk danken. Niet alleen voor de steun tijdens deze masterproef, maar vooral voor de manier waarop zij mij hebben gesteund in goede en kwade dagen. Bart P.G. Van Parys
i
Inhoudsopgave Voorwoord
i
Samenvatting
v
Abstract
vi
Woordenlijst en symbolen Woordenlijst . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Acroniemen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 Inleiding 1.1 Wat is een homomorf encryptieschema ? 1.2 Een aantal toepassingen . . . . . . . . . 1.3 Het doel van deze thesis . . . . . . . . . 1.4 Omkadering en bereikte resultaten . . . 2 Homomorfe encryptie 2.1 Overzicht . . . . . . . . . . 2.2 Homomorfe encryptie . . . 2.3 Bootstrappable encryptie . 2.4 De squahing transformatie . 2.5 Een praktische demonstratie 3 De 3.1 3.2 3.3 3.4 3.5 3.6 3.7
ii
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
Smart-Vercauteren variant Het initiële homomorfe schema, abstract . . . . . Het initiële homomorfe schema, concreet . . . . . Verband met de algemene Gentry constructie . . Hoe homomorf is het initiële schema ? . . . . . . Het volledig homomorfe schema . . . . . . . . . . Recryptieprocedure . . . . . . . . . . . . . . . . . Veiligheidsanalyse en bepalen van de parameters 3.7.1 De parameters λ en µ . . . . . . . . . . . 3.7.2 Onomkeerbaarheid van encryptie . . . . . 3.7.3 Brutekrachtaanval op de ruis . . . . . . .
. . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . .
vii vii viii
. . . .
1 2 3 4 4
. . . . .
7 7 8 9 11 12
. . . . . . . . . .
13 13 15 17 18 20 24 24 25 25 26
Inhoudsopgave . . . . . . . . . . schema . . . . . . . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
26 27 27 29 29
DGHV variant Het initiële homomorfe schema . . . . . . . . . . . . Het volledig homomorfe schema . . . . . . . . . . . . Veiligheidsanalyse en bepalen van de parameters . . 4.3.1 Onomkeerbaarheid van encryptie . . . . . . . 4.3.2 Brutekrachtaanval op de ruis . . . . . . . . . 4.3.3 Aanval op het SSSP . . . . . . . . . . . . . . 4.3.4 Zoeken naar de private sleutel . . . . . . . . . 4.3.5 De homomorfe diepte van het initiële schema 4.3.6 Samenvatting parameters . . . . . . . . . . . 4.4 Implementatieresultaten . . . . . . . . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
33 33 36 39 39 40 41 41 42 43 43
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .
47 47 48 51 53 53 54 56 57 59 60 61 64
3.8
3.7.4 Aanval op het SSSP . . . . . . . . . 3.7.5 Zoeken naar de private sleutel . . . . 3.7.6 De homomorfe diepte van het initiële 3.7.7 Samenvatting parameters . . . . . . Implementatieresultaten . . . . . . . . . . .
4 De 4.1 4.2 4.3
5 De 5.1 5.2 5.3 5.4
SIMD variant Inleiding . . . . . . . . . . . . . . . . . . . . . . . . . Velden en homomorfismen . . . . . . . . . . . . . . . Het initiële homomorfe schema . . . . . . . . . . . . Het volledig homomorfe schema . . . . . . . . . . . . 5.4.1 Recryptieprocedure, versie 1 . . . . . . . . . . 5.4.2 Recryptieprocedure, versie 2 . . . . . . . . . . 5.4.3 Recryptieprocedure, versie 3 . . . . . . . . . . 5.4.4 Recryptieprocedure, versie 4 (nieuw) . . . . . 5.5 Veiligheidsanalyse en bepalen van de parameters . . 5.5.1 De homomorfe diepte van het initiële schema 5.6 Implementatieresultaten . . . . . . . . . . . . . . . . 5.7 Resultaten . . . . . . . . . . . . . . . . . . . . . . . .
6 Recryptie met hulpservers 6.1 Inleiding . . . . . . . . . . . . . . . . . 6.2 Beschrijving . . . . . . . . . . . . . . . 6.3 Minimale initiële homomorfe schema’s 6.4 Performantie . . . . . . . . . . . . . . 6.5 Resultaat . . . . . . . . . . . . . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
65 65 65 68 69 70
7 Besluit 7.1 De Smart-Vercauteren variant 7.2 De DGHV variant . . . . . . 7.3 De SIMD variant . . . . . . . 7.4 Recryptie met hulpservers . . 7.5 Een blik op de toekomst . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
73 73 74 75 76 77
A Roosters A.1 Definities en eigenschappen . . . . . . . . . . . . . . . . . . . . . . .
81 81
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
iii
Inhoudsopgave A.2 Rooster basissen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A.3 De Hermite normaal vorm . . . . . . . . . . . . . . . . . . . . . . . .
82 84
B CD-ROM
87
C IEEE artikel
89
Bibliografie
97
iv
Samenvatting Recent in 2009, heeft Gentry het eerste volledig homomorfe encryptie schema uitgevonden. Hiermee eindigde hij de zoektocht van bijna 40 jaar naar een eerste volledig homomorf schema. Sindsdien zijn er een aantal volledig homomorfe schema’s opgesteld. Echter, een vergelijking tussen deze constructies heeft nog niet plaatsgevonden. Het eerste doel van deze masterproef is dan ook om de voorgestelde schema’s aan een eerlijke vergelijking te onderwerpen. Meer in het bijzonder worden in deze thesis 2 fundamentele schema’s vergeleken: de Smart-Vercauteren variant en de DGHV variant. De Smart-Vercauteren variant is een concrete instantie van het oorspronkelijke Gentry schema, beschreven in getallenvelden. De DGHV variant is een schema dat enkel gebruikmaakt van gehele getallen. Uit de gedane tijdmetingen valt te besluiten dat de Smart-Vercauteren variant performanter is dan de DGHV variant, ondanks wat de desbetreffende auteurs publiceerden. De SIMD variant is een volledig homomorf schema dat single instruction multiple data (SIMD) operaties toelaat. Deze variant is een natuurlijke veralgemening van de achterliggende idee gebruikt in de Smart-Vercauteren variant. Ook deze variant wordt vergeleken met de Smart-Vercauteren en DGHV variant; we beschouwen hierbij 3 verschillende versies om een boodschap te hersleutelen. We stellen ook een nieuwe hersleutelversie voor, die zeer performant blijkt wanneer het beoogde parallellisme groot is. Ook qua geheugen is deze versie zeer competitief in vergelijking met de andere versies. Er kan opgemerkt worden dat zelfs het meest performante schema beschreven in de literatuur bezwaarlijk praktisch performant kan worden genoemd. Daarom wordt finaal een praktisch schema voorgesteld dat, gebruikmakend van 2 vertrouwde hulpservers, wel praktisch haalbaar kan worden genoemd. Ook dit schema is voor een groot stuk gebaseerd op de Smart-Vercauteren variant. Wel kan opgemerkt worden dat dit schema natuurlijk extra veronderstellingen omtrent de veiligheid zal moeten gebruiken.
v
Abstract In 2009 Gentry came up with the first construction of a fully homomorphic encryption scheme based on ideal lattices, hereby ending the nearly 40 year old quest of finding such scheme. Since then a number of fully homomorphic encryption schemes were constructed. However, a comparison of these constructions has never been conducted. Hence, the primary objective of this thesis is to give a fair comparison between the proposed schemes. More in particular, we compare the 2 fundamental schemes: the Smart-Vercauteren scheme and the DGHV scheme. The Smart-Vercauteren scheme is a concrete instance of the original Gentry schema, described in terms of number fields. The DGHV variant is a scheme that is based only on integers, and hence is conceptually very simple. The conducted timings suggest that the Smart-Vercauteren scheme is considerable faster then the DGHV scheme, this in contrast with what is suggested in literature. The SIMD variant is a fully homomorphic encryption scheme that supports SIMD operations. This scheme is a natural extension of the idea behind the SmartVercauteren scheme. Also this scheme is compared to both the Smart-Vercauteren and the DGHV scheme; whereby we consider 3 different methods for recrypting messages. We also suggest a new recryption method, which is very performant when the needed level of parallelization is high. Also in terms of memory usage this method seems to be very competitive. Finally we note that even the most performant scheme proposed in literature can hardly be called practically feasible. Hence we suggest a practical scheme that, using 2 trusted servers, can be considered practically feasible. It should be noted however that this comes at the expense of extra security assumptions.
vi
Woordenlijst en symbolen Woordenlijst birthday attack Een verjaardagaanval is een cryptografische aanval die gebruik maakt van de wiskunde achter het verjaardagsprobleem in het kansrekenen. Vertaling van http://en.wikipedia.org/wiki/Birthday_attack. bootstrappable Eigenschap van een encryptieschema; in staat zijn om het decryptiecircuit en een extra universele poort homomorf te evalueren. Een nodige en voldoende voorwaarde om een correcte Recrypt procedure te ontwikkelen. circuit Een circuit in computerwetenschappen is een theoretische structuur dat een reëel circuit nabootst, waarbij ingangswaarden het circuit binnenkomen en waarbij de uitgang een toepassing is van een aantal poorten op deze ingangswaarden. Vertaling van http://en.wikipedia.org/wiki/Circuit_(computer_theory). cloud computing Cloud computing is het via het internet op aanvraag beschikbaar stellen van hardware, software en gegevens, ongeveer zoals energie uit het elektriciteitsnet. De term cloud staat voor het internet en de delen en acties van de applicatie die niet op de machine van de gebruiker plaatsvinden. Bron http://nl.wikipedia. org/wiki/Cloud_computing. Encrypt Vercijferalgoritme van een encryptieschema. In een publieke sleutel encryptieschema aanvaardt deze procedure een publieke sleutel pk en correcte boodschap m en geeft de cijfertekst c terug. vii
Acroniemen KeyGen Sleutelgeneratieprocedure in een encryptie schema. In een publieke sleutel encryptieschema wordt in deze methode een sleutelpaar pk en sk gegenereerd. Recrypt Procedure om een gegeven cijfertekst te vernieuwen zonder kennis van de private sleutel. Essentiële methode om een initieel schema volledig homomorf te maken. squahing Transformatie van een complex decryptiecircuit naar een ondiep decryptiecircuit, door het laten starten van decryptie bij encryptie. De resulterende extra informatie wordt de squashing informatie genoemd. squahing information Informatie die het decryptiecircuit van een schema minder complex maakt. Een belangrijke stap in het bootstrappable maken van de decryptieprocedure van een initieel homomorf schema.
Acroniemen
viii
AES
advanced encryption standard.
BDDP
bounded distance decoding problem.
CCA CRT CVP
chosen ciphertext attack. Chinese remainder theorem. closest vector problem.
FFT
fast Fourier transform.
GCD GSA
greatest common divisor. grade school addition.
HNF
hermite normal form.
IFFT
inverse fast Fourier transform.
MAC
message authentication code.
RSA
Rivest, Shamir en Adleman.
SIMD
single instruction multiple data.
Acroniemen SPIP SSSP SVP
small principal ideal problem. subset sum problem. shortest vector problem.
XGCD XOR
extended algorithm of Euclides. exclusive or.
Notatie [·]d [·]pk < · >d b·c d·e b·e Zp Fp = :=
Reductie naar het interval [−d/2, . . . , d/2). Versleuteld met de publieke sleutel pk. Reductie naar het interval [0, . . . , d). Afronden naar het grootste geheel getal dat kleiner is dan het gegeven getal. Afronden naar het kleinste geheel getal dat groter is dan het gegeven getal. Afronden naar het geheel getal dat het dichtst bij het geven getal ligt. De verzameling van restklassen van de congruentierelatie a = b mod p over de gehele getallen. Een eindig veld met p elementen. Gelijkheid Toekenning of definitie
ix
Hoofdstuk
Inleiding inds de ontdekking van asymmetrische cryptosystemen in de jaren 1970 door Diffie en Hellman [DH76] en hierop volgend de uitvinding van het RSA encryptieschema door Rivest, Shamir en Adleman [RSA78], is men in staat om informatie te versleutelen door middel van een publieke sleutel zodat die alleen nog ontcijferbaar is met de bijhorende private sleutel. Eenmaal versleuteld kan je met de meeste algoritmes niets meer aanvangen met de cijfertekst, tenzij je over de private sleutel beschikt.
S
Maar het Rivest, Shamir en Adleman (RSA) schema is een schema met een zeer eigenaardige eigenschap, het product van twee cijferteksten is gelijk aan de encryptie van het product van de onderliggende boodschappen. Meestal wordt deze eigenschap als een inherente zwakte beschouwd van het RSA schema, net omdat ze het rekenen met data door middel van cijferteksten toelaat. We zeggen dat RSA multiplicatief homomorf is, er kan gerekend worden met de data onder de cijferteksten zolang alleen vermenigvuldigingen moeten gebeuren. Echter, in sommige situaties is het zeer wenselijk dat een schema dergelijke eigenschappen bezit, denk maar aan een online stemcomputer die de versleutelde stemmen zou kunnen tellen zonder de private sleutel te bezitten. Op die manier zou de kiezer er zeker van zijn dat zijn stem onbekend blijft. Homomorfe encryptie schema’s laten de gebruiker toe om willekeurige bewerkingen uit te voeren op data met enkel de bijhorende cijferteksten en publieke sleutel in zijn/haar bezit. Dus niet alleen vermenigvuldigingen, zoals in het RSA schema, of optellingen zoals nodig in de online stemcomputer maar beide tegelijkertijd! Lang werd deze eigenschap van een encryptieschema als de heilige graal van de cryptografie beschouwd. Recent in 2009, heeft een onderzoeker aan het Stanford instituut, Craig Gentry aangetoond dat deze heilige graal wel degelijk bestaat. In deze context moet het materiaal in deze tekst bekeken worden, het is een poging om de vele volledig homomorfe schema’s, ontworpen sinds 2009, aan een heldere en eerlijke analyse te onderwerpen. 1
1
1. Inleiding +, x Enc !m , pk "
klaartekstruimte
cijfertekstruimte
Dec !c , sk "
Figuur 1.1: De origine van het woord homomorfe encryptie, in een homomorf schema zijn de cijfertekstruimte en de klaartekstruimte homomorf, met de encryptie en decryptiefunctie als morfismen.
1.1
Wat is een homomorf encryptieschema ?
Zoals reeds gezegd laat een volledig homomorf encryptieschema willekeurige bewerkingen op data toe, met enkel kennis van de bijhorende cijferteksten en de publieke sleutel. Hoewel er symmetrische homomorfe schema’s bestaan, bv. het Caesarcijfer met concatenatie als homomorfe bewerking, zullen in deze tekst alleen asymmetrische homomorfe encryptieschema’s besproken worden. Een hoog-niveau introductie in verband met asymmetrische encryptie kan gevonden worden in [Wik11], we onderstellen de terminologie in verband met asymmetrische encryptie gekend. In een volledig homomorf schema zijn de klaartekst ruimte en de cijfertekst ruimte homomorf aan elkaar, zie figuur 1.1. Dit is ook de reden waarom men spreekt van homomorfe encryptie, dit morfisme laat ons toe om te rekenen op data (klaartekstruimte) door middel van cijferteksten (cijfertekstruimte). De wiskunde garandeert dat overeenkomstige operaties ook worden uitgevoerd op de onderliggende boodschappen. Om het vorige wat duidelijker te maken, en te tonen wat nu juist bedoeld wordt met volledig homomorfe encryptie, geven we hier een kleine demonstratie. Stel Prof. Pythagoras geeft ons twee getallen a en b, weliswaar versleuteld met een volledig homomorf encryptie schema, en vraagt ons om de versleuteling van “c2 = a2 + b2 ” te berekenen. Hoe dit, gebruikmakend van volledig homomorfe encryptie, in zijn werk gaat wordt aangegeven in demonstratie 1.1. In de eerste stap maakt Prof. Pythagoras zijn sleutelpaar aan met de KeyGen procedure, geparameteriseerd door een hier irrelevante veiligheidsparameter λ. In de tweede en derde stap versleutelt hij de zelfgekozen getallen a en b met zijn publieke sleutel pk. Hierna begint het probleem voor ons, hoe berekenen we een vercijfering van 2
1.2. Een aantal toepassingen Algorithm 1.1 De demonstratie met Prof. Pythagoras 1: sk, pk := KeyGen(λ) 2: acijfertekst := Enc(a, sk) 3: bcijfertekst := Enc(b, sk) (2) 4: acijfertekst := Mult(a, a, pk) (2)
5:
bcijfertekst := Mult(b, b, pk)
6:
Antwoord := Add(acijfertekst , bcijfertekst , pk)
(2)
(2)
a2 + b2 met enkel de cijferteksten acijfertekst en bcijfertekst (we kunnen niet ontcijferen want we krijgen enkel de publieke sleutel)? Hier maken we gebruik van de kracht van volledig homomorfe encryptie; in de vierde en vijfde stap berekenen we de (2) (2) cijferteksten acijfertekst en bcijfertekst met behulp van de procedure Mult. De Mult methode voert de ⊗ bewerking uit tussen twee cijferteksten. Als Prof. Pythagoras (2) acijfertekst zou ontcijferen dan vindt hij exact a2 = a × a, zie ook figuur 1.1. In de laatste stap wordt met behulp van de Add methode het antwoord berekend. De Add methode voert de ⊕ bewerking uit tussen twee cijferteksten. Als Prof. Pythagoras het antwoord nakijkt dan moet hij besluiten dat we in onze opdracht geslaagd zijn want: a2 + b2 = Dec(Antwoord, sk) ! We zeggen dat we a2 + b2 homomorf hebben berekend, waarbij ⊕ en ⊗ respectievelijk de homomorfe additie en vermenigvuldigingsoperatie genoemd wordt. De notie van volledig homomorfe encryptie, oorspronkelijk genoemd privacy homomorphism, werd geïntroduceerd door Rivest, Adleman en Dertouzous [RAD78] kort na de uitvinding van RSA. Hieronder verstond men een publieke sleutel encryptieschema dat naast de gebruikelijke 3 basis procedures (sleutelgeneratie, encryptie en decryptie) een vierde procedure had genaamd Evaluate die werd gebruikt om een gegeven functie te evalueren op versleutelde data. Bijvoorbeeld, Antwoord := Evaluate(“x2 + y 2 ”, a, b, pk) in demonstratie 1.1. Pas in 2009 is Craig Gentry er als eerste in geslaagd [Gen09a] om een volledig homomorf schema op te stellen. In de volgende sectie geven we een aantal (mogelijke) toepassingen van volledig homomorfe schema’s.
1.2
Een aantal toepassingen
Sinds de introductie van de notie volledig homomorfe encryptie hebben cryptrografen een lange lijst opgebouwd van uiterst interessante toepassingen. We geven er hier een tweetal mee.
Filteren van versleutelde e-mails Heden ten dage krijgt iedereen er wel eens mee te maken: ongewenste berichten. We zouden graag hebben dat deze berichten automatisch verticaal worden geklasseerd, zodat onze aandacht kan gaan naar de belangrijkere zaken. Maar dan herinneren we R ons aan het feit dat we een webgebaseerde e-mail dienst gebruiken zoals Gmail , 3
1. Inleiding R Hotmail , etc. We hebben niet graag dat derden onze e-mails kunnen lezen. Daarom stellen we hier een methode voor, gebruikmakend van homomorfe encryptie, waarmee een derde toch zonder de boodschap te kennen de e-mail kan beoordelen als ongewenst. De webgebaseerde e-mail dienst hoeft nu slechts zijn filterfunctie toe te passen op de versleutelde data, om hiermee een versleuteling te krijgen van ‘0’ (deze mail is OK) of ‘1’ (deze mail is ongewenst). Nadien hoeft de cliënt alleen deze ene bit te ontcijferen en opent slechts de volledige boodschap als de bit ‘0’ was.
Rekenen met versleutelde data in de wolk Cloud computing is binnen de huidige IT infrastructuur van de meeste bedrijven een zeer relevant begrip geworden. Maar dit fenomeen brengt een aantal veiligheidsoverwegingen met zich mee. Bedrijven plaatsen hun data meestal in versleutelde vorm in de wolk en geven een vertrouwde computer de geheime sleutel zodat deze kan werken op de data. Het grote nadeel is natuurlijk dat die vertrouwde computer toegang heeft tot alle data, wat niet altijd gewenst is. Volledig homomorfe encryptie biedt in deze situaties een interessant alternatief. De data worden in versleutelde vorm in de wolk geplaatst en de wolk krijgt een kopie van de publieke sleutel, hiermee kan de wolk operaties op de data uitvoeren en de cliënt hoeft slechts nadien het resultaat op te vragen en te ontcijferen.
1.3
Het doel van deze thesis
Hoewel er sinds de introductie van het eerste volledig homomorfe schema in 2009 door Gentry een aantal varianten en alternatieven werden ontdekt, kunnen de tot op heden bestaande schema’s bezwaarlijk praktisch worden genoemd. Het doel van de thesis is dan ook tweeledig: (i) het analyseren en vergelijken van de bestaande systemen, en (ii) verbetering(en) of alternatieven voorstellen waar mogelijk. Om de schema’s te evalueren en op een eerlijke manier te kunnen vergelijken moet er natuurlijk een implementatie voorhanden zijn. Daar deze niet bestond werden alle schema’s op een zo eerlijk mogelijke manier geïmplementeerd in de hoog-niveau programmeertaal Magma [BCP97].
1.4
Omkadering en bereikte resultaten
In deze sectie proberen we een bondig overzicht te geven van deze thesis. Terzelfder tijd wensen we ook de doelstellingen en de geleverde prestaties in de verschillende hoofdstukken samen te vatten. In hoofdstuk 2 bespreken we de methode van Gentry, zoals die kan gevonden worden in [Gen09b], op een hoog-niveau manier, zodat de lezer de rode draad doorheen de hierop volgende hoofdstukken weet te herkennen. Het is namelijk zo dat elk bekend homomorf schema gebruikmaakt van de kernideeën van [Gen09b]. Dit hoofdstuk moet aldus gelezen worden als een inleiding op homomorfe encryptie. Dit hoofdstuk bevat ook de belangrijkste definities in verband met dit onderwerp. 4
1.4. Omkadering en bereikte resultaten In hoofdstuk 3 wordt een eerste fundamenteel volledig homomorf schema besproken. De Smart-Vercauteren variant, genoemd naar de auteurs van deze constructie [SV09], is een specifieke instantie van de algemene Gentry constructie besproken in hoofdstuk 2. Doordat we hier de constructie van [GH10] lichtjes aanpassen, worden de schemaparameters opnieuw afgeleid. De variant wordt geïmplementeerd, geanalyseerd en vergeleken met het tweede fundamenteel homomorfe schema besproken in het hierop volgende hoofdstuk. Uit tijdmetingen blijkt dat deze variant performanter is, zowel op vlak van tijdsefficientië als geheugengebruik. In hoofdstuk 4 wordt een tweede fundamenteel volledig homomorf schema besproken. De DGHV variant, waarbij het acroniem staat voor de auteurs van [vDGHV09], is een eerste echte variant, vermits dit geen instantie is van het algemene Gentry schema. Om een eerlijke vergelijking toe te laten moeten de veiligheidsonderstellingen in [vDGHV09] compatibel worden gemaakt met diegene gegeven in hoofdstuk 3. Nadat we de nieuwe schemaparameters hebben afgeleid, wordt ook deze variant geïmplementeerd en geanalyseerd. In [vDGHV09] laten de auteurs uitschijnen dat deze variant performanter is dan het Smart-Vercauteren schema in hoofdstuk 3, maar een eerlijke analyse en implementatie van beide schema’s toont ons hier net het tegenovergestelde. In hoofdstuk 5 wordt een variant op het Smart-Vercauteren schema besproken die ons toelaat meerdere bits per homomorfe operatie te behandelen, zie [SV11]. In deze variant, ook de SIMD variant genoemd, stellen we een nieuwe manier van recryptie voor. We implementeren en vergelijken de twee belangrijkste recryptieversies voorgesteld in [SV11] met onze nieuwe versie. Uit de tijdmetingen blijkt dat de nieuwe versie performanter is ten opzichte van de reeds bestaande recryptieprocedures uit [SV11]. Ook blijkt uit de tijdmetingen dat het gebruik van de SIMD variant, voor een voldoende aantal recrypties, efficiënter is dan het gebruik van de Smart-Vercauteren of DGHV variant. Finaal, in hoofdstuk 6 stellen we een nieuw praktisch volledig homomorf schema voor dat met behulp van 2 vertrouwde hulpservers een stuk performanter is dan de constructies tot nog toe beschreven. Het is natuurlijk zo dat de veronderstelling van 2 vertrouwde hulpservers het schema niet meer volledig homomorf maakt in de strikte zin van het woord, vermits bij recryptie een (partiële) private sleutel vereist is. Deze nieuwe constructie leidt wel tot een praktisch haalbare oplossing voor volledig homomorfe encryptie. Een overzicht van dit document wordt getoond in figuur 1.2. Het moet de lezer gidsen doorheen de hoofdstukken van deze thesis.
5
1. Inleiding
Figuur 1.2: Blokdiagram dat de relaties tussen de hoofdstukken in deze masterproef toont.
6
Hoofdstuk
Homomorfe encryptie et doel van dit hoofdstuk is om een algemeen kader te schetsen omtrent homomorfe (encryptie)schema’s. Dit hoofdstuk moet een kapstok vormen waaraan de volgende hoofdstukken kunnen worden opgehangen. De bedoeling is dan ook om de lezer de rode draad doorheen de verschillende volledig homomorfe schema’s, beschreven in de hierop volgende hoofdstukken, aan te reiken. Dit hoofdstuk kan als dusdanig beschouwd worden als een inleiding bij elk homomorf schema. Er wordt hier dan ook niets nieuws voorgesteld.
H
2.1
Overzicht
In dit hoofdstuk wordt een algemene inleiding in verband met volledig homomorfe encryptie gegeven; een cryptosysteem dat toelaat een willekeurig circuit te evalueren op data waarvan slechts de cijfertekst bekend is, zonder deze te moeten ontcijferen. Dit hoofdstuk bevat een samenvatting van de grote lijnen en ideeën die teruggevonden worden in de doctoraalscriptie van Gentry [Gen09a]. Hierin beschrijft Gentry hoe 3 algemeen toepasbare stappen een volledig homomorf schema kunnen opleveren, we geven ze hier alvast even mee. In een eerste stap wordt een initieel homomorf schema opgesteld; een schema dat toelaat circuits te evalueren van een beperkte complexiteit. Dit schema kan op zich praktisch gebruikt worden als het te evalueren circuit beperkt is in complexiteit, i.e. de som van een beperkt aantal getallen bepalen, maar is op zich nog niet volledig homomorf. In de laatste stap is het de bedoeling dat het initiële schema zijn eigen geaugmenteerde decryptiecircuit kan evalueren. We zeggen dan dat het schema bootstrappable is. Praktisch betekent dit dat we in staat zijn een nieuwe encryptie van een cijfertekst homomorf te berekenen (wat met recryptie wordt aangeduid) plus 1 extra universele poort. De procedure Recrypt wordt aan het schema toegevoegd, hierna tonen we aan dat het schema met dit algoritme volledig homomorf wordt. We zoeken dus een decryptiefunctie die zo eenvoudig mogelijk is. In de tweede stap wordt dan ook het decryptiecircuit gesquashed, wat zoveel betekent als het decryptiecircuit aan te passen zodat het minder complex wordt. Dit wordt gerealiseerd 7
2
2. Homomorfe encryptie door een deel van de ontcijfering te laten plaatsvinden bij encryptie met behulp van een hint omtrent de private sleutel. De concrete constructie van Gentry is in meer detail beschreven in [Gen09a], hierin werd een initieel schema gekozen gebaseerd op ideale roosters. Een samenvatting van Gentry’s thesis is ook beschreven in het artikel [Gen09b]. Het belangrijkste element beschreven in [Gen09a] is echter de manier (de 3 stappen) waarop men een initieel homomorf schema volledig homomorf maakt, deze methode is de rode draad doorheen alle tot op heden bekende volledig homomorfe schema’s.
2.2
Homomorfe encryptie
De notie van volledig homomorfe encryptie, is geïntroduceerd door Rivest, Adleman en Dertouzos in [RAD78] als privacy homomorphism. Het RSA schema was een van de eerste encryptieschema’s met een homomorfe eigenschap; i.e. gegeven de publieke sleutel pk = (N, e) en de cijferteksten {ψi ← πie mod N }, kan een multiplicatief circuit (slechts bestaande uit multiplicatoren) worden Q Q geëvalueerd als i ψi = ( i πi )e mod N , een cijfertekst die tot het product van de klaarteksten {πi } ontcijferd. Een homomorf publieke sleutel schema E heeft 4 algoritmes, de gebruikelijke KeyGenE , EncE , DecE en een extra algoritme EvaluateE dat als invoer de publieke sleutel heeft, een circuit C uit een verzameling van toegelaten circuits CE en een vector van cijferteksten Ψ = (ψ1 , . . . , ψt ), en als uitvoer een cijfertekst ψ heeft. De computationele complexiteit van deze 4 algoritmes moet een polynoom zijn in de veiligheidsparameter λ en in het geval van EvaluateE in de grootte van C. Definitie 2.2.1 (Correctheid van een homomorf schema). Een schema E is correct voor circuits uit CE , als voor elk sleutelpaar (pk, sk) gegenereerd met KeyGenE , voor alle klaarteksten π1 , . . . , π2 , voor alle circuits C ∈ CE en voor alle cijferteksten ψ1 , . . . , ψt met ψi ← EncE (pk, πi ) het zo is dat : ψ ← EvaluateE (pk, C, Ψ) ⇒ C(π1 , . . . , πt ) = DecE (sk, ψ). Om triviale schema’s uit te sluiten is het eisen van correctheid an sich niet voldoende, daarom eisen we dat de grootte van de cijfertekst en de decryptietijd naar boven begrensd zijn door een veelterm in de veiligheidsparameter λ, onafhankelijk van de grootte van C. Dit om schema’s te vermijden waarbij Evaluate(pk, C, Ψ) = (C, Ψ) en waarbij Dec de componenten van Ψ ontcijferd en toepast op C. Definitie 2.2.2 (Homomorfe encryptie). E is homomorf voor de circuits in CE als E correct is en DecryptE kan worden uitgedrukt als een circuit met grootte poly(λ). We spreken dus reeds van homomorfe encryptie als er slechts een beperkte verzameling circuits CE bestaat die het schema homomorf kan evalueren. In het geval van het RSA schema is CE de verzameling van alle multiplicatieve circuits. Definitie 2.2.3 (Volledig homomorfe encryptie). E is volledig homomorf als het homomorf is voor alle circuits. 8
2.3. Bootstrappable encryptie Hier zoeken we naar schema’s die naast correct ook nog semantisch veilig zijn tegen een gekozen-klaartekstaanval. Het is ook zo dat schema’s die homomorf zijn per definitie niet veilig zijn tegen gekozen-cijfertekstaanvallen (CCA2). In de volgende sectie wordt een zeer belangrijk concept, bootstrappability besproken. Deze eigenschap van een cryptosysteem zal verder cruciaal blijken om een volledig homomorf schema te verkrijgen.
2.3
Bootstrappable encryptie
Om bootstrappable te zijn moet E niet alleen in staat zijn om zijn eigen decryptiecircuit te evalueren, wat er op zich voor zorgt dat E cijfertekst homomorf kan hersleutelen, maar ook geaugmenteerde versies van zijn decryptiecircuit, zodat na recryptie vooruitgang kan worden gemaakt doorheen het te evalueren circuit. Definitie 2.3.1 (Geaugmenteerd decryptiecircuit). Laat Γ de verzameling zijn van alle poorten met ingangen en uitgang in de klaartekstruimte P inclusief de eenheidspoort. Voor poort g ∈ Γ bestaat het g-geaugmenteerd decryptiecircuit uit een g-poort die verschillende kopieën van DecE verbindt, waar DecE als ingang de private sleutel en de cijfertekst aanvaard geformatteerd als elementen uit de klaartekstruimte P l(λ) . We noteren de verzameling van g-geaugmenteerde decryptiecircuits, g ∈ Γ, als DE (Γ). We kunnen nu definiëren wat een bootstrappable homomorf circuit is. Het blijkt dat alle homomorfe schema’s die bootstrappable zijn ook volledig homomorf kunnen gemaakt worden. Definitie 2.3.2 (Bootstrappable encryptie). Zij CE de verzameling van circuits waarvoor E homomorf is. We zeggen dat E bootstrappable is met betrekking tot Γ als DE (Γ) ⊆ CE . We kunnen nu van de bootstrappability eigenschap gebruik maken om een willekeurig circuit te gaan evalueren. Zij E een bootstrappable schema met betrekking tot de poorten van Γ. We kunnen nu E gebruiken om het schema E new := (KeyGenE new , EncE new , EvaluateE new , DecE new ) te definiëren dat alle circuit kan evalueren, zie ook figuur 2.1. KeyGenE new (λ) Heeft als invoer een veiligheidsparameter λ, deze parameter duidt erop dat het minstens 2λ tijd duurt om het schema te breken. Voor l = l(λ) geldt nu (sk, pk) := KeyGenE (λ), skj
:= EncE (pk, skj ),
j ∈ [1, l],
waarbij sk1 , . . . , skl de voorstelling is van de geheime sleutel als elementen in de klaartekst ruimte P. De private sleutel van E new is dan sknew := sk en de nieuwe publieke sleutel pknew := (pk, skj ). 9
2. Homomorfe encryptie
Figuur 2.1: Een Nand-geaugmenteerd decryptiecircuit, waarbij met Enc een encryptie bedoeld wordt van het initiële schema. Aangezien de Nand poort een universele poort is, is het duidelijk dat recursief herhalen van deze constructie doorheen een willekeurig circuit resulteert in een schema E new dat volledig homomorf is.
EncE new (pknew , π) Heeft als invoer een publieke sleutel pknew en een boodschap π ∈ P. De cijfertekst is dan ψ := EncE (pk, π). DecE new (sknew , ψ) Heeft als invoer de private sleutel sknew en een cijfertekst ψ versleuteld met de bijhorende publieke sleutel. De uitvoer is π := DecE (sk, ψ). EvaluateE new (pknew , C, Ψδ ) Heeft als invoer de publieke sleutel pknew en een willekeurig circuit C met poorten uit Γ en de bijhorende versleutelde data waarop het circuit moet worden uitgevoerd. Men gaat hier als volgt te werk, elke poort g in het gegeven circuit C wordt vervangen door het g-geaugmenteerd decryptiecircuit waarbij de dataingang van het decryptiecircuit opnieuw wordt verbonden met dezelfde component als voorheen. Een voorbeeld is gegeven in figuur 2.1, dat het resultaat voorstelt van deze procedure voor een Nand circuit. Het bekomen geëxpandeerde circuit C new kan homomorf geëvalueerd worden met het initiële schema en correctheid volgt direct uit de bootstrappability eigenschap. Dit kan als volgt worden ingezien, elke poort wordt vervangen door een geaugmenteerd decryptiecircuit. Dit geaugmenteerde decryptiecircuit wordt, volgens de bootstrappability eigenschap, correct geëvalueerd. De uitvoer van de het geaugmenteerd decryptiecircuit is dus correct waardoor, wegens inductie, de correctheid van de gehele evaluatie volgt. Het besluit van deze sectie is dan ook dat we op zoek moeten gaan naar een initieel homomorf schema dat in staat is zijn eigen geaugmenteerd decryptiecircuit te evalueren. Daarbij zullen we dus vooral moeten kijken naar schema’s waarbij het ontcijferen een vrij eenvoudig circuit is en waarbij er tegelijkertijd een zo groot mogelijke verzameling CE homomorf kan worden geëvalueerd. In hoofdstuk 3 wordt gewerkt met initieel homomorf schema dat beschreven is door middel van getallenvelden. In hoofdstuk 4 wordt een schema voorgesteld dat beschreven wordt aan de hand van gehele getallen. Gentry zelf beschrijft een abstract 10
2.4. De squahing transformatie
Figuur 2.2: De squahing transformatie. Het initiële decryptiecircuit Dec wordt gesplitst in een computationeel intensief circuit Dec1 uitgevoerd zonder hulp van de private sleutel en een computationeel ondiep circuit Dec2 uitgevoerd met behulp van de private sleutel.
initieel schema aan de hand van ideale roosters. We tonen in hoofdstuk 3 aan dat de Smart-Vercauteren variant een concrete instantie is van deze abstracte constructie.
2.4
De squahing transformatie
De complexiteit van het decryptiecircuit van het initiële schema moet dus zo laag mogelijk gemaakt worden om enerzijds een bootstrappable initieel schema te hebben en anderzijds om de performantie van het afgeleide volledig homomorfe schema zo hoog mogelijk te maken. In [Gen09a] wordt deze transformatie van de decryptiefunctie squahing genoemd. De idee is dat het encryptieproces zijn eigen cijfertekst reeds voor een deel ontcijfert, maar dit zonder de directe hulp van de geheime sleutel, waardoor het decryptieproces logischerwijze minder complex wordt. De idee is in figuur 2.2 visueel uitgebeeld. Het encryptieproces start de decryptie van de cijfertekst Ψ met behulp van een hint over de private sleutel f (sk, r) (met r de willekeurige muntstukken van de functie f) die aan de publieke sleutel pk ∗ = (pk, f (sk, r)) werd toegevoegd. Hier wordt een extra veiligheidsonderstelling aangenomen, de publieke hint mag geen cruciale informatie lekken omtrent de private sleutel sk. De door de encryptiefunctie extra berekende informatie Ψ∗ wordt de squahing information genoemd. Het getransformeerde decryptiecircuit (Dec2 in figuur 2.2) aanvaardt de squahing information en een (gewijzigde) private sleutel sk∗ waarmee een decryptie kan worden uitgerekend. 11
2. Homomorfe encryptie In alle concrete varianten in deze thesis wordt de squahing transformatie uitgevoerd met behulp van een subset sum problem (SSSP). De extra veronderstelling die hier moet gemaakt worden is dat een aanvaller er niet in slaagt, om in tijd 2λ , de private sleutel af te leiden uit de extra informatie toegevoegd aan de publieke sleutel door de squahing transformatie, voor meer uitleg zie hoofdstuk 3 of 4.
2.5
Een praktische demonstratie
Om het vorige wat aannemelijker te maken, geven we hier een korte demonstratie van hoe een initieel homomorf schema willekeurige bewerkingen kan uitvoeren op data waarvan alleen de bijhorende cijferteksten beschikbaar zijn. Stel we hebben een initieel homomorf encryptieschema dat an sich alle tweedegraadsveeltermen homomorf kan evalueren en dat bootstrappable is, zodat we een Recrypt functie hebben. Stel dat we nu gevraagd worden om “a3 + b3 ” homomorf te evalueren met enkel de bijhorende cijferteksten, dan gaan we te werk zoals aangeven in demonstratie 2.1. Algorithm 2.1 Demonstratie van de Recrypt procedure 1: sk, pk := KeyGen(λ) 2: acijfertekst := Enc(a, sk) 3: bcijfertekst := Enc(b, sk) (2) 4: acijfertekst := Mult(a, a, pk) (2)
5:
bcijfertekst := Mult(b, b, pk)
6:
acijfertekst := Recrypt(a, skj , pk)
7:
bcijfertekst := Recrypt(b, skj , pk)
8:
acijfertekst := Mult(a, acijfertekst , pk)
9:
bcijfertekst := Mult(b, bcijfertekst , pk)
10:
(2)
(2)
(3)
(3)
(2)
(2)
(3)
(3)
Antwoord := Add(acijfertekst , bcijfertekst , pk)
Na stappen 4 en 5 moet een recryptieoperatie plaatsvinden, daar het gebruikte schema op zichzelf geen derdegraadsveeltermen kan evalueren. Na recryptie kan weer 1 extra operatie uitgevoerd worden (bootstrappability). Deze manier van werken kan toegepast worden om een willekeurige veelterm te evalueren !
12
Hoofdstuk
De Smart-Vercauteren variant n dit hoofdstuk wordt de Smart-Vercauteren variant op het algemene Gentry schema besproken, zie ook referentie [SV09]. De KeyGen procedure en een groot aantal optimalisaties worden beschreven in [GH10]. We werken in dit hoofdstuk hetzelfde schema uit als in [GH10], maar met een andere keuze voor het SSSP. Hierdoor moet het index-encoderingsmechanisme, zoals beschreven in [GH10], niet meer worden toegepast. Het aangepaste schema is hierdoor een stuk sneller dan de originele versie. Het grootste deel van de constructie zal beschreven worden gebruikmakend van getallenvelden. Gezien elk algebraïsch getal uit een getallenveld kan gezien worden als een vector in een rooster, kan de beschrijving ook gebeuren aan de hand van roosters, zoals in [GH10]. In dit hoofdstuk wordt hoofdzakelijk met getallenvelden gewerkt. Zoals aangegeven in hoofdstuk 2 starten we de volledig homomorfe constructie met een initieel homomorf schema, dat we nadien bootstrappable maken.
I
3.1
Het initiële homomorfe schema, abstract
Het initiële homomorfe encryptieschema bestaat uit 5 basisprocedures: KeyGen, Enc, Dec, Add en Mult. Hieronder beschrijven we abstract wat de verschillende procedures berekenen. 1. KeyGen procedure. De KeyGen procedure produceert een element γ = G(θ) in het getallenveld K gedefinieerd door de irreducibele veelterm F (x) ∈ Z[x] van graad N . Dit element genereert het hoofdideaal p = γ · Z[θ]. Een bijkomende eis is dat het ideaal p kan voorgesteld worden door twee elementen hδ1 , δ2 i. Dit kan door te eisen dat de hermite normal form (HNF) van de rotatiebasis van p een speciale vorm heeft. De twee element representatie wordt dan p = p · Z[θ] + (θ − α) · Z[θ], met G(α) = F (α) = 0 mod p en p de norm van γ in K. Het element γ is de private representatie van p, de twee element representatie is de publieke representatie van p. 13
3
3. De Smart-Vercauteren variant 2. Encrypt procedure. De Enc procedure veronderstelt hier de klaartekst m ∈ P = Z2 . De klaartekst m wordt opgeteld met een kleine even ruisterm R(x) wat een veelterm C(x) oplevert. De ∞-norm van R(x) is begrensd door de parameter µ. De ∞-norm van een veelterm R(x) is de absolute waarde van de coëfficiënt met maximale absolute waarde. Encryptie betekent dan de reductie van C(θ) mod p met de twee element voorstelling. Dit komt neer op het evalueren van C(x) mod p met x = α. Een cijfertekst van het SmartVercauteren is dus een geheel getal modulo p, met c = m + R(α) mod p, m.a.w de cijfertekstruimte is Zp . Als de ∞-norm van de bijhorende ruisterm R(x) op een cijfertekst c begrensd is door µ, dan zeggen we ook wel dat de ruis op de cijfertekst c begrensd is door µ. 3. Decrypt procedure. Door de definitie van de encryptieprocedure weten we dat C(θ) − c ∈ p. Daardoor is C(θ) − c = q(θ) · γ, met q(θ) ∈ Z[θ]. We zouden C(θ) terug willen recupereren, omdat we dan hebben m = C(θ) mod (2). We hebben dat γ −1 = Z(θ)/p. Dus vermenigvuldigen met γ −1 levert −c · Z(θ)/p = q(θ) − (C(θ) · Z(θ))/p. Als we nu hebben dat kC(θ) · Z(θ)k∞ < 1/2 dan kunnen we q(θ) berekenen door de coëfficiënten van −cγ −1 af te ronden naar het dichtstbijzijnde gehele getal. Dan is C(θ) = c + q(θ) · γ. 4. Add, Mult procedure. Hier sommeert of vermenigvuldigt men gewoon de 2 cijferteksten modulo p. Voor een positieve straal r, definiëren we hier eerst de ∞-bal rond de oorsprong: B∞,N (r) =
(N −1 X
) i
ai x : −r ≤ ai ≤ r .
i=0
Stel c1 en c2 zijn 2 cijferteksten met bijhorende C{1,2} (θ) = m{1,2} + R{1,2} (θ) en R{1,2} ∈ B∞,N (r{1,2} − 1), dan heeft de som Add(c1 , c2 , pk) als bijhorende veelterm C3 (θ) = (m1 + m2 ) + (R1 (θ) + R2 (θ)), en het product Mult(c1 , c2 , pk) C4 (θ) = (m1 · m2 ) + (R1 (θ) · m2 + R2 (θ) · m1 + R1 (θ) · R2 (θ)), met C3 (θ) ∈ B∞,N (r1 + r2 ) en C4 (θ) ∈ B∞,N (δ∞ · r1 · r2 ). Waarbij de factor δ∞ enkel afhankelijk is van het getallenveld, gekarakteriseerd door F (x), waarin wordt gewerkt. We definiëren de factor als kg(x) · h(x) mod F (x)k∞ = sup : Deg(g), Deg(h) < N . kg(x)k∞ · kh(x)k∞
δ∞ 14
3.2. Het initiële homomorfe schema, concreet Deze factor heeft een belangrijke invloed op de homomorfe capaciteiten van het initiële homomorfe schema. Dit kan als volgt worden verklaard, decryptie is correct zolang dat de ruis op een cijfertekst c tot de bal B∞,N (rdec ) behoort. Dus na een aantal Add en Mult operaties dreigt de ruis te groot te worden. Dit probleem wordt opgelost met de Recrypt operatie, zie figuur 3.1. In de volgende sectie bespreken we hoe dit abstracte schema concreet geïmplementeerd wordt. Een eerste praktische versie van dit schema werd gegeven in [GH10].
3.2
Het initiële homomorfe schema, concreet
In het concrete schema werken we in een getallenveld K gedefinieerd door de veelterm F (x) := xN + 1, met N een macht van 2. De veelterm F (x) ∈ Z[x] is altijd irreducibel over de gehele getallen. Deze specifieke keuze laat geoptimaliseerde procedures toe in vergelijking met een generieke irreducibele veelterm, ook de factor δ∞ = N is vrij gunstig in de zin dat de groei van δ∞ , in het slechtste geval, exponentieel kan zijn in N voor een generieke veelterm F (x).
De sleutelgeneratieprocedure, KeyGen(N, η) De KeyGen procedure heeft als invoer 2 parameters: • N . De graad van de veelterm F (x), en dus de dimensie van het getallenveld K waarmee het schema werkt. In de praktijk wordt verondersteld dat N een macht van 2 is. • η. De ∞-norm van de veelterm G(x), heeft een belangrijke invloed op de homomorfe diepte die het initiële schema zal kunnen aanbieden, zie sectie 3.4. De procedure zelf kan opgesplitst worden in 3 verschillende stappen: −1 i 1. Kies een willekeurige veelterm G(x) = N i=0 gi x . Hierbij kan men ook als extra voorwaarde opleggen dat G(x) mod (2) = 1, dit bewijst vooral zijn nut in de SIMD variant op dit schema, zie hoofdstuk 5.
P
2. Inverteer de veelterm Z(x) = G(x)−1 in de zin dat Z(x) · G(x) = p mod F (x), waarbij p de norm is van G(θ) in het getallenveld gedefinieërd door F (x). Men kan in het algemeen het extended algorithm of Euclides (XGCD) voor veeltermen aanwenden om Z(x) te bepalen. Dit kan echter efficiënter gebeuren met de fast Fourier transform (FFT) wanneer F (x) = xN + 1. Aangezien zal blijken dat we slechts Z(x) mod x2 nodig hebben kan er nog een efficiënter algoritme gebruikt worden. Dit algoritme, gebaseerd op een verdeel-en heersstrategie, wordt uitgebreid beschreven in [GH10]. 15
3. De Smart-Vercauteren variant 3. Hier wordt getest opdat de veelterm G(x) wel een ideaal J = (G(x)) oplevert met een HNF van de vorm : HNF(J) =
d −α −[α2 ]p −[α3 ]p .. .
0 1 0 0
0 0 1 0
0 0 0 1
··· ··· ··· ··· .. .
0 0 0 0 .. .
−[αN −1 ]p 0 0 0 · · · 1
.
Deze voorwaarde is equivalent aan de voorwaarde dat [GH10] ∃r ∈ Z : −r · Z(x) + x · Z(x) = 0
mod F (x)
mod p,
hierbij is r = α. Als F (x) = xN + 1 dan leidt bovenstaande voorwaarde tot
∀i = 1, · · · , N − 2 :
r · zi+1 = zi
mod p,
(3.1)
−r · z0 = zN −1
mod p,
(3.2)
PN −1
met Z(x) = i=0 zi xi . Als de gekozen veelterm G(x) nu niet voldoet aan de voorwaarden 3.1 en 3.2, kies dan een andere totdat aan de voorwaarde is voldaan. De volledige procedure is in pseudocode samengevat in algoritme 3.1. Algorithm 3.1 KeyGen(N, η) 1: 2: 3: 4: 5: 6: 7: 8: 9:
F (x) := xN + 1 repeat S(X) := B∞,N (η/2) G(X) := 1 + 2 · S(x) p := Norm(G(θ)) Z(x) := G(x)−1 mod F (x) α := coeff(Z(x) · x, 0) · coeff(Z(x), 0)−1 mod p until F (α) = G(α) = 0 mod p return sk = (p, z0 ), pk = (p, α)
Encryptieprocedure, Encrypt(m, pk, µ∗ ) De belangrijkste parameter in dit algoritme is µ∗ , die de ∞-norm van de ruis R(x) op de cijfertekst bepaalt, µ∗ wordt ook wel renc genoemd. Zoals gezegd is het resultaat van deze procedure een geheel getal modulo p. Ter volledigheid geven we een procedure in pseudocode in algoritme 3.2. In de eigenlijke implementatie was µ∗ steeds 2 en werd R(x) ook niet willekeurig uit B∞,N (µ∗ ) getrokken, voor meer informatie zie encryptie methode in [GH10]. 16
3.3. Verband met de algemene Gentry constructie Algorithm 3.2 Enc(m, pk, µ∗ ) Require: M ∈ P = Z2 1: Parse pk als (p, α) 2: R(x) := B∞,N (µ∗ /2) 3: C(x) := m + 2 · R(x) 4: c := C(α) mod p 5: return c
Decryptieprocedure, Decrypt(c, sk) Het decryptiealgoritme neemt een cijfertekst en de private sleutel sk als invoer. De correctheid van het algoritme is gegarandeerd als de term C(x), geassocieerd aan c, een element is van B∞,N (rdec ). Stelling 3.4.1 geeft aan wat deze decryptie straal rdec is in functie van de schema-parameters. Het waarom van de gelijkheid op regel 2 van algoritme 3.3 kan gevonden worden in [GH10]. Algorithm 3.3 Dec(c, sk) Require: C(x) ∈ B∞,N (rdec ) 1: Parse sk als (p, z0 ) 2: M := c − bc · z0 /pe = [c · z0 ]p mod 2 3: return M
3.3
Verband met de algemene Gentry constructie
In deze sectie geven we nog even het verband tussen de algemene Gentry constructie [Gen09b] en de Smart-Vercauteren variant. De analogie is gegeven in tabel 3.1. De ring waarin we werken is hier het getallenveld K gedefinieerd door de irreducibele veelterm F (x). Het kleine ideaal I is hier gegeven door het hoofdideaal (2), wat onder meer betekent dat de klaartekst M ∈ P = Z2 [x]/F . Merk op dat het schema hierboven beschreven P verder beperkt tot Z2 , een beperking die we zullen laten vallen in hoofdstuk 5. We kunnen ten eerste opmerken dat de sleutel groottes ook veel kleiner zijn dan in de algemene Gentry variant. Dit komt vooral doordat in het algemene schema de basissen BJpk en BJsk volle matrices zijn, dit in contrast met deze variant waarbij de publieke sleutel pk = (p, α) een paar gehele getallen is, en sk = γ −1 slechts 1 geheel getal. Ook kan er veel eenvoudiger worden gerekend in de ring Z[x]/(xN + 1) dan in een generische ring R. Doordat de wortels van F (x) = xN + 1 de nde -macht wortels zijn van 1, kan het FFT algoritme gebruikt worden bij het inverteren van de veelterm G(x). 17
3. De Smart-Vercauteren variant Algemene Gentry constructie Ring R Klein ideaal I Groot ideaal J Publieke basis BJpk Private basis BJsk Klaartekst P = R/I Samp(x, BI , R, BJ ) IdealGen(R, BI )
Smart-Vercauteren variant Getallenring K ∼ = Z[x]/(F (x)) Ideaal I = (2) Ideaal J = p HNF(J) Rotatiebasis (γ) P = Z2 deelveld van Z2 [x]/F C(x) = m + 2 · R(x) De KeyGen(N, η) procedure
Tabel 3.1: De link tussen de algemene Gentry constructie en de Smart-Vercauteren variant. Reductie met de HNF(J) kan hier echter zeer efficiënt gebeuren door C(x) mod p te evalueren in α. We werken in de praktijk ook altijd met F (x) = xN + 1, en we zorgen ervoor dat γ mod (2) = 1.
3.4
Hoe homomorf is het initiële schema ?
Het is nu interessant om na te gaan hoe homomorf deze initiële constructie juist is. We definiëren nu twee belangrijke afstanden die bepalen wat de complexiteit is van de circuits die homomorf kunnen worden geëvalueerd. Een visuele representatie van de afstanden is afgebeeld in figuur 3.1. We weten reeds dat voor een specifieke veelterm C(x) de decryptie correct zal zijn als kC(θ) · Z(θ)k∞ < 1/2. Stelling 3.4.1 geeft een relatie tussen de ∞-norm van C(x) en de correctheid van de decryptieprocedure. Stelling 3.4.1. Laat Z(x), G(x), α en p gedefinieerd zijn zoals in de sleutelgeneratiemethode. Als C(x) ∈ Z[x]/(F (x)) een veelterm is met kC(x)k∞ < rdec en de cijfertekst zoals in encryptieprocedure c = C(α) mod p dan c · Z(x) · G(x) C(x) = c − p
mod (F (x))
met rdec =
p . 2 · δ∞ · kZ(x)k∞
Het bewijs van deze stelling kan gevonden worden in [LMSV10], en wordt hier weggelaten. We kunnen dit combineren met stelling 3.4.2, we verkrijgen dan een uitdrukking voor rdec in functie van G(x) en F (x). Stelling 3.4.2. Laat F (x), G(x) ∈ Z[x] met F(x) een monische irreducibele veelterm van graad Deg(F ) = N en deg(G) = M en M < N en resultant(F, G) = p, dan bestaat er een veelterm Z(x) ∈ Z[x] met Z(x) · G(x) = p mod F (x) en −1 kZ(x)k∞ ≤ kG(x)kN · kF (x)kM 2 . 2
18
3.4. Hoe homomorf is het initiële schema ?
Figuur 3.1: Een schematische voorstelling van de parameters rdec , renc , rrec1 en rrec2 . Een nieuwe cijfertekst vertrekt altijd met een beginruis renc . Decryptie is correct wanneer de ruis begrensd is door rdec . Een recryptie is nodig als de ruis dreigt groter te worden dan rrec1 , recryptie brengt het ruisniveau terug naar rrec2 , zie sectie 3.6. De diepte op de horizontale as is een indicatie van het aantal operaties die reeds homomorf uitgevoerd zijn.
Het bewijs van deze stelling staat in [SV09], en wordt hier dus ook weggelaten. M Samen met p ' kG(x)kN 2 · kF (x)k2 krijgen we dan een benaderende uitdrukking voor het homomorf vermogen van het initiële schema in functie van de ringparameter δ∞ en de generator van het ideaal p.
rdec ' ' '
p , M 2 · δ∞ · kG(x)kN 2 · kF (x)k2 kG(x)k2 , 2 · δ∞ √ η· N . 2 · δ∞
In [GH10] toont men op een empirische wijze aan dat, als de circuitveelterm bestaat uit Npoly termen met een graad begrensd door deg, dan homomorfe evaluatie van het initiële schema mogelijk als 19
3. De Smart-Vercauteren variant
Figuur 3.2: Het recryptie circuit. Impliciet wordt er verondersteld dat de ruis op ingangswaarde beperkt is door rrec1 . We willen dat de ruis op het resultaat minder is dan de ruis op de invoer, rrec2 < rrec1 .
rdec ≈ η ≥ ndeg ·
q
Npoly ,
met n de Euclidische norm van de ruis op de cijfertekst c. We gebruiken deze gelijkheid verder in sectie 3.7.
3.5
Het volledig homomorfe schema
Aangezien we hebben aangetoond in sectie 3.3 dat dit schema een specialisatie is van het algemene schema hoeven we slechts de methode van Gentry toe te passen op dit speciaal geval. We kunnen de methode ietwat vereenvoudigen daar we hier werken met gehele getallen en niet met vectoren. We definiëren dus een nieuwe procedure Recrypt, die een cijfertekst aanvaardt als invoer en een nieuwe cijfertekst uitvoert van dezelfde onderliggende klaartekst boodschap. Zoals gezegd in hoofdstuk 2 tracht deze procedure de decryptieprocedure homomorf te evalueren. De bedoeling hiervan is natuurlijk om een cijfertekst met veel ruis te kunnen terugbrengen tot een cijfertekst met minder ruis, zonder dat de private sleutel sk vereist is. We zullen dus proberen de cijfertekst homomorf te ontcijferen, zoals gevisualiseerd in figuur 3.2. De decryptieoperatie wordt ook hier vereenvoudigd of gesquashed door het toevoegen van extra informatie over de private sleutel sk = (p, z0 ) van het initiële homomorfe schema. We verstoppen de geheime sleutel in een SSSP S−1 X
σi · Bi = z0
mod p.
(3.3)
i=0
Met σi ∈ {0, 1} en met een Hamming gewicht S−1 i=0 σi = s. De sleutels van het afgeleide volledig homomorfe schema worden dan gegeven door P
pk = (p, α, S, s, {ci = Enc(σi , pk), Bi }S−1 i=0 ), sk = (p). 20
3.5. Het volledig homomorfe schema Natuurlijk moeten we erop toekijken dat het toevoegen van de extra hint de veiligheid van het schema niet ondergraaft, zie sectie 3.7. De decryptieprocedure verandert in Dec(c, sk) =
"S−1 X
#
σi Bi
i=0
mod 2. p
We tonen hier aan dat de functie Dec(c, sk) kan worden uitgedrukt als een veelterm van lage graad in de bits van σi , wat vereist is in de Recrypt procedure (bootstrappability). We hebben "S−1 X
S−1 X
#
σi Bi
i=0
=
!
σi · Bi
i=0
p
&S−1 X
%
Bi −p· σi · . p i=0
Om nu Dec(c, sk) te bepalen reduceren we vorige vergelijking modulo 2, we hebben dan met yi = hc · Bi ip : S−1 M
Dec(c, sk) =
!
σi · hyi i2 ⊕ hpi2 ·
i=0 S−1 M
σi · hyi i2 ⊕
=
i=0
&*S−1 X
*&S−1 X
yi σi · p i=0
yi σi · p i=0
%+
,
(3.4)
2
+ %
.
(3.5)
2
Deze laatste gelijkheid volgt uit het feit dat p een oneven getal is. De eerste term uit vorige vergelijking is een veelterm van de eerste graad in de private bits σi . Het tweede gedeelte is wat moeilijker, de vraag is met hoeveel bits precisie er moet gewerkt worden opdat correct kan worden afgerond. Decryptie is correct zolang dat kC(θ) · Z(θ)k∞ < p/2, de afstand tussen de cijfertekst en het rooster J is dus kleiner dan p/2 in de ∞-norm. In dit homomorfe schema beschouwen we cijferteksten waarvoor de afstand tot het rooster in ∞-norm kleiner is dan p/(2(s + 1)). De afstand rrec1 is dus rdec /(s + 1), zie ook figuur 3.1. Laat pb de precisieparameter zijn, duidend op het aantal bits na de komma van zi . Laten we nu deze precisieparameter kiezen als pb := dlog2 (s + 1)e . Voor alle i is zi is de beste benadering van yi /p met pb -bits na de komma, we hebben dat zi − yi ≤ 2−(pb +1) . p
En meer in het bijzonder hebben we dan dat de totale ruis, welke bestaat uit de ruis op c en de extra ruis toegevoegd door het werken met slechts pb bits na de komma begrensd blijft tot ruis op c
z
}|
quantisatieruis
{
z
}|
{
p p p +s · ≤ . 2 (s + 1) 2 (s + 1) 2 21
3. De Smart-Vercauteren variant In dat geval hebben we natuurlijk dat er juist afgerond wordt en dus dat &S−1 X i=0
%
σi yi /p =
&S−1 X
%
σ i zi .
i=0
Wat ons een correcte decryptieprocedure oplevert. In de volgende subsecties bespreken we een aantal optimalisaties op deze basisprocedure.
Het optellen van de zi Het optellen van de getallen σi zi kan nu worden gedaan met behulp van een lage graad veelterm, gebruik makend van de grade school addition (GSA) methode, zie ook figuur 3.3. Zoals aangeleerd op de lagere school worden de bits van de vectoren σi zi onder elkaar geplaatst. Men begint met de uiterst rechtse kolom en berekent de som van deze kolom als een vector van bits, zie algoritme 3.4. De minst significante bit wordt gebruikt in de uiteindelijke som en de rest wordt als overdracht boven de nevenstaande kolommen geplaatst. Dit herhaalt men tot de eerste bit na de komma is berekend, aangezien alleen het resultaat modulo 2 ons interesseert. Het berekenen van het Hamming gewicht van een kolom steunt op theorema 3.5.1, en komt uit [SV09]. Een efficiënte implementatie, zie ook [SV09], voor het berekenen van deze symmetrische veeltermen is in pseudocode gegeven in algoritme 3.4. Stelling 3.5.1. De bits van het Hamming gewicht van een bit vector ~b = (b1 , . . . , bk ) worden gegeven door (SymPol2s−1 (b1 , . . . , bk ) , . . . , SymPol20 (b1 , . . . , bk ))
mod 2.
Algorithm 3.4 Berekenen van de bit representatie van het Hamming gewicht van ~b = (b1 , . . . , bk ). 1: s := blog2 (k)c + 1 2: S := 2s−1 3: (s1 , . . . , sS ) := (0, . . . , 0) 4: for i ∈ [1, . . . , k] do 5: for k ∈ [min(i, S), . . . , 2] do 6: sk := sk + sk−1 · bi 7: end for 8: end for 9: return (s2s−1 , s2s−2 , . . . , s20 ) mod 2 Een naïeve implementatie zou echter ongeveer S · s vermenigvuldigingen vereisen, door het feit dat er S termen zijn met precisie pb = dlog2 (s + 1)e. We geven hier een alternatief waarbij het aantal termen wordt teruggebracht naar s, in dit geval zullen slechts s2 vermenigvuldigingen vereist zijn, zie [GH10]. 22
3.5. Het volledig homomorfe schema
Figuur 3.3: Illustratie van de GSA methode. De bits binnen de grote rechthoek stellen de bits van qk voor, de bits boven deze rechthoek stellen de overdrachtbits voor en de bits in de donkere rechthoek zijn deze van de som. De overdracht en som bits worden berekend gebruikmakend van symmetrische veeltermen.
23
3. De Smart-Vercauteren variant We vertrekken van een lichtjes ander SSSP, we veronderstellen dat we s vectoren σ~i hebben elk met Hamming gewicht 1. Met andere woorden verdelen we het aantal 1 bits in ~σ over de verschillende σ~i . De verzameling B = {B0 , . . . , BS−1 } wordt nu s verschillende verzamelingen Bi . De bits in σ~i duiden we aan met σk,i en de elementen van Bi als Bk,i . We hebben dan, analoog aan vergelijking 3.3, de volgende gelijkheid s−1 X S−1 X
σk,i Bk,i = z0
mod p.
k=0 i=0
Het analoog van vergelijking 3.5 is dan qk z }| { + * s−1 S−1 M XX , Decrypt(σ~1 , . . . , ~σs ) = σk,i · hyk,i i2 ⊕ σ z k,i k,i k,i 2 k=0 i=0
(3.6)
waarbij yk,i := hcBk,i ip en zk,i de benadering met pb bits precisie van yk,i /p. Het is nu vrij eenvoudig in te zien dat qk kan berekend worden als de exclusive or (XOR) van de getallen σk,i zk,i voor alle i, door de simpele reden dat slechts 1 van de σk,i voor i ∈ [1, · · · , S] verschillend is van 0. Het probleem is dus teruggebracht tot het optellen van de qk met pb bits precisie.
3.6
Recryptieprocedure
Voor de volledigheid geven we hier nog eens de pseudocode van het volledige Recrypt algoritme zoals geïmplementeerd, zie algoritme 3.5. Algorithm 3.5 Recrypt(c, σpk , pk) 1: Initialisatie: pb := dlog2 (s + 1)e
2: Bereken de squashing informatie in de klaartekst ruimte : yk,i := cxk Ri p 3: Bereken zk,i , welke een benadering is van yk,i /d met pb bits precisie 4: Bereken de vector qk homomorf, zoals formule 3.6 aangeeft, met een XOR operatie Tel de getallen qk homomorf op, som := sk=1 qk , gebruik de GSA methode in combinatie met algoritme 3.4 6: Rond het getal som af, dit kan worden gedaan als de homomorfe additie van de 2 meest significante bits van som L 7: Bereken k,i σk,i · hyk,i i2 8: return Tel de berekende bit uit de twee vorige stappen homomorf op 5:
3.7
P
Veiligheidsanalyse en bepalen van de parameters
Ten eerste kan opgemerkt worden dat vermits dit schema een specialisatie is van het algemene Gentry schema, de analyse gegeven in [Gen09b] toegepast kan worden. 24
3.7. Veiligheidsanalyse en bepalen van de parameters Wel moet er opgelet worden dat vermits dit schema een specifieke instantie is van de algemene constructie, de veronderstellingen over willekeurige roosters hier dus niet strikt opgaan.
3.7.1
De parameters λ en µ
We definiëren 2 veiligheidsparameters λ en µ die alle andere parameters bepalen. De parameter λ bepaalt het veiligheidsniveau van het encryptieschema. Deze veiligheidsparameter wordt gekozen als λ = 72, m.a.w. noemen we het schema gebroken als er een aanvaller bestaat die het schema kan breken in tijd minder dan 272 . De parameter µ kwantificeert de exponentiële moeilijkheid van van het shortest vector problem (SVP) en het bounded distance decoding problem (BDDP) in de gebruikte roosters. Het duurt 2k tijd om een SVP of BDDP in een n-dimensionaal rooster te benaderen tot op een factor µn
2 k/log(k) , zie appendix A. In [GH10] wordt aangetoond dat uit praktische benaderingen in roosters van dimensie 100-400 volgt dat µ ≈ 0.11. We nemen voor µ de volgende parameter waarden µ = {0.15, 0.59, 2.39}, welke sterkere veronderstellingen zijn dan µ = 0.11. Deze drie parameterwaarden µ samen met λ = 72 zullen ons drie schema’s opleveren: (i) een klein schema (µ = 2.39), (ii) een middel schema (µ = 0.59) en (iii) een groot schema (µ = 0.15). Merk op dat alle schema’s hetzelfde veiligheidsniveau λ = 72 hebben, maar telkens voor een andere inschatting (µ) van de moeilijkheid van roosterreductie. Dezelfde redenering wordt gevolgd in [GH10].
3.7.2
Onomkeerbaarheid van encryptie
Hier proberen we de onderliggende boodschap te verkrijgen zonder de private sleutel te kennen. Het is duidelijk dat het probleem equivalent is aan een roosterreductieprobleem. Gegeven p en α, c ∈ Zp , zoek xi voor i ∈ [0, . . . , N − 1] zodat N −1 X
xi αi = c − k · p,
i=0
waarbij |xi | ≤ rEnc voor een geheel getal k. Dit probleem kan ingebed worden in een roosterreductieprobleem, beschouw het rooster gegeven door H = HNF(J). Dan is (k, −x1 , · · · , −xN −1 ) · H = (c − x0 , −x1 , · · · , −xN −1 ) De vector in het rechterlid ligt zeer dicht (minder dan renc in ∞-norm) tegen de vector (c, 0, · · · , 0). Dit probleem kan dus gereduceerd worden tot een closest vector problem (CVP). Maar het onderliggende rooster H is een zeer goed bestudeerd rooster in de computationele getaltheorie, en kan dus als moeilijk bestempeld worden. Men moet hier een CVP exact oplossen, in sectie 3.7.5 zullen we echter een CVP tegenkomen dat slechts benaderend moet worden opgelost. Een aanvaller zal er dus altijd beter aan doen het benaderend CVP in sectie 3.7.5 op te lossen. 25
3. De Smart-Vercauteren variant
3.7.3
Brutekrachtaanval op de ruis
We moeten natuurlijk voorkomen dat de aanvaller de ruisvector kan raden doordat de initiële ruis rEnc te beperkt is. We hebben initieel dat C(x) = M + 2 · R(x) ∈ B∞,N (µ∗ ). Het aantal veeltermen van deze vorm in B∞,N (µ∗ ) is meer dan (µ∗ + 1)N . Om te testen opdat R(x) de correcte ruisterm is kan men testen opdat c − 2 · R(α) ∈ {0, 1}
mod p.
In de implementatie was µ∗ steeds 2, zodat kR(x)k∞ = 1 en R(α) efficiënt kan gebeuren. Doordat N > 512 was deze aanval nooit een probleem.
3.7.4
Aanval op het SSSP
We kiezen in onze implementatie steeds s als een een macht van 2 min 1 zodat er een minimale precisie pb nodig is voor een zo hoog mogelijke veiligheid. We nemen hier s = 15, waardoor pb = 4 en er dus slechts met 5 bits per zk,i moet worden verder gerekend. De aanvaller heeft hier alleen een som-controleer orakel, waardoor de enige mogelijkheid om het probleem te breken een brutekrachtaanval wordt op het SSSP. Het aantal mogelijke oplossingen van het SSSP is dan S s , wat dus meer moet zijn dan wat mogelijk is om met een brutekrachtaanval na te gaan, we hebben dan S s ≥ 2λ .
(3.7)
In [vDGHV09, GH10] wordt verondersteld dat het SSSP nog steeds moet onbreekbaar zijn als de aanvaller het private getal z0 kent. In dat geval is een birthday attack mogelijk waardoor S ds/2e ≥ 2λ . Er moet ook voor gezorgd worden dat een roosterreductieaanval (SVP) op de matrix B niet mogelijk is, B=
B0,0 B0,1 .. .
1 1 ..
. 1
. Bs−1,S−1 1 −z0
p Maar de veronderstelling dat een aanvaller de private sleutel heeft lijkt ons te ver te gaan, daarom houden we in onze implementatie alleen rekening met voorwaarde 3.7. 26
3.7. Veiligheidsanalyse en bepalen van de parameters
3.7.5
Zoeken naar de private sleutel
De private sleutel afleiden uit de publieke sleutel is een instantie van het small principal ideal problem (SPIP). Het is een van de basisproblemen in de computationele getaltheorie en vormt de basis van eerdere cryptografische voorstellen zie bijvoorbeeld [BMM00]. Definitie 3.7.1 (Small principal ideal problem). Gegeven een hoofdideaal a in een twee element representatie, of een HNF representatie, bereken een kleine generator van het ideaal. Het probleem kan ook gezien worden als het zoeken naar een gereduceerde basis B van de publieke basis Bpk = HNF(J), waarmee decryptie op een cijfertekst met minimale ruis renc correct is, zie [GH10]. De correctheid is gegarandeerd wanneer C(x) in het fundamentele parallellepipedum, zie appendix A, van B ligt. Het komt er dus op aan een basis B te vinden met een fundamenteel parallellepipedum waarin de bol B∞,N (renc ) past. We weten echter dat er een basis Bsk bestaat waarin de bol B∞,N (rdec ) past. Hieruit besluiten we dat een basis B, die rdec /renc slechter is dan de Minkowski gereduceerde basis, nog steeds voldoende is om cijferteksten met ruis renc te ontcijferen. De basis B wordt gevonden door het zoeken naar een basis met vectoren die een oplossing zijn van het SVP tot op een factor γ = rdec /renc ≈ 2t . We hebben dus nodig dat de dimensie N zo is dat N≥
λt , µ log(λ)
zodanig dat reductiealgoritmen geen oplossing vinden binnen 2λ tijd.
3.7.6
De homomorfe diepte van het initiële schema
In deze sectie leiden we de veelterm af die homomorf geëvalueerd moet worden wanneer men een recryptieoperatie wil uitvoeren. P P De veelterm van de bit d k i σk,i zk,i c mod 2 in functie van de bits van qk , bevat 234 graad 15 termen, zie figuur 3.4. Nu is de veelterm van elke bit van qk een veelterm bestaande uit een som van S eentermen van graad 1. We hebben dus dat de veelterm van de finale bit een veelterm is van S 15 234 graad 15 eentermen. Nu is het zo dat het initieel homomorf schema deze veelterm plus 1 extra vermenigvuldiging moet kunnen homomorf evalueren. Het komt er dus op aan om het initieel schema zo te kiezen dat het in staat is om een veelterm met 268 S 30 graad 30 eentermen homomorf te evalueren. In [GH10] wordt empirisch aangetoond dat aan volgende voorwaarde moet voldaan zijn, zie ook sectie 3.4, rrec1 ≈ 2t−pb ≥ n30 ·
√
268 S 30 ,
met pb = 4 en S = 32 en waarbij n experimenteel bepaald werd als c ≈ 7, leidt dat tot t ≈ 197. Wij namen in de implementatie het ronde getal t = 210. 27
3. De Smart-Vercauteren variant
Figuur 3.4: Homomorfe diepte van de GSA methode. De cijfers in de vierkantjes geven de graad van de veelterm van de bit op die plaats, als functie van de ingangsbits, hier de bits van de vectoren qk . De bits binnen de grote rechthoek stellen de bits van qk voor, de bits boven deze rechthoek stellen de overdracht bits voor en de bits in de donkere rechthoek zijn deze van de som. De finale bit, welke wordt bepaald door de som af te ronden, bevindt zich uiterst links. Het aantal termen van graad 15 om de finale bit te berekenen is C115 C215 C415 C815 ≈ 234 , zie stippellijnen.
28
3.8. Implementatieresultaten
Klein Middel Groot
λ 72 72 72
µ 2.39 0.59 0.15
N 1024 4096 16384
t 210 210 210
(s, S) (15, 32) (15, 32) (15, 32)
R 2102 2381 2381
Tabel 3.2: De 3 schema’s op basis van een verschillende µ waarde. Merk op dat het veiligheidsniveau λ constant is, enkel de inschatting (µ) van een roosterreductieaanval is anders. De gekozen parameterwaarden zijn in overeenstemming met de voorwaarden opgesteld in deze sectie.
3.7.7
Samenvatting parameters
Aan de hand van de verschillende veiligheidsanalyses en voorwaarden op het initiële homomorfe schema stellen we nu volledig homomorfe schema’s voor die enkel verschillen in hun keuze van de parameter µ, zie ook sectie 3.7.1. De schema’s zijn samengevat in tabel 3.2. Merk op dat de schema parameters veel kleiner zijn dan de parameters terug te vinden in [GH10], dit doordat de onderstelling dat een aanvaller de private sleutel heeft is weggevallen en dat de index-encoderingsmechanisme van [GH10] hier niet is toegepast.
3.8
Implementatieresultaten
De implementatie van de algoritmen werd gedaan in de taal Magma, zie ook [BCP97]. We geven hier de tijdmetingen voor het schema met een veiligheidsniveau λ = 72 en de BDDP hardheid-parameters µ = {0.15, 0.59, 2.39}. De code werd uitgevoerd op machines met elk een Intel Xeon Quad core CPU (X7350) aan een kloksnelheid van 2.93GHz, met 8 GiB werkgeheugen, en met Debian GNU/Linux 6 als besturingssysteem. De verkregen tijdmetingen zijn onderhevig aan ruis maar de resultaten tussen verschillende testen toonden nooit meer dan 5% variatie. Om de resultaten wat overzichtelijker te maken geven we hier de belangrijkste bondig weer.
Klein Middel Groot
KeyGen [s] 29 402 7018
Enc [s] 0.04 0.29 1.92
Dec [s] 0.05 0.40 2.61
Recrypt [s] 5 39 216
|pk| [MiB] 40 479 6910
Geheugengebruik In praktische implementatie is natuurlijk de grote van het sleutelpaar (sk, pk) van belang. Om geen verwarring te creëren gebruiken we de eenheden zoals aangeraden door de NIST [NIS00]. We hebben dat de grootte van het sleutelpaar gegeven is door 29
3. De Smart-Vercauteren variant
|pk| ≈ |p| (N + s · (S + 1)) , |sk| ≈ |p| . Vermits de private sleutel verwaarloosbaar is qua geheugengebruik laten we ze in de implementatieresultaten achterwege. We merken op dat de sleutelgrootte in het grote schema wel zeer groot wordt.
Tijdsgebruik Om het tijdsgebruik wat meer in detail te kunnen bediscussiëren geven we hier voor elk van de 3 schema’s een werklastverdeling mee. De KeyGen procedure wordt opgesplitst in (i) het berekenen van de inverse van G(x), (ii) het opstellen van het SSSP, (iii) het berekenen van de machten van α mod p en (iv) het berekenen van de versleuteling van de private bits σi . De Recrypt procedure wordt opgesplitst in het berekenen van (i) de squashing informatie, (ii) de getallen qk , (iii) het sommeren van qk met de GSA methode en (iv) de rest.
Het kleine schema, λ = 72 en µ = 2.39 N 1024 KeyGen
t 210
Enc Dec Recrypt
s S 15 32 totaal G(x)−1 SSSP i α : i ∈ [0, . . . , N − 1] Enc(σi , pk)
totaal yi , z i qk Ps k=1 qk bsume |p| 217887 [bit]
Geheugen
R 2102 28.61 [s] 01 % 02 % 31 % 66 % 0.04 [s] 0.05 [s] 4.97 [s] 03 % 01 % 96 % 00 % |pk| 39.4 [MiB]
Het middel schema, λ = 72 en µ = 0.59 N 4096 30
t 210
s 15
S 32
R 2381
3.8. Implementatieresultaten totaal G(x)−1 SSSP i α : i ∈ [0, . . . , N − 1] Enc(σi , pk)
KeyGen
Enc Dec Recrypt
totaal yi , zi qk Ps k=1 qk bsume |p| 875744 [bit]
Geheugen
401.75 [s] 01 % 02 % 63 % 33 % 0.29 [s] 0.40 [s] 38.89 [s] 03 % 00 % 97 % 00 % |pk| 479.3 [MiB]
Het grote schema, λ = 72 en µ = 0.15 N 16384 KeyGen
Enc Dec Recrypt
Geheugen
t 210
s S 15 32 totaal G(x)−1 SSSP i α : i ∈ [0, . . . , N − 1] Enc(σi , pk)
totaal yi , zi qk Ps k=1 qk bsume |p| 3519100 [bit]
R 2381 7017.61 [s] 00 % 00 % 86 % 13 % 1.92 [s] 2.61 [s] 216.00 [s] 03 % 00 % 97 % 00 % |pk| 6.91 [GiB]
Discussie Uit de implementaties blijkt dat in de KeyGen procedure de berekening van αi het grootste deel van het werk opeist. Ook de grootte van de publieke sleutel is voor een groot deel bepaald door αi . In [GH10] wordt een iets gesofisticeerdere manier van werken voorgesteld waarbij er met minder dan N getallen wordt gewerkt. Hoewel dit de sleutelgeneratie performanter maakt en de publieke sleutel kleiner maakt, heeft dit nadelige gevolgen voor de tijdsefficiëntie van de Encrypt procedure. Uit de tijdmetingen blijkt dat de GSA procedure het grootste deel van het werk in de Recrypt procedure opeist. Het verschil met deze vaststelling en de resultaten gepubliceerd in [GH10] worden verklaard door het feit dat het SSSP in hun geval 31
3. De Smart-Vercauteren variant anders werd gekozen, zodat in [GH10] gebruik moest gemaakt worden van een indexencoderingsmechanisme. Het wegvallen van dit mechanisme maakt het schema veel sneller.
Resultaten bondig samengevat Het voorgestelde schema is sterk gebaseerd op het schema voorgesteld in [GH10]. Maar de schemaparameters worden opnieuw afgeleid voor een andere keuze van het SSSP en het weglaten van het index-encoderingsmechanisme. Dit doordat hier niet wordt verondersteld dat het SSSP veilig moet zijn in het geval dat een aanvaller in het bezit is van de private sleutel. Deze vreemde veronderstelling wordt ook verworpen in [SV11]. Hierdoor kan het SSSP een stuk kleiner worden gemaakt en is er geen nood aan het index-encoderingsmechanisme. Voor verdere informatie zie sectie 3.7. Het schema wordt geïmplementeerd en opgemeten in de Magma programmeertaal, de resultaten worden samengevat in sectie 3.8. Door de verschillende keuze van het SSSP en het weglaten van het index-encoderingsmechanisme wordt het schema ongeveer 5 maal sneller. Verder in de tekst zal dit schema vergeleken worden met de DGHV variant (hoofdstuk 4) en de SIMD (hoofdstuk 5) variant. Wel kan opgemerkt worden dat uit de tijdmetingen blijkt dat homomorfe encryptie een tijdrovende eigenschap is. Daarom ook dat in hoofdstuk 6 een pragmatische oplossing wordt aangeboden voor dit probleem.
32
Hoofdstuk
De DGHV variant n dit hoofdstuk wordt een tweede variant besproken op het algemene Gentry schema. Deze variant vertrekt echter wel van een iets ander initieel homomorf schema. Waar de Smart-Vercauteren variant meer een specifieke instantie is van het algemene Gentry schema kan dit schema een volwaardige variant genoemd worden. We werken in dit hoofdstuk hetzelfde schema uit als in [vDGHV09], maar met een andere keuze voor het SSSP. Hierdoor moet het index-encoderingsmechanisme, zoals gebruikt in [vDGHV09], niet meer worden toegepast. Het grote verschilpunt met het schema beschreven in [vDGHV09] is dat de veiligheidsanalyse wordt compatibel gemaakt met de analyse gegeven in hoofdstuk 3, dit om een eerlijke vergelijking van beide schema’s mogelijk te maken. Het aangepaste schema is hierdoor een stuk sneller dan de originele versie, om gelijkaardige redenen als in hoofdstuk 3. Deze variant is vanuit wiskundig oogpunt iets makkelijker te beschrijven omdat hier alleen met gehele getallen wordt gewerkt. Zoals aangegeven in hoofdstuk 2 starten we ook hier de volledig homomorfe constructie met een initieel homomorf schema, dat we nadien bootstrappable maken.
I
4.1
Het initiële homomorfe schema
De bedoeling van deze constructie is dat we enkel werken met gehele getallen om een initieel homomorf schema op te stellen. Stel dat er een privaat geheel getal p is gedefinieerd en dat het formaat van de cijfertekst voldoet aan c = m + 2 · (p · q + r)
mod x0 ,
(4.1)
met x0 = p · q0 een publiek geheel getal en de ruisterm |2 · r| < p/2 = rdec . De term R = 2 · r zullen we de ruisterm op de cijfertekst c noemen. Doordat p een deler is van x0 kunnen we ook zeggen dat c=m+2·r
mod p. 33
4
4. De DGHV variant Doordat de ruis beperkt is kan met behulp van de private informatie p de boodschap m gerecupereerd worden als m = [c]p mod 2. De encryptieprocedure is gebaseerd op een verzameling van publieke gehele getallen xi , met xi = pqi + ri ,
1 ≤ i ≤ τ,
waarbij de bedoeling van de ruisterm ri is een aanvaller verhinderen om de private sleutel p af te leiden uit de publieke sleutel als de greatest common divisor (GCD) tussen twee verschillende xi . In het volgende deel van deze sectie bespreken we hoe de net besproken ideeën concreet worden geïmplementeerd.
Encryptieprocedure, Encrypt(m, pk) De encryptie van een boodschap m volgens het formaat 4.1 kan met behulp van de publieke getallen xi gevonden worden als c = m + 2r + 2
X
xi
mod x0 ,
i∈S
met S een willekeurige deelverzameling van {1, . . . , τ } met slechts s elementen. We 0 0 hebben ook dat r ∈ (−2ρ , 2ρ ). Modulo p wordt bovenstaande vergelijking dan c = m + 2(
X
ri + r)
mod p,
i∈S
P
waardoor de ruis op een cijfertekst c in deze methode dus gelijk is aan R = 2( i∈S ri + r). Het mag ook duidelijk zijn dat x0 een oneven getal is, anders is het schema natuurlijk niet veilig, daar de boodschap m dan altijd kan gevonden worden als c mod 2. De encryptie procedure is nog eens in pseudocode samengevat in algoritme 4.1. Merk op, dat ook nu weer een cijfertekst een geheel getal is, in Zx0 . Algorithm 4.1 Enc(m, pk) Require: m ∈ {0, 1} P 1: c := m + 2r + 2 i∈S xi mod x0 2: return c
De sleutelgeneratieprocedure, KeyGen(η, τ, γ, ρ) De sleutelgeneratieprocedure moet het privaat getal p bepalen en ook het publieke getal x0 . Om encryptie toe te laten zonder p te kennen wordt ook de verzameling xi toegevoegd aan de publieke sleutel. De KeyGen procedure heeft als invoer de volgende parameters: • η: De lengte van de private sleutel p in bits, heeft een belangrijke invloed op de homomorfe capaciteiten van het initiële schema sinds rdec = p/2. 34
4.1. Het initiële homomorfe schema • τ : Het aantal publieke gehele getallen xi = pqi + ri . • γ: Bepaalt de grootte van de gehele getallen qi ∈ [0, 2γ /p). • ρ: De grootte van de ruis ri ∈ (−2ρ , 2ρ ). De procedure is in pseudocode samengevat in algoritme 4.2. Algorithm 4.2 KeyGen(η, τ, γ, ρ) 1: p := 2η−1 + 2 · Random(0, 2η−2 − 1) + 1 2: q0 := 2 · Random(0, 2γ−η−1 ) + 1 3: x0 := p · q0 4: for all i ∈ [1, τ ] do 5: xi := p · Random(0, 2γ−η ) + Random(−2ρ + 1, 2ρ − 1) 6: end for 7: return sk = p, pk = (x0 , x1 , · · · , xτ )
Ontcijfer procedure, Decrypt(sk, c) De decryptie van een cijfertekst is nu gedefinieerd zoals aangegeven in algoritme 4.3. We hebben nu natuurlijk dat, c = m + 2(
X
ri + r)
mod p,
i∈S
waaruit volgt dat decryptie werkt zolang dat −p/2 ≤ m + 2( i∈S ri + r) < p/2. We definiëren hier dan ook op een gelijkaardige manier zoals in hoofdstuk 3 de afstand rdec = p/2, welke de decryptiestraal voorstelt. P
Algorithm 4.3 Dec(c, sk) 1: m := [c]p mod 2 2: return m
Homomorfe operaties, Add(c1 , c2 , pk) en Mult(c1 , c2 , pk) Additie en vermenigvuldiging zijn gelijkaardig aan de homomorfe operaties in het Smart-Vercauteren schema, de cijferteksten worden gewoon modulo x0 opgeteld of vermenigvuldigd. Correctheid volgt onmiddellijk uit het formaat van de cijferteksten, zoals gedefinieerd in vergelijking 4.1. We noteren c ∈ B(d) als de ruis R op de cijfertekst c = m + R mod p beperkt is tot |R| ≤ d. Als c1 ∈ B(d1 − 1), wat zoveel betekent als −d1 < m1 + 2R1 < d1 modulo p, en c2 ∈ B(d2 − 1) dan zal c1 ⊕ c2 ∈ B(d1 + d2 ),
(4.2)
c1 ⊗ c2 ∈ B(d1 · d2 ).
(4.3) 35
4. De DGHV variant Hierbij kan opgemerkt worden dat in dit schema de factor δ∞ , zoals gedefinieerd in hoofdstuk 3, dus steeds 1 is. Dit wil zeggen dat de ruis hier minder snel groeit in functie van de circuitdiepte als in het Smart-Vercauteren schema. Decryptie is ook hier correct zolang dat de ruis op een cijfertekst c tot de bal B(rdec ) behoort. Dus na een aantal Add en Mult operaties dreigt de ruis te groot te worden. Dit probleem wordt opgelost met de Recrypt operatie, zie figuur 3.1.
Reduceren van de publieke sleutel We veronderstelden dat we τ publieke gehele getallen xi hadden die gegenereerd werden zoals aangegeven in de KeyGen procedure 4.2. Een eerste aanpassing aan deze initiële constructie is dat we slechts een klein aantal xi zullen genereren en dat het multiplicatief combineren van deze getallen de volledige publieke sleutel zal opleveren. We genereren α paren (xi,0 , xi,1 ) op dezelfde manier als aangegeven in algoritme 4.2. We leiden uit deze paren 2α gehele getallen xu af op de volgende manier xu =
α Y
xi,ui
mod x0 ,
0 ≤ u < 2α ,
i=1
waarbij u = (u1 , . . . , uα ) de binaire voorstelling is van een geheel getal tussen 0 en 2α − 1. De parameter α neemt dus de rol over van τ en encryptie wijzigt lichtjes naar c = m + 2r + 2
X
xu
mod x0 ,
u∈S
met S een willekeurige deelverzameling van s elementen uit {0, . . . , 2α − 1} en r zoals voorheen. Deze reductie heeft natuurlijk zijn implicaties op de grootte van de term ru = xu mod p van de getallen xu . De bitlengte van ri = xi mod p is begrensd door ρ, maar doordat elk publiek getal xu nu wordt gegenereerd door het vermenigvuldigen van α getallen xi hebben we dat de bitlengte van de term ru ten hoogste αρ is.
4.2
Het volledig homomorfe schema
Zoals in hoofdstuk 3 zullen we hier weer een recryptieprocedure voorstellen die ons in staat stelt de ruis op een cijfertekst homomorf te reduceren. Het zal blijken dat het Recrypt circuit weinig verschilt van het circuit voor de Smart-Vercauteren variant. Ook hier verstoppen we de geheime sleutel in een SSSP, waarbij de som van het SSSP de inverse van het private getal p is, S−1 X
σi Bi = b2κ /pe mod 2κ+1 ,
i=0
met σi ∈ {0, 1} en met een Hamming gewicht s. De sleutels van het afgeleide volledig homomorfe schema worden dus gegeven door 36
4.2. Het volledig homomorfe schema
pk = (xi,ui , x0 , {ci = Enc(σi , sk), Bi }S−1 i=0 ), sk = (p), waarbij met “Enc(σi , sk)” encryptie verondersteld wordt met behulp van de private sleutel sk, Enc(m, sk) := m + 2 · Random(−2ρ , 2ρ ) + 2 · Random(−2γ−η , 2γ−η ) · p, waardoor de ruis op de versleutelde private bits σi kleiner is dan de ruis op een cijfertekst versleuteld met behulp van het publieke encryptiealgoritme, zie vorige hP i S σ y sectie. We definiëren nu yi = Bi /2κ en merken op dat = 1/p − ∆p met i=0 i i 2
∆p ≤ 2−κ−1 . De decryptieprocedure verandert in Dec(c, sk) = c −
&S−1 X
%
σi cyi
mod 2.
i=0
De squahing information in dit schema is dan yi en zi = [cyi ]2 , waarbij we slechts pb bits precisie na de komma bijhouden. We kiezen, net zoals in hoofdstuk 3, de precisie parameter pb := dlog2 (s + 1)e. Het decryptie circuit kan dan geschreven worden als Dec(c, sk) = c −
&S−1 X
%
σ i zi
mod 2.
i=0
En ook hier passen we de optimalisaties toe zoals aangegeven in hoofdstuk 3. We krijgen dan met een aangepast SSSP het volgende decryptiecircuit qk }| { z s−1 X X S−1 Dec(c, sk) = c − σk,i zk,i k=0 i=0
mod 2.
Aangezien het recryptie circuit zeer analoog is aan het circuit van het SmartVercauteren schema gaan we hier niet opnieuw in op de vraag hoe de bovenstaande vergelijking homomorf kan worden geëvalueerd, voor meer uitleg zie sectie 3.6.
Correctheid van de recryptie procedure We moeten nu nog nagaan of dat de recryptie procedure correct is voor alle mogelijke toegelaten cijferteksten c en private bits σi . Om de notatie wat te vereenvoudigen vertrekken we hier van het SSSP zonder optimalisatie. Het bewijs met optimalisatie is volledig analoog, we gaan dus na of dat 37
4. De DGHV variant
Figuur 4.1: Een schematische voorstelling van de parameters in de recryptie procedure. We weten dat het schema correct is wanneer de ruis |R| kleiner is dan p/2, immers dan wordt c/p correct afgerond met m = c − dc/pc mod 2. De grootheid c/p ligt dan niet verder dan 1/2 van een geheel getal, zie bovenste interval. We eisen echter in de recryptieprocedure dat de ruis kleiner is dan rrec1 wat een c/p oplevert ergens in het onderste interval. Als de fout geïntroduceerd door ∆p en ∆z nu kleiner is dan de ruimte tussen het bovenste en onderste interval dan is de recryptieprocedure steeds correct.
c−
&S−1 X
%
σi zi = [c]p
mod 2.
i=0
Dit kan door te eisen dat &S−1 X
%
σi zi = dc/pc
mod 2,
i=0
wat zich in onze situatie vertaalt in volgende ongelijkheid, zie figuur 4.1, fout(κ,pb ) }| { z " # S−1 X σi zi ≤ 1/2. rrec1 /p + c/p − i=0 2
Als we bovenstaande voorwaarde verder uitwerken komt dit neer op volgende voorwaarde S−1 X σi ∆zi ≤ 1/2, rrec1 /p + c · ∆p + i=0
waarbij we ∆p en ∆zi als volgt definiëren 38
4.3. Veiligheidsanalyse en bepalen van de parameters
S−1 X
σi yi = 1/p − ∆p ,
|∆p | ≤ 2−κ−1 ,
zi = [yi c]2 + ∆zi ,
|∆zi | ≤ 2−pb −1 .
i=0
We hebben een bovengrens voor |c · ∆p | < |2γ−1 · 2−κ−1 |. Een bovengrens voor PS−1 i=0 σi ∆zi is s · ∆z , we hebben dan dat s < 1/2, rrec1 /p + 2−2+(η−κ) + 2(s + 1)
We beperken rrec1 = p/2 · 0.5/(s + 1), dit betekent dat rrec1 = rdec /(2(s + 1)). Met deze keuze hebben we nu dat 0.25η−κ < 0.25/(s + 1). Met s = 15 volgt hier direct uit dat κ = η + 4.
4.3
Veiligheidsanalyse en bepalen van de parameters
We definiëren 2 veiligheidsparameters λ en µ die alle andere parameters bepalen. De parameter λ bepaalt het veiligheidsniveau van het encryptie schema. Deze veiligheidsparameter wordt gekozen als λ = 72, m.a.w. noemen we het schema gebroken als er een aanvaller bestaat die het schema kan breken in tijd minder dan 272 . De parameter µ kwantificeert de exponentiële moeilijkheid van van het SVP en het BDDP in de gebruikte roosters. Het duurt 2k tijd om een SVP of BDDP in een n-dimensionaal rooster te benaderen tot op een factor µn
2 k/log(k) , zie appendix A. In [GH10] wordt aangetoond dat uit praktische benaderingen in roosters van dimensie 100-400 volgt dat µ ≈ 0.11. We nemen voor µ de volgende parameter waarden µ = {0.15, 0.59, 2.39}, welke sterkere veronderstellingen zijn dan µ = 0.11. Deze drie parameterwaarden µ samen met λ = 72 zullen ons drie schema’s opleveren: (i) een klein schema (µ = 2.39), (ii) een middel schema (µ = 0.59) en (iii) een groot schema (µ = 0.15). Merk op dat alle schema’s hetzelfde veiligheidsniveau λ = 72 hebben, maar telkens voor een andere inschatting (µ) van de moeilijkheid van roosterreductie. Dezelfde redenering wordt gevolgd in [GH10].
4.3.1
Onomkeerbaarheid van encryptie
In dit schema is de cijfertekst gegeneerd door middel van een ijle deelsom van de P publieke getallen xi , c = m + 2r + 2 u∈S xu mod x0 . In wat volgt veronderstellen we dat r = 0, wat het de aanvaller alleen maar eenvoudiger maakt. We beschouwen het volgende rooster gedefinieerd door de rijen van 39
4. De DGHV variant
L=
2 2 ..
.
2x1 2x2 .. .
. 2 2xτ x0
1 1 ... 1
c
De vector (±1, . . . , ±1, 0) is vanzelfsprekend een vector in het rooster met een norm √ τ . De Minkowski bovengrens op de kortste vector doet ons vermoeden dat de norm van de op een na kortste vector een norm heeft van ≈ (Vol(L))1/τ ≈ 2γ/τ . We kunnen er dus vrij zeker van zijn dat de oplossing van het SVP in L een manier biedt om de boodschap m te recupereren. De kortste vector wordt gevonden wanneer we een SVP benaderend oplossen met een benaderingsfactor kleiner dan λ2 (L) ≈ 2γ/τ , λ1 (L) waarbij λ1 (L) en λ2 (L) de norm van de kortste en op een na kortste lineair onafhankelijke vector in het rooster L. Dit leidt ons tot de conclusie dat τ2 ≥
γ·λ , µ log(λ)
moet zijn opdat deze aanval faalt. Natuurlijk moet een brutekrachtaanval op de encryptie procedure niet aantrekkelijk zijn, de aanvaller zou een birthday attack kunnen uitvoeren tegen de ijle deelverzameling om zo te achterhalen welke xi gebruikt zijn in de encryptie van een cijfertekst c. De tijdscomplexiteit van deze aanval is τ s/2 en moet dus groter zijn dan 2λ . Deze voorwaarde vertaalt zich in deze implementatie in s λ ≥ , 2 α met τ = 2α .
4.3.2
Brutekrachtaanval op de ruis
We moeten natuurlijk voorkomen dat de aanvaller de ruisterm op een publiek getal xi kan raden doordat de ruisterm ri te beperkt is. Gegeven is dat x0 = p · q0 en x1 = q1 · p + r1 met |r1 | < 2ρ . De aanvaller kan proberen de ruisterm r1 te raden en de private sleutel te recupereren door p = GCD(x0 , x1 − r1 ) te berekenen. De aanval vereist gemiddeld 2ρ berekeningen van de GCD, daarom eisen we dat ρ ≥ λ. 40
4.3. Veiligheidsanalyse en bepalen van de parameters
4.3.3
Aanval op het SSSP
We kiezen in onze implementatie steeds s als een een macht van 2 min 1 zodat er een minimale precisie nodig is voor een zo hoog mogelijke veiligheid. We nemen hier s = 15, waardoor pb = 4 en er dus slechts met 5 bits per zk,i moet worden verder gerekend. De aanvaller heeft hier alleen een som-controleer orakel, waardoor de enige mogelijkheid om het probleem te breken een brutekrachtaanval wordt op het SSSP. Het aantal mogelijke oplossingen van het SSSP is dan S s , wat dus meer moet zijn dan wat mogelijk is om met een brutekrachtaanval na te gaan, we hebben dan S s ≥ 2λ .
(4.4)
In [vDGHV09, GH10] wordt verondersteld dat het SSSP nog steeds onbreekbaar moet zijn zelfs in het geval dat de aanvaller het private getal p kent. In dat geval is een birthday attack mogelijk waardoor S ds/2e ≥ 2λ . Er moet ook voor gezorgd worden dat een roosterreductieaanval (SVP) op de matrix B niet mogelijk is,
B0,0 B0,1 .. .
1 1
B=
..
.
. 1 Bs−1,S−1 1 −b2κ /pe
2κ+1
De analyse is hier volledig analoog aan de analyse van de roosteraanval besproken in 4.3.1. Maar de veronderstelling dat een aanvaller de private sleutel heeft lijkt ons te ver te gaan, daarom houden we in onze implementatie alleen rekening met voorwaarde 4.4.
4.3.4
Zoeken naar de private sleutel
De private sleutel afleiden uit de publieke sleutel is een instantie van het benaderend grootste gemene deler probleem. Een aanval gebaseerd op rooster reductie gaat als volgt, beschouw de publieke getallen xi = p · qi + ri ,
1≤i≤τ
en x0 = q0 · p. We beschouwen nu de eerste t getallen xi en een vector u die orthogonaal staat ten opzichte van de eerste t getallen van xi , met andere woorden t X
ui · xi = 0
mod x0 .
i=1
41
4. De DGHV variant Dit geeft ti=1 ui · ri = 0 mod p en als de ruistermen ri voldoende klein zijn geldt vorige gelijkheid over Z. Door het verzamelen van voldoende orthogonale vectoren u kan men de ruistermen ri bepalen en via de GCD ook de private sleutel p. In wat volgt veronderstellen we het schema gebroken als we minstens 1 zo’n vector u kunnen bepalen. Om u te vinden beschouwen we het rooster bestaande uit de rijen van de volgende matrix P
L=
1 1 ..
.
−x1 /xt · x0 −x2 /xt · x0 .. .
. 1 −xt−1 /xt · x0
x0 waarin elke rij orthogonaal staat op de vector x = (x1 , . . . , xt ), en waarin we dus P korte vectoren zoeken zodat ti=1 ui · ri = 0 mod p geldt over de gehele getallen. De Minkowski bovengrens op de kortste vector doet√ons vermoeden dat de norm van de kortste vector in L een norm heeft die ongeveer t · Vol(L)1/t ≈ 2γ/t . De voorwaarde P kuk∞ ≤ 2η−ρ < 2η is een nodige voorwaarde opdat ti=1 ui · ri = 0 mod p geldt over de gehele getallen. Als we nu de Minkowski bovengrens combineren met vorige voorwaarde krijgen we dat t > γ/η. Met t zo gekozen dat t > γ/η mogen we dus een benaderingsfactor van het SVP hebben die kleiner is dan de verhouding tussen de bovengrens op kuk∞ < 2η en de Minkowski bovengrens ≈ 2γ/η . Om de analyse hier te vereenvoudigen nemen we een zwakkere voorwaarde voor de benaderingsfactor, die nu slechts kleiner moet zijn dan 2η in plaats van 2η−γ/η . Gecombineerd met het feit dat de kleinste approximatie µt factor die we in tijd 2λ kunnen krijgen 2 λ/ log(λ) is geeft dit ons een grens op γ γ≥
η2 · λ . µ log(λ)
In [vDGHV09] worden nog een aantal aanvallen besproken tegen het benaderend grootste gemene deler probleem, maar deze blijken ook allen te falen met onze keuze van schema parameters.
4.3.5
De homomorfe diepte van het initiële schema
Eenzelfde redenering als die hoofdstuk in 3 leidt ons tot de conclusie dat de veelterm van het GSA circuit een graad heeft gelijk aan 15 en waarin er ≈ 234 eentermen zijn van deze graad in de bits van qk , zie figuur 3.4. Nu is natuurlijk de veelterm van elke bit van qk een veelterm, bestaande uit een som van S eentermen van graad 1. We hebben dus dat de veelterm van de finale bit een veelterm is van S 15 234 graad 15 eentermen in de bits van σk,i . Om bootstrappable te zijn moet het initiële schema nog 1 extra vermenigvuldiging homomorf kunnen evalueren. Het komt er dus op aan om het initieel schema zo te 42
4.4. Implementatieresultaten
Klein Middel Groot
λ 72 72 72
µ 2.39 0.59 0.15
α 11 11 11
ρ 72 72 72
η 2500 2500 2500
γ ×106 27.7 112.3 441.8
(s, S) (15, 32) (15, 32) (15, 32)
Tabel 4.1: De 3 schema’s op basis van een verschillende µ waarde, de gekozen parameterwaarden zijn in overeenstemming met de voorwaarden opgesteld in deze sectie.
kiezen dat het in staat is om een veelterm met 268 S 30 graad 30 eentermen homomorf te evalueren. Met 2ρ de ruis op de private bits σk,i en η de bitlengte van de private sleutel p kunnen we stellen dat het initiële schema homomorf wordt als 268 · S 30 · 2ρ·30 < rrec1 ≈ 2η−pb −1 .
4.3.6
Samenvatting parameters
Net zoals in hoofdstuk 3 stellen we nu 3 schema’s voor waarvoor de parameters samengevat zijn in tabel 4.1. Deze parameters zijn zo gekozen dat ze voldoen aan alle voorwaarden gepresenteerd in deze sectie. In de implementatie hebben we ook ρ0 = 0 verondersteld omdat deze parameter niet veel bijdraagt aan de veiligheid van het schema, dit in tegenstelling tot de implementatie in [vDGHV09] waar men ρ0 = 2λ neemt. Dit heeft echter geen invloed op de implementatieresultaten.
4.4
Implementatieresultaten
De implementatie van de algoritmen werd gedaan in de taal Magma, zie ook [BCP97]. We geven hier de tijdmetingen voor het schema met een veiligheidsniveau λ = 72 en de BDDP hardheidsparameters µ = {0.15, 0.59, 2.39}. De code werd uitgevoerd op machines met elk een Intel Xeon Quad core CPU (X7350) aan een kloksnelheid van 2.93GHz, met 8 GiB werkgeheugen, en met Debian GNU/Linux 6 als besturingssysteem. De verkregen tijdmetingen zijn onderhevig aan ruis maar de resultaten tussen verschillende testen toonden nooit meer dan 5% variatie. Om de resultaten wat overzichtelijker te maken geven we hier reeds de belangrijkste bondig weer.
Klein Middel Groot
KeyGen [s] 39 161 649
Enc [s] 773 4283 21912
Dec [s] 0.14 0.65 2.85
Recrypt [s] 3680 20243 95228
|pk| [GiB] 01.62 06.56 25.82 43
4. De DGHV variant
Geheugen gebruik In praktische implementatie is natuurlijk ook de grootte van het sleutelpaar (sk, pk) van belang. Om geen verwarring te creëren gebruiken we de eenheden zoals aangeraden door de NIST [NIS00]. We hebben dat de grootte van het sleutelpaar gegeven is door
|pk| ≈ (2α + s · S) γ, |sk| ≈ γ. Vermits de private sleutel verwaarloosbaar is qua geheugengebruik, laten we ze in de implementatieresultaten achterwege.
Tijdsgebruik Om het tijdsgebruik wat meer in detail te kunnen bediscussiëren geven we hier voor elk van de 3 schema’s een werklastverdeling mee. De KeyGen procedure wordt opgesplitst in (i) het opstellen van het SSSP, (ii) het berekenen van de versleuteling van de private bits σi en (iii) de rest. De Recrypt procedure wordt opgesplitst in het berekenen van (i) de squashing informatie, (ii) de getallen qk en (iii) het sommeren van qk met de GSA methode.
Het kleine schema, λ = 72 en µ = 2.39 α 11 KeyGen
ρ 72
Encrypt Decrypt Recrypt
η 2500 totaal SSSP Enc(σi , pk) andere
totaal yi , z i qk Ps k=1 qk |x0 | 27700000 [bit]
Geheugen
γ (s, S) 27.7 × 106 (15, 32) 38.95 [s] 20 % 76 % 04 % 772.67 [s] 0.14 [s] 3680.32 [s] 11 % 00 % 89 % |pk| 1.62 [GiB]
Het middel schema, λ = 72 en µ = 0.59 α 11 44
ρ 72
η 2500
γ 112.3 × 106
(s, S) (15, 32)
4.4. Implementatieresultaten totaal SSSP Enc(σi , pk) andere
KeyGen
Encrypt Decrypt Recrypt
totaal yi , zi qk Ps k=1 qk |x0 | 112300000 [bit]
Geheugen
161.49 [s] 19 % 77 % 04 % 4283.20 [s] 0.65 [s] 20243.41[s] 10 % 00 % 90 % |pk| 6.56 [GiB]
Het grote schema, λ = 72 en µ = 0.15 α 11 KeyGen
Encrypt Decrypt Recrypt
Geheugen
ρ 72
η 2500 totaal SSSP Enc(σi , pk) andere
totaal yi , zi qk Ps k=1 qk |x0 | 441800000 [bit]
γ (s, S) 6 441.8 × 10 (15, 32) 648.76 [s] 19 % 77 % 04 % 21912.21 [s] 2.85 [s] 95228.43 [s] 08 % 00 % 92 % |pk| 25.82 [GiB]
Discussie Uit de implementaties blijkt dat in de KeyGen procedure de berekening van de versleuteling van de private getallen σi het grootste deel van het werk opeist. Uit de tijdmetingen blijkt dat de GSA procedure het grootste deel van het werk in de Recrypt procedure voorstelt, net zoals bij het Smart-Vercauteren schema. Het verschil met deze vaststelling en de resultaten gepubliceerd in [vDGHV09] wordt verklaard door het feit zij hun parameters veel optimistischer hebben gekozen. Zelf zeggen zij hierover “The performance of the code including all optimizations are summarized in table 3, and are significantly better then then Gentry-Halevi (nvdr. Smart-Vercauteren) implementation of Gentry’s scheme, even though we use much more modest hardware , and most of the programming is done in a high-level language.” 45
4. De DGHV variant In realiteit echter worden de parameters in [vDGHV09] gekozen, vertaald naar onze manier van werken, in de veronderstelling dat µ ≈ 28, wat dus wel heel optimistisch is en niet compatibel met de keuze uit [GH10]. Het besluit van dit hoofdstuk is dan ook dan het DGHV schema bezwaarlijk performanter kan genoemd worden dan de Smart-Vercauteren variant. En dit zowel op vlak van tijdsefficiëntie als geheugengebruik.
Resultaten bondig samengevat Het voorgestelde schema is sterk gebaseerd op het schema voorgesteld in [vDGHV09]. Maar de schemaparameters worden opnieuw afgeleid voor een andere keuze van het SSSP en het weglaten van het index-encoderingsmechanisme, zie ook hoofdstuk 3. Ook worden alle veiligheidsonderstellingen opnieuw afgeleid op een manier die compatibel is met hoofdstuk 3, zodat een eerlijke vergelijking mogelijk is. Het schema wordt geïmplementeerd en opgemeten in de Magma programmeertaal, de resultaten worden samengevat in sectie 4.4. Uit deze analyse blijkt duidelijk dat het Smart-Vercauteren schema performanter is als dit DGHV schema, en dit op zowel het vlak van tijdsefficiëntie als geheugengebruik. De discrepantie tussen de opgemeten resultaten in deze thesis en de resultaten gepubliceerd in [vDGHV09] wordt toegewezen aan een oneerlijke vergelijking tussen de beide encryptieschema’s. Aangezien dit encryptieschema verder als inferieur wordt beschouwd, laten we een vergelijking met het SIMD encryptieschema in hoofdstuk 5 achterwege.
46
Hoofdstuk
De SIMD variant ezien het feit dat in de Smart-Vercauteren variant en de DGHV variant de recryptie van een boodschap computationeel zeer intensief is en gezien het feit dat de cijfertekstexpansie zeer groot kan zijn, stellen we in dit hoofdstuk een schema voor dat meerdere databits in 1 cijfertekst kan versleutelen. Dit schema zal ons onder meer toelaten om een vector van l bits te versleutelen en op deze datavector componentsgewijze operaties uit te voeren met enkel kennis van de cijferteksten. Dit type operaties worden ook SIMD operaties genoemd. Zo’n SIMD schema wordt bekomen door, bij het gebruik van het abstracte initiële schema uit hoofdstuk 3, een veelterm F (x) te gebruiken die modulo 2 splitst in verschillende irreducibele veeltermen van dezelfde graad, zodat er meerdere bits per bewerking kunnen worden behandeld. Meer in het bijzonder kiezen we voor F (x) een cyclotome veelterm. Bovendien laat een cyclotome veelterm ook bijna alle optimalisaties toe die werden gebruikt in de Smart-Vercauteren variant. We behandelen de verschillende manieren van recryptie besproken in [SV11] en stellen ook zelf een nieuwe manier van recryptie voor.
G
5.1
Inleiding
De bedoeling van deze variant is om in één enkele cijfertekst meerdere databits te kunnen versleutelen en hiermee ook te rekenen. Dit schema zou SIMD operaties moeten toelaten, een model waarbij een enkele operatie kan worden uitgevoerd op meerdere databits in parallel. In zowel het Smart-Vercauteren schema als het DHGV schema was de klaartekstruimte Z2 , een boodschap m heeft daar dus slechts 1 bit informatie. Hier willen we een schema met een klaartekstruimte van de vorm Zl2 , een boodschap m is dan een bitvector van lengte l. De Add en Mult operatie zullen dan, gegeven 2 cijferteksten en de publieke sleutel, een cijfertekst berekenen waarvan de onderliggende data de optelling of vermenigvuldiging (in Zl2 ) is van de data versleuteld in de gegeven cijferteksten. Een kleine demonstratie is gegeven in demo 5.1. Hierin onderstelden we l = 3, merk ook op dat in Z2 : “1 + 1 = 0”. In deze variant van het Smart-Vercauteren schema nemen we voor F (x) een cyclotome veelterm in plaats van F (x) = xN + 1. Dit vooral omdat deze keuze 47
5
5. De SIMD variant Algorithm 5.1 Demonstratie van SIMD operaties 1: sk, pk := KeyGen(λ) 2: c1 := Enc([1, 0, 1] , sk) 3: c2 := Enc([0, 1, 1] , sk) 4: csom := Add(c1 , c2 , pk) 5: cprod := Mult(c1 , c2 , pk) 6: [1, 1, 0] = Dec(csom , sk) 7: [0, 0, 1] = Dec(cprod , sk) alle optimalisaties behalve 1 toelaat zoals gebruikt wanneer F (x) = xN + 1. De 4 basisprocedures hoeven dus slechts minimaal aangepast te worden, en hebben asymptotisch eenzelfde efficiëntie. Praktisch blijkt de KeyGen methode wel wat trager. De grootste verandering met het Smart-Vercauteren schema is dat de klaartekstruimte van Z2 wijzigt in Z2 [x]/(F ). In de volgende sectie geven we wat wiskundige achtergrond om aan te geven wanneer en hoe een schema met klaartekst ruimte F2 [x]/(F ) aanleiding geeft tot een schema dat SIMD operaties ondersteunt.
5.2
Velden en homomorfismen
Stel F (x) ∈ F2 [x] is een monische irreducibele veelterm van graad N die in exact r verschillende factoren splitst van graad d = N/r F (x) :=
r Y
Fi (x).
i=1
A is de algebra gedefinieerd als A := F2 [x]/(F ), dan hebben we volgens het Chinese remainder theorem (CRT) de volgende natuurlijke isomorfismen A ∼ = F2 [x]/(F1 ) ⊗ · · · ⊗ F2 [x]/(Fr ) ∼ F d ⊗ · · · ⊗ F d. = 2
2
A is dus isomorf aan r kopieën van GF(2d ). We definiëren Li := F2 [x]/(Fi ) en merken op dat alle isomorf zijn aan elkaar en natuurlijk aan F2d , de isomorfismen worden gegeven door (
Λi,j :
Li → Lj , a(x) → a(ri,j (x))
waarbij ri,j (x) een vast nulpunt is van Fi in Lj , met andere woorden geldt er dat Fi (ri,j (x)) = 0
mod Fj .
Voor elke deler n van d zal het eindige veld Kn := F2n een deelveld zijn van Kd := F2d . We veronderstellen een vaste canonieke representatie van Kn door middel van een 48
5.2. Velden en homomorfismen canonieke irreducibele veelterm fn ∈ F2 [x] van graad n. Omdat Kn nu een deelveld is van alle Li , hebben we de homomorfismen van Kn naar Li (
φn,i :
Kn → Li , a(x) → a(sn,i (x))
waarbij voor sn,i (x) geldt dat fn (sn,i (x)) = 0
mod Fi .
We merken op dat de afbeeldingen φn,i en Λi,j beide lineair zijn in de coëfficiënten van de gegeven veelterm a(x) in respectievelijk Kn en Li . Als we nu deze homomorfismen combineren met het CRT, dan krijgen we het homomorfisme tussen l ≤ r kopieën van Kn en de algebra A via (
Γn,l :
Kln → A P , (k1 , . . . , kl ) → li=1 φn,i (ki ) · Hi · Gi
waarbij Hi = F/Fi en Gi = Hi−1 mod Fi . De verschillende morfismen worden nog eens gevisualiseerd in figuur 5.1.
Cyclotome veeltermen Een interessante specifieke irreducibele veelterm F (x) is de mde cyclotome veelterm Φm (x), gedefinieerd als Φm (x) :=
Y
(x − η),
η
waarbij η loopt over alle mde primitieve wortels van 1. We hebben dat deg(Φm (x)) = ϕ(m), met ϕ(m) de indicator of totiënt [SA64] van het geheel getal m. Men kan ook aantonen dat de veelterm Φm (x) irreducibel is over Z en dat Φm (x) ∈ Z[x]. Uit [SV11] weten we het volgende, als m oneven is dan splitst Φm (x) modulo 2 in r veeltermen van graad d. We hebben dat d het kleinste gehele getal is waarvoor geldt dat 2d = 1
mod m.
We hebben in tabel 5.1 de eigenschappen van Φm (x) samengevat voor een aantal interessante waarden m. We merkten tevens ook op dat de ∞-norm van Φm (x) voor m ≤ 40000 kleiner is dan 59. 49
5. De SIMD variant
Figuur 5.1: Een schematische voorstelling van de verschillende morfismen tussen A en de algebra Kln . Merk op dat wanneer l < r een aantal van de algebras Li in A steeds 0 als voorstelling voor Γn,l (Kln ) zullen hebben.
50
5.3. Het initiële homomorfe schema
5.3
Het initiële homomorfe schema
We vertrekken hier van hetzelfde initiële schema als datgene gebruikt in de SmartVercauteren variant. De idee is dat de algebra van de klaartekst, de klaartekstruimte P := F2 [x]/(F ), isomorf is met een algebra van de vorm P := F2 [x]/(F1 ) ⊗ · · · ⊗ F2 [x]/(Fr ), met Fi (x) verschillende irreducibele veeltermen van gelijke graad. We beperken daarom in dit schema de boodschappen m(x) niet langer tot Z2 maar laten boodschappen m(x) toe uit de volledige klaartekstruimte F2 [x]/(F ). Hierdoor is een operatie op een boodschap in de klaartekstalgebra P isomorf aan een SIMD operatie op r elementen in parallel uit de ruimte Kd zoals uitgelegd in de voorgaande sectie. Het is nu echter zo dat F (x) = xN + 1 niet splitst in verschillende irreducibele veeltermen sinds F (x) = xN + 1 = (x − 1)N
mod 2.
(5.1)
Het komt er dus op aan een irreducibele veelterm F te vinden die splitst in verschillende factoren van gelijke graad modulo 2. We nemen voor F de mde cyclotome veelterm Φm en we beschouwen m verder als een schema parameter. Alleen de KeyGen, Dec en Enc procedure verschillen van de gelijknamige procedures van het initiële schema voor het geval dat de veelterm F (x) = xN + 1 en de klaartekst ruimte P = Z2 (de Smart-Vercauteren variant).
De KeyGen procedure In de sleutelgeneratieprocedure is de computationeel intensiefste stap het inverteren van de veelterm G(x) modulo de veelterm F (x) = Φm (x), zie tijdmetingen van dit schema in sectie 5.6. We zullen om deze procedure te versnellen, gebruik maken van het feit dat de wortels van Φm (x) in C de mde machtswortels zijn van 1, xm + 1 = 0
mod Φm (x).
Het inverteren van de veelterm G(x) ∈ Z[x] kan als volgt worden gedaan: 1. Evalueer de veelterm G(x) in de nulpunten λi van de veelterm F (x) over C. 2. Bereken de discriminant p =
Q
i G(λi ).
3. Bereken Z(λi ) = p · G(λi )−1 over C. 4. Construeer de interpolerende veelterm Z(x) ∈ Z[x] doorheen de interpolatie punten Z(λi ). 51
5. De SIMD variant In het geval dat de veelterm F (x) = Φm (x) kan voor het evalueren en interpoleren respectievelijk de FFT en inverse fast Fourier transform (IFFT) met lengte m aangewend worden. Een algoritme in pseudocode is gegeven in algoritme 5.2. We berekenen in feite de inverse van G(x) over xm + 1 maar sinds Φm (x) een deler is van xm + 1 kunnen we het resultaat reduceren met Φm (x). De private sleutel van dit schema is nu de volledige veelterm Z(x). Algorithm 5.2 InvertPolynomial(G(x), m) 1: Z(λi ) := FFT(G(x), m) Qm−1 2: p = i=0 Z(λi ), waarbij GCD(i, m) = 1 voor de primitieve wortels. 3: Z(λi ) := p · G(λi )−1 4: Z(x) := IFFT(Z(λi ), m) 5: return Z(x) mod Φm (x)
De Encrypt procedure De Enc procedure verandert, maar niet fundamenteel. Een cijfertekst is nu een geheel getal van de vorm c = m(α) + R(α)
mod p,
wat dus zeer gelijkaardig is aan de vorm zoals voorgesteld in hoofdstuk 3. Ook hier weer is een cijfertekst een geheel getal modulo p. Ter volledigheid geven we hier ook het encryptiealgoritme in pseudocode mee, zie algoritme 5.3. Algorithm 5.3 Enc(m, pk, µ∗ ) Require: M ∈ P = Z2 [x]/F (x) 1: Parse pk als (p, α) 2: R(x) := B∞,N (µ∗ /2) 3: C(x) := m(x) + 2 · R(x) 4: c := C(α) mod p 5: return c Verder definiëren we hier een nieuw soort notatie. Zoals reeds gedefinieerd staat c = [m]pk voor het feit dat m de boodschap is onder de cijfertekst c. We kunnen nu in dit SIMD schema schrijven dat c = [m(x)]pk , de data onder de cijfertekst c is de veelterm m(x). Of dankzij het homomorfisme c = [m] ~ pk , met m ~ ∈ Kln . Een voorbeeld is [1]pk = [1, 1, · · · , 1]pk .
De Decrypt procedure De decryptieprocedure moet natuurlijk aangepast worden sinds de klaartekstruimte is gewijzigd. Als we ervoor zorgen dat G(x) mod (2) = 1, dan is ook Z(x) mod (2) = 1, zie [SV11]. Een argument gelijklopend aan wat Gentry gebruikt in sectie 6 in [GH10] geeft ons dat 52
5.4. Het volledig homomorfe schema
~ ×W +m [~c × W ]p = 2R ~ × W, met W de rotatie basis van Z(x), ~c = (c, 0, . . . , 0), R = (r0 , . . . , rN −1 ) en m = (m0 , . . . , mN −1 ). De vorige vergelijking modulo 2 levert ons direct de recryptieprocedure op, we hebben dat W mod 2 = I, zodat [~c × W ]p = m. ~ Componentsgewijs levert ons dit een praktische manier van decryptie op mi = [czi ]p
mod 2,
PN −1
−1 i met Z(x) = i=0 zi xi de private veelterm en m(x) = N i=0 mi x de boodschap. De recryptieprocedure kan dan vrij eenvoudig worden aangepast en wordt gegeven in algoritme 5.4.
P
Algorithm 5.4 Dec(c, sk) N −1 [czi ]p · xi mod 2 m(x) = i=0 2: return m(x)
1:
5.4
P
Het volledig homomorfe schema
De recryptieprocedure moet natuurlijk ook aangepast worden doordat de decryptieprocedure gewijzigd is. Doordat de klaartekstruimte nu veranderd is in F2 [x]/Φm (x) is de ruimte N := φ(m) keer groter geworden ten opzichte van Z2 . Het kan dus verwacht worden dat recryptie meer werk zal kosten. Het is echter de bedoeling in deze SIMD variant dat de recryptieprocedure sneller is dan N maal de recryptieprocedure van de Smart-Vercauteren variant! Anders kan men zich terecht afvragen wat de meerwaarde is van de SIMD operaties als werken met N Smart-Vercauteren schema’s even performant is. De eerste versie van de recryptieprocedure is naïef en in essentie niets anders dan N keer de recryptieprocedure van de Smart-Vercauteren variant. We hopen hieraan te verhelpen in de daaropvolgende versies van het recryptiealgoritme.
5.4.1
Recryptieprocedure, versie 1
In het algemeen is de klaartekst nu een veelterm m(x) van graad hoogstens N − 1. De coëfficiënten mi kunnen gevonden worden als mi := [c · zi ]p
mod 2.
Een nieuwe cijfertekst kan dan homomorf berekend worden als cnew :=
N −1 X
c¯i αi ,
i=0
53
5. De SIMD variant met c¯i = [mi ]pk voor i = 0, . . . , N − 1 de recrypties van de coëfficiënten van de onderliggende boodschap m(x). Het nadeel aan deze naïeve methode is dat ze in essentie sequentieel is, ze verreist het N maal aanroepen van de Recrypt methode zoals beschreven in hoofdstuk 3. Om slechts 1 SSSP te hebben voegen we aan de publieke sleutel de getallen wi = zi · z0−1 mod d toe, zodat zi = wi · z0 mod d. Een pseudocodeimplementatie is gegeven in algoritme 5.5, waarin met Recrypt het algoritme wordt bedoeld zoals beschreven in hoofdstuk 3. Algorithm 5.5 Recrypt_V1(c, σpk , pk) 1: cnew := 0 2: for i ∈ [0, . . . , N − 1] do 3: c¯i := Recrypt(c · wi , σpk , pk) 4: cnew := cnew + c¯i · αi mod p 5: end for 6: return cnew In deze vorm biedt deze SIMD variant natuurlijk niet bijster veel voordelen, hoewel de Add en Mult nu SIMD operaties zijn (zie demonstratie 5.1), zal dit de performantie niet sterk verbeteren. Doordat de recryptieprocedure een belangrijke invloed heeft op de performantie van een homomorf schema zullen we in wat volgt alternatieve procedures beschrijven waarin de recryptieprocedure (deels) parallel wordt uitgevoerd.
5.4.2
Recryptieprocedure, versie 2
De naïeve recryptieprocedure kan verbeterd worden door volgende vaststellingen 1. In sectie 5.2 over het homomorfisme tussen Kln en F2 [x]/Φm (x) lieten we de mogelijkheid om l < r en n een deler van d te kiezen. Het is dan duidelijk dat Γn,l (Kln ) slechts een deelveld is van F2 [x]/Φm (x). We proberen daarom een procedure op te stellen die slechts l · n < N Smart-Vercauteren recrypties vereist. 2. In een tweede stap proberen we de SIMD eigenschappen van het initiële schema te benutten om l bits in parallel te hersleutelen. We beginnen met het aanpassen van de naïeve methode voor het geval dat l · n < N . We proberen nu direct de coëfficiënten van de boodschap m(x) in de algebra Kln te hersleutelen. We zullen dit proberen door het homomorfisme Γ−1 n,l , l tussen F2 [x]/Φm (x) en Kn , homomorf uit te voeren. We herinneren ons dat de afbeelding Γn,l , zoals beschreven in sectie 5.2 , een vector van l binaire veeltermen (κ1 , . . . , κ2 ) van graad ten hoogste n − 1 afbeeldt in de algebra F2 [x]/Φm (x) op een element a(x) van graad ten hoogste N − 1. Hierbij kan opgemerkt worden dat de afbeelding lineair is in de coëfficiënten van de veeltermen 54
5.4. Het volledig homomorfe schema (κ1 , . . . , κ2 ), en dus kunnen de afbeeldingen Γn,l en Γ−1 n,l voorgesteld worden als matrixvermenigvuldigingen. (n·l,N ) We definiëren nu de volgende binaire matrix B ∈ F2 die de afbeelding Γ−1 n,l voorstelt, in de zin dat coeff(κi1 , i2 ) =
N −1 X
Bi1 +i2 ·n+1,k+1 · coeff(a(x), k),
k=0
waarbij i1 loopt van 0 tot l − 1 en i2 van 0 tot n − 1. In matrixnotatie wordt dit
~κ0 ~κ1 ~κ... ~κl−1
=B
a0 a1 a... aN −1
,
waarbij ai de coëfficiënten zijn van de veelterm a(x) en waarbij ~κi1 kolomvectoren zijn in Fn2 . De idee is nu om coëfficiënt i1 van component i2 uit Kln te hersleutelen door de afbeelding Γ−1 n,l homomorf uit te voeren. Hiermee kunnen we dan een volledige recryptie reconstrueren door cnew :=
n−1 l−1 X X
c¯i1 ,i2 · Γn,l (0, . . . , 0, Ψi1 , 0, . . . , 0)|α ,
i1 =0 i2 =0
met (0, . . . , 0, Ψi1 , 0, . . . , 0) ∈ Kln het element waarvoor de ide 2 -component gelijk is aan Ψi1 en de andere gelijk aan 0 en c¯i1 ,i2 de recryptie van coëfficiënt i1 van component i2 uit Kln . Met andere woorden, c¯i1 ,i2 = [0, . . . , 0, coeff(κi1 , i2 ), 0, . . . , 0]pk . We keren hier terug naar de vraag hoe we überhaupt een recryptie c¯i1 ,i2 kunnen berekenen. We weten door de definitie van de matrix B dat coeff(i1 , i2 ) =
N −1 X
Bi1 +i2 ·n+1,k+1 [c · zk ]p
mod 2.
k=0
Als we nu veronderstellen dat de afstand van de cijfertekst c tot het rooster J minder is dan 1/N keer de decryptiestraal rdec , dan is [c · zk ]p kleiner dan p/(2N ). We kunnen dan schrijven dat
coeff(i1 , i2 ) = cz0
X Rk+1 6=0
wk
mod 2,
p
met R de relevante rij van de matrix B. We hebben dus dat c¯i1 ,i2 een recryptie is met P de 1 bit Smart-Vercauteren variant met cijfertekst c∗i1 ,i2 = c · Rk+1 6=0 wk en met z0 als private sleutel. We vatten dit alles samen in algoritme 5.6. In de praktijk wordt γi1 ,i2 en Γn,l (0, . . . , 0, Ψi1 , 0, . . . , 0)|α mod p toegevoegd aan de publieke sleutel om recryptie te versnellen. 55
5. De SIMD variant Algorithm 5.6 Recrypt_V2(c, σpk , pk) 1: cnew := 0 2: for i2 ∈ [0, . . . , l − 1] do 3: for i1 ∈ [0, . . . , n − 1] do PN −1 Bi1 +i2 ·n+1,k+1 wk mod p 4: γi1 ,i2 = z0 · k=0 5: c¯i1 ,i2 := Recrypt(c · γi1 ,i2 , σpk , pk) 6: cnew = cnew + c¯i1 ,i2 · Γn,l (0, . . . , 0, Ψi1 , 0, . . . , 0)|α mod p 7: end for 8: end for 9: return cnew
5.4.3
Recryptieprocedure, versie 3
Zoals naar verwezen in sectie 5.4.2, zullen we hier proberen de SIMD capaciteiten van het initiële schema te benutten. Als we versies 1 en 2 beschouwen dan merken we op dat ze geen SIMD operaties gebruiken, de recrypties c¯i1 ,i2 bevatten elk slechts 1 bit informatie. Hierin zullen we verandering brengen door de recryptie cˆi1 te berekenen van de coëfficiënten i1 in alle l componenten van Kln . We hebben dan cˆi1 = [coeff(κ1 , i1 ), . . . , coeff(κl , i1 )]pk . Om de notatie wat te verlichten definiëren we hier de vector ~γ ~γ :=
N −1 X
!
mod p : i2 ∈ [0, . . . , l − 1] .
Bi1 +i2 ·n+1,k+1 wk
k=0
Om de recryptie cˆi1 te berekenen hebben we nodig dat
c∗
0 z}|{
cγ0 ·z0 p ∗ c1 z}|{ cˆi1 = cγ1 ·z0 p .. . ∗ c l−1 z }| {
cγl−1 ·z0
p
mod 2 mod 2
mod 2
,
pk
waarbij de vectornotatie van cˆi1 natuurlijk slaat op de voorstelling in Kln . We herinneren ons eraan dat [c∗i2 · z0 ]p mod 2, voor alle i2 ∈ [0, . . . , l − 1], wordt uitgerekend als (i )
z }| {+ * s−1 S−1 D E M XX (i ) (i ) 2 2 ∗ [ci2 · z0 ]p = σk,i · yk,i ⊕ σk,i zk,i 2 k,i 2 k=0 i=0
56
qk 2
mod 2,
5.4. Het volledig homomorfe schema (i )
h
met yk,i2 = c∗i2 · Bk,i
i
(i )
p
(i )
en zk,i2 = yk,i2 /p met pb bits nauwkeurigheid (voor alle
k ∈ [0, . . . , s − 1], i ∈ [0, . . . , S − 1] en i2 ∈ [0, . . . , n − 1]). Hier merken we op dat (i ) de berekening in elke component van cˆi1 dezelfde zijn, maar op andere data yk,i2 en (i )
zk,i2 . We zullen nu een schema geven waarbij de GSA methode slechts 1 keer zal moeten worden uitgevoerd in tegenstelling tot de l keer in versie 2, we zullen echter wel l verschillende encrypties van σk,i nodig hebben. Een methode die slechts 1 keer de GSA methode wil uitvoeren moet h
(0)
(l−1)
qksimd := qk , . . . , qk
i pk (d)
kunnen berekenen, waarna de GSA methode de getallen qk in alle l componenten simultaan zal optelllen. De berekening van qksimd kan eenvoudig gebeuren als we de private bits σk,i versleutelen in alle l componenten van Kln . We hebben dan dat qksimd :=
l−1 S−1 X X (i ) 2
(i )
σk,i · zk,i2
mod p,
i2 =0 i=0 (i )
met σk,i2 = [0, . . . , 0, σk,i , 0, . . . , 0]pk de versleuteling van σk,i in component i2 van Kln . De methode wordt ook in pseudocode beschreven in algoritmen 5.7 en 5.8. Algorithm 5.7 Recrypt_V3(c, ~σpk , pk) 1: cnew := 0 2: for i1 ∈ [0, . . . , n − 1] do (i ) 3: cˆi1 := RecryptP_V1(c · ~γ , σpk2 , pk, i1 ) 4: cnew := cnew + cˆi1 · Γn,l (Ψi1 , . . . , Ψi1 )|α mod d 5: end for 6: return cnew We geven hier aan wat de werklast is om y simd en qksimd te berekenen. Hiermee zullen we trachten de performantie resultaten te verklaren. Het berekenen van y simd vergt Ty3 ≈ l · s · S (T⊕ + Ty ) + l · T⊕ (i )
tijd, met T⊕ de tijd voor een additie in Zp en Ty de tijd om één getal van yk,i2 uit te rekenen. De tijd nodig om qksimd te berekenen is Tq3 ≈ s · l · (Tz + T⊕ ) · S · pb + pb · s · l · T⊕ , (i )
met Tz de tijd om één bit van één getal zk,i2 uit te rekenen.
5.4.4
Recryptieprocedure, versie 4 (nieuw) (i )
We stellen vast dat in versie 3 de private bits σpk2 zorgen voor een expansie van de grootte van de publieke sleutel pk met een factor ongeveer l. Er kan ook opgemerkt 57
5. De SIMD variant (i )
Algorithm 5.8 RecryptP_V1(c~∗ , σpk2 , pk, i1 ) Berekenen ~γ en c~∗ . 2: y simd := 0, qksimd := 0 3: for i2 ∈ [0, . . . , l − 1] do (i ) 4: yk,i2 := c∗i · Bk,i mod p 1:
(i )
5:
zk,i2 := yk,i /p met pb bits precisie.
6:
qk 2 :=
7:
y i2
8: 9: 10: 11: 12: 13:
(i )
:=
PS−1 (i2 ) i=0
Ps
(i )
σk,i · zk,i2
mod p
PS−1 (i2 ) D (i2 ) E
yk,i i=0 σk,i 2 (i ) qksimd + qk 2 mod p y simd + y (i2 ) mod p k=1
mod p
qksimd := y simd := end for Tel de getallen qksimd homomorf op met de GSA methode Rond de finale som af en tel hierbij y simd op return cˆi1
worden dat alleen de GSA methode in versie 3 van de recryptieprocedure gebruikmaakt van SIMD operaties. We proberen in deze versie hieraan te verhelpen door ook de squahing information voor te stellen in Kln , (0)
(l−1)
),
(0)
(l−1)
).
simd yk,i = (yk,i , . . . , yk,i simd zk,i = (zk,i , . . . , zk,i
Deze grootheden kunnen berekend worden als
simd yk,i
=
l−1 X (i2 )
yk,i · Γn,l (0, . . . , 0, 1, 0, . . . , 0) |α
mod p,
i2 =0 simd zk,i =
l−1 X (i2 )
zk,i · Γn,l (0, . . . , 0, 1, 0, . . . , 0) |α
mod p,
i2 =0
waarbij we ervan uitgaan dat de gehele getallen Γn,l (0, . . . , 0, 1, 0, . . . , 0) |α mod p in de sleutelgeneratiemethode worden berekend. simd en z simd berekend zijn, hebben we de squahing information in Kl , Nadat yk,i n k,i simd en z simd verder zoals in de 1-bit Smart-Vercauteren variant. en werken we met yk,i k,i Nadat we cˆi1 hebben bepaald met algoritme 5.9, kan een volledige recryptie van c gevonden worden zoals aangegeven in algoritme 5.7. We geven hier aan wat de werklast is om y simd en qksimd te berekenen. Hiermee zullen we trachten de performantieresultaten te verklaren. Het berekenen van y simd vergt 58
5.5. Veiligheidsanalyse en bepalen van de parameters Algorithm 5.9 RecryptP_V2(c~∗ , σpk , pk, i1 ) 1: Berekenen ~ γ en c~∗ . simd simd := 0 2: yk,i := 0, zk,i 3: for i2 ∈ [1, . . . , l] do (i ) 4: yk,i2 := c∗i2 · Bk,i mod p (i )
5:
zk,i2 := yk,i /p met pb bits precisie.
6:
simd := y simd + y 2 yk,i k,i k,i
7: 8: 9: 10: 11: 12: 13:
D
(i )
(i ) zk,i2
E 2
· Γ(0, . . . , 0, 1, 0, . . . , 0)|α mod p
simd := z simd + zk,i · Γ(0, . . . , 0, 1, 0, . . . , 0)|α mod p k,i end for P P simd mod p y simd := sk=1 S−1 i=0 σk,i · yk,i P S−1 simd mod p qksimd := i=0 σk,i · zk,i simd Tel de getallen qk homomorf op met de GSA methode Rond de finale som af en tel hierbij y simd op return cˆi1
Ty4 = l · s · S (T⊕ + Ty ) + s · S (T⊕ + T⊗ ) tijd, met T⊗ de tijd nodig voor een vermenigvuldiging in Zp en Ty de tijd om één (i ) getal van yk,i2 uit te rekenen. De hoeveelheid tijd nodig om qksimd te berekenen is Tq4 = s · S · (Tz + T⊕ ) · l · pb + s · S · (T⊕ + T⊗ ) pb , (i )
met Tz de tijd om één bit van één getal zk,i2 uit te rekenen. Vergelijken we deze resultaten nu met deze gegeven in versie 3 dan merken we op dat Ty4 − Ty3 = (s · S − l) T⊕ + s · S · T⊗ ,
(5.2)
Tz4
(5.3)
−
Tz3
= pb · s (S − l) T⊕ + pb · s · S · T⊗ .
We zien dus dat deze recryptieversie zeer aantrekkelijk wordt wanneer l ≥ S. In de praktijk echter blijkt dat er ook een performantievoordeel wordt gehaald uit het feit dat deze methode veel geheugenvriendelijker is, zie tabel 5.4.
5.5
Veiligheidsanalyse en bepalen van de parameters
Aangezien dit schema een specialisatie is van de Smart-Vercauteren variant met F (x) = Φm (x) verwijzen we naar sectie 3.7 in hoofdstuk 3 met N = φ(m) voor een veiligheidsanalyse. Naast de beperking dat de dimensie N van het rooster moet voldoen aan ϕ(m) = N ≥
λt , µ log(λ) 59
5. De SIMD variant m 7 31 85 127 585 341 819 511 1023 1285 1971 2255 4095 2047 4369 4681 5461 12483 8191 16383 29127 21845 31775 32767
deg(Φm (x)) 6 30 64 126 288 300 432 432 600 1024 1296 1600 1728 1936 4096 4500 5292 7776 8190 10584 15552 16384 24000 27000
kΦm (x)k∞ 1 1 1 1 2 1 2 1 2 1 1 2 4 1 1 1 1 1 1 1 4 2 2 2
r 2 6 8 18 24 30 36 48 60 64 72 80 144 176 256 300 378 432 630 756 864 1024 1200 1800
d 3 5 8 7 12 10 12 9 10 16 18 20 12 11 16 15 14 18 13 14 18 16 20 15
Tabel 5.1: Eigenschappen van Φm (x) en A := F2 [x]/Φm (x) voor optimale waarden van m voor 5 ≤ m ≤ 215 . De lijst is gesorteerd op deg(Φm (x)) en die waarden van m zijn opgenomen die resulteren in een maximale r voor een minimale graad van Φm (x).
proberen we nu m te kiezen zodat r, het aantal componenten van Krd , zo groot mogelijk is. Vermits de grootte van N een belangrijke invloed heeft op de performantie van het schema (hoe groter N , hoe trager het schema) willen we een zo groot mogelijke r voor een zo klein mogelijke N . We geven daarom in tabel 5.1 de waarden van 5 ≤ m ≤ 215 , gesorteerd op toenemende N , waarbij een maximale waarde r bereikt wordt.
5.5.1
De homomorfe diepte van het initiële schema
Het grootste deel van de analyse is hetzelfde als de analyse gegeven in de gelijknamige sectie in hoofdstuk 3. Het grootste verschil is dat homomorfe evaluatie van het homomorfisme Γ−1 n,l in rekening wordt gebracht. Ook de extra ruis door de bewerking 60
5.6. Implementatieresultaten m 127 585 511 1023 2255
l 18 24 48 60 80
t 380 380 380 380 380
S 32 32 32 32 32
s 15 15 15 15 15
Tabel 5.2: Een aantal schema’s met SIMD operaties, de gekozen parameterwaarden zijn niet in overeenstemming met de voorwaarden opgesteld in deze sectie.
i cnew := N i=0 c¯i α wordt in rekening gebracht, dit zorgt voor een expansie met een factor δ∞ N . Dit alles geeft ons volgende voorwaarde
P
√
1 N 2δ
∞
rrec1 > rrec2 ,
met rrec1 en rrec2 de waarden zoals tegengekomen in hoofdstuk 3. Wij namen in de implementatie het ronde getal t = 380, wat voldoende bleek voor m < 2047 in een empirische studie. Een aantal schema’s zijn gegeven in tabel 5.2. De reden waarom m niet groot genoeg werd genomen om veilig genoemd te kunnen worden, is de KeyGen methode die zeer traag is.
5.6
Implementatieresultaten
De implementatie van de algoritmen werd gedaan in de taal Magma, zie ook [BCP97]. De code werd uitgevoerd op machines met elk een Intel Xeon Quad core CPU (X7350) aan een kloksnelheid van 2.93GHz en 8 GiB werkgeheugen, en met Debian GNU/Linux 6 als besturingssysteem. De verkregen tijdmetingen zijn onderhevig aan ruis maar de resultaten tussen verschillende testen toonden nooit meer dan 5% variatie. We geven hier een tijdmeting voor alle versies van het recryptiealgoritme, behalve de naïeve recryptiemethode. De bedoeling van deze tijdmetingen is om het verschil in performantie te tonen tussen de verschillende recryptiemethoden. Door de zeer trage KeyGen methode kon de dimensie N = ϕ(m) niet groot worden genomen, zie tabel 5.6, wat de vergelijking met het Smart-Vercauteren en DGHV schema bemoeilijkt. De vergelijking met het Smart-Vercauteren en DGHV schema gebeurt hier door middel van geëxtrapoleerde tijdmetingen. We merken dan wel duidelijk op dat de parallelle formulering van de recryptieprocedure ons geen windeieren legt.
Werklastverdeling van recryptie met versies 2, 3 en 4 Om de performantie van de verschillende recryptieversies te kunnen begrijpen, splitsen we de tijdmetingen voor een particuliere verzameling waarden op volgens de grote stappen binnen de recryptieprocedures, zie tabel 5.3. De opsplitsing van de Recrypt methode is dezelfde als in hoofdstuk 3. 61
5. De SIMD variant m l 1023 60 Recrypt (i ) (i ) (1) yi,k2 , zi,k2 (i )
(2) qk 2 (3) GSA (4) som totaal [s]
n 1 v2 03%
t 380 v3 70%
00% 97% 00% 318.19
05% 23% 02% 26.19
S 32
s 15 v4 48% 23% 24% 05% 26.26
Tabel 5.3: Werklast verdeling van de recryptiemethode met versies 2, 3 en 4. Hieruit kan direct besloten worden waarom de tweede versie minder performant is, de GSA methode moet hier l maal herhaald worden en maakt de versie traag.
Uit tabel 5.3 blijkt dat versie 2 de minst performante is doordat de GSA methode hier niet met SIMD instructies wordt uitgevoerd. In versies 3 en 4 zijn de laatste 2 stappen dezelfde en dus is de werklast daar gelijkaardig, versie 4 besteedt relatief meer tijd aan de tweede stap doordat in de laatste versie hier een extra vermenigvuldiging nodig is.
Vergelijking recryptie met versies 2, 3 en 4 In tabel 5.4 bekijken we in meer detail de performantie van de 3 versies van de recryptiemethode. De bedoeling van deze tijdmetingen is om de invloed van de parameters m en l op de performantie aan te tonen, de veiligheid van deze schema’s is dan ook eerder laag genomen. De dimensie N is niet groot genoeg om echt veilig te kunnen worden genoemd. Zoals verwacht uit vergelijkingen 5.2 en 5.3 wordt de vierde versie performanter dan de derde in het geval dat l > S. Het grote voordeel aan de nieuwe versie is natuurlijk dat de publieke sleutel pk veel kleiner is dan deze gebruikt in versie 3 en dit voor een gelijkaardige snelheid van de recryptiemethode. Je zou de laatste versie dan ook kunnen beschouwen als een goed compromis tussen geheugengebruik en recryptiesnelheid in het geval dat l < S. De grootte van de publieke sleutel in de verschillende versies is gegeven als
|pk1 | ≈ |p| (N + s · S + 2 · N ) , |pk2 | ≈ |p| (N + s · S + 2 · l · n) , |pk3 | ≈ |p| (N + s · S · l + n + n · l) , |pk4 | ≈ |p| (N + s · S + n + n · l) ,
met pki de publieke sleutel in versie i, zie tabel 5.5. 62
5.6. Implementatieresultaten
m 127 585 511 1023 2255
l 18 24 48 60 80
t 380 380 380 380 380
S 32 32 32 32 32
s 15 15 15 15 15
v2 [s] 9.95 46.27 173.73 318.19 1754.48
v3 [s] 1.55 5.31 14.83 26.19 121.85
v4 [s] 2.27 7.29 18.39 26.26 110.34
Tabel 5.4: Performantie van de verschillende recryptiemethodes voor verschillende F (x) = Φm (x). We namen n steeds gelijk aan 1, waardoor er met bits wordt gewerkt. De versies 3 en 4 die gebruik maken van SIMD operaties zijn significant sneller dan versie 2. Zoals verwacht uit vergelijkingen 5.2 en 5.3 is voor l > S de vierde versie het snelst.
m
l
t
S
s
127 585 511 1023 2255
18 24 48 60 80
380 380 380 380 380
32 32 32 32 32
15 15 15 15 15
pk2 [MiB] 3.68 10.7 20.5 32.8 163.7
pk3 [MiB] 50.33 155.1 493.2 805.8 2929
pk4 [MiB] 3.58 10.4 19.5 31.2 157.9
Tabel 5.5: Performantie van de verschillende recryptiemethodes voor verschillende F (x) = Φm (x). We namen n steeds gelijk aan 1, waardoor er met bits wordt gewerkt. Zoals verwacht is de derde recryptieversie zeer geheugen onvriendelijk.
m
l
t
S
s
127 585 511 1023 2255
18 24 48 60 80
380 380 380 380 380
32 32 32 32 32
15 15 15 15 15
KeyGen v2 [s] 16.9 222.9 821.1 2237 40137
KeyGen v3 [s] 31.6 293.2 1171 3012 48474
KeyGen v4 [s] 23.4 256.6 1011 2806 47110
Tabel 5.6: Performantie van de verschillende sleutelgeneratiemethoden voor verschillende F (x) = Φm (x). We namen n steeds gelijk aan 1, waardoor er met bits wordt gewerkt. Merk op dat deze procedure veel trager is dan de gelijknamige procedure uit het Smart-Vercauteren schema.
63
5. De SIMD variant
Vergelijking met de Smart-Vercauteren variant Is het gebruik van deze SIMD constructie voordeliger ten opzichte van de klassieke Smart-Vercauteren variant? Ten eerste moet opgemerkt worden dat de KeyGen procedure in dit schema veel trager is dan dezelfde procedure in het Smart-Vercauteren schema, we praten dan toch snel over een factor 100 keer trager. Het is natuurlijk zo dat deze procedure slechts 1 keer moet worden aangewend. Het performantieverschil voor de Recrypt procedure kan afgelezen worden als het verschil in performantie tussen versies 2 en 4 ( of 3 ) in tabel 5.4. Dit aangezien recryptieversie 2 en recryptie met n · l Smart-Vercauteren cijferteksten even snel is. Versie 2 is dan ook, behalve het berekenen van γ (wat verwaarloosbaar is), essentieel gelijk aan recryptie van n · l Smart-Vercauteren cijferteksten. We beschouwen dan ook versie 2 als de controlegroep om te bepalen wat de tijdswinst is van recryptie met een SIMD recryptieversie (versies 3 of 4). Hier merken we dus een significant performantieverschil op. Dit performantieverschil neemt toe met de parameter m, wat ons vertrouwen geeft dat ook voor veilige waarden van m de recryptieversies 3 en 4 performanter zullen zijn. Het antwoord op de vraag of dit schema voordeliger is zal afhangen van hoe de vaste kost van sleutelgeneratie kan opgevangen worden door snellere een recryptieversie. Wel kan opgemerkt worden dat qua geheugen de SIMD variant altijd voordelen biedt, vermits er minder cijferteksten zijn voor meer databits.
5.7
Resultaten
In dit hoofdstuk bespraken we een schema dat SIMD operaties toelaat. We analyseerden de werking van drie reeds bekende recryptiemethoden uit [SV11] en stelden zelf ook een nieuwe recryptiemethode voor. Uit de tijdmetingen en geheugengebruik blijkt dat de hier voorgestelde recryptieversie zeer aantrekkelijk is. De recryptieversie heeft voor dezelfde tijdsefficiëntie, zie tabel 5.4, een veel minder grote publieke sleutel, zie tabel 5.5. We hebben ook aangetoond dat het gebruik van een SIMD schema voordeliger is dan het gebruik van het Smart-Vercauteren schema onder de volgende conditie. De KeyGen procedure is, in deze SIMD variant, zeer traag ten opzichte van de gelijknamige procedure in het Smart-Vercauteren schema, dus slechts bij een voldoende aantal recrypties zal het voordeliger worden dit schema te gebruiken.
64
Hoofdstuk
Recryptie met hulpservers n de tot nog toe besproken varianten was de recryptieoperatie voor een groot stuk verantwoordelijk voor de computationele kost van een homomorfe functie-evaluatie. Dit lijkt een onoverkomelijke moeilijkheid te zijn bij alle bekende volledig homomorfe schema’s. De vraag is nu of deze bewerking, met de hulp van 2 extra vertrouwde servers, kan geëlimineerd worden. We verliezen dan natuurlijk een stukje veiligheid doordat er bepaalde veronderstellingen moeten worden gemaakt omtrent deze hulpservers, maar we zouden de schema’s een heel stuk praktischer kunnen maken.
I
6.1
Inleiding
We veronderstellen dat de cliënt 2 hulpservers ter beschikking heeft. De bedoeling van deze servers is dat ze een cijfertekst kunnen hersleutelen zonder dat één van beide servers de boodschap kent. Om van homomorfe encryptie te kunnen spreken, moet het zo zijn dat geen van de 3 entiteiten (= 2 hulpservers + rekenwolk) de private sleutel in zijn bezit mag krijgen. Het idee van deze constructie is dat beide servers een partiële recryptieoperatie kunnen uitvoeren met behulp van een partiële private sleutel. Het is dan de bedoeling dat de cliënt deze partiële recrypties kan benutten om een volledige recryptie te verkrijgen. De constructie is gevisualiseerd in figuur 6.1. Natuurlijk moet nu worden verondersteld dat de twee vertrouwde hulpservers geen informatie omtrent de partiële sleutels vrijgeven. Dit is nodig om te voorkomen dat ëën van de drie entiteiten in het schema de volledige private sleutel in zijn bezit kan krijgen.
6.2
Beschrijving
We veronderstellen 2 hulpservers, HS1 en HS2. De servers hebben een geheim k gemeenschappelijk dat ze niet delen met de cliënt. Server j ∈ {1, 2} heeft ook nserver partiële sleutels zij in zijn bezit. 65
6
6. Recryptie met hulpservers
Figuur 6.1: Overzichtsschema van recryptie met behulp van 2 hulpservers. De rekenwolk zendt zijn cijfertekst naar de hulpservers. De twee hulpservers delen een geheim k. Beide servers hebben ook een partiële sleutel die ze verondersteld zijn niet te delen. De boodschap wordt partieel ontcijferd door de hulpservers met hun partiële sleutel. Met behulp van het geheim k kunnen de servers aanduiden welk van de partiële ontcijferingen kan gebruikt worden door de rekenwolk om een volledige (homomorfe) ontcijfering te bekomen.
We vertrekken in deze constructie ook met een initieel homomorf schema, de eisen gesteld aan dit homomorf schema zullen minder streng zijn dan in het SmartVercauteren schema daar recryptie hier een graad 1 veelterm zal blijken te zijn. We nemen als initieel schema het initiële schema dat gebruikt wordt in de SmartVercauteren variant, zie sectie 3.2. Natuurlijk weerhoudt niets ons ervan om in de praktijk een andere variant, bijvoorbeeld het DGHV schema, te gebruiken. De partiële sleutels zij hebben de eigenschap dat zi1 + zi2 = z, met z de private sleutel van het gebruikte initiële schema. De ontcijferprocedure van het Smart-Vercauteren schema is gegeven door Dec(sk, c) = [cz]p
mod 2.
Dit kan geschreven worden als Dec(sk, c) = 66
h
czi1
i
h
p
+ czi2
i p p
mod 2.
6.2. Beschrijving We noemen DecHSj (sk, c) = [czij ]p de partiële ontcijferingen van de cijfertekst c. We kunnen dan de volledige ontcijfering van c schrijven als h
Dec(sk, c) = DecHS1 (ski1 , c) + DecHS2 (ski2 , c)
i p
mod 2.
(6.1)
Chosen Ciphertext Attack Nu is het natuurlijk zo dat we niet de partiële recrypties DecHSj (ski , c) mod 2 willen prijsgeven aan één van de drie entiteiten. Deden we dit wel dan kan de entiteit mits goed gekozen verzoeken c de partiële geheime sleutels skij in O(log2 (n)) verzoeken uniek bepalen, zie [LMSV10]. Deze chosen ciphertext attack (CCA) wordt nog eens gegeven in algoritme 6.1, een analyse van dit algoritme kan ook gevonden worden in [LMSV10]. Algorithm 6.1 CCA(p, ODec (◦)) Ensure: output = sk 1: L := 0; U := d − 1 2: while (U − L) ≥ 1 do 3: c := bd/(U − L)e 4: b := ODec (c) 5: q := c + b mod 2 6: k := bLc/d + 1/2c 7: B := (k + 1/2)d/c 8: if k mod 2 = q then 9: U := bBc 10: else 11: L := dBe 12: end if 13: end while 14: return L
Recryptie protocol Om nu vergelijking 6.1 te kunnen evalueren, met enkel de partiële recrypties, hebben we nodig dat h
DecHS1 (ski1 , c) + DecHS2 (ski2 , c)
i p
= DecHS1 (ski1 , c) + DecHS2 (ski2 , c)
mod 2.
Het idee is een partieel sleutelpaar zi∗ te zoeken waarvoor geldt dat
∗
∗
Sign DecHS1 (ski1 , c) 6= Sign DecHS2 (ski2 , c) .
(6.2)
Om deze reden hebben we nserver verschillende sleutelparen, de kans dat geen van alle paren voldoet aan vergelijking 6.2 is 2−nserver . De cliënt moet natuurlijk wel 67
6. Recryptie met hulpservers te weten komen welke van de partiële recrypties die hij krijgt van de hulpservers hij moet combineren om een volledige recryptie te bekomen. Dit moet gebeuren zonder dat één van de hulpservers weet wat i∗ is, anders kunnen de hulpservers een CCA uitvoeren om de partiële sleutels van de andere te bekomen, zie vorige sectie. Daarom zenden beide servers naast hun versleutelde partiële recrypties
∗
∗
πi1 := Enc DecHS1 (ski1 , c) πi2 := Enc DecHS2 (ski2 , c)
mod 2, pk ,
mod 2, pk ,
ook de message authentication codes (MACs) die als volgt worden aangeduid mac1i := MAC(c, k) ⊕ (DecHS1 (ski1 , c) ≥ 0), mac2i := MAC(c, k) ⊕ (DecHS2 (ski2 , c) ≥ 0), met ⊕ de operatie waarbij de laatste bit van macji wordt gezet als de XOR van beide leden. De cliënt neemt dan 2 partiële recrypties waarbij de MACs verschillend zijn. De MAC gebruikt in de praktische implementatie is gebaseerd op de advanced encryption standard (AES) MAC(c, k) = AES256 (c mod 2256 , k), en is alles behalve veilig en efficiënt in deze constructie, maar dit is hier minder relevant. In een echte implementatie mag bovenstaande MAC dus niet gebruikt worden. We verduidelijken alles nog eens in pseudocode in algoritmen 6.2 en 6.3. Algorithm 6.2 Recrypt(c) met 2 hulpservers 1: (πi1 , mac1i ) := Hulpserver1 (c) 2: (πi2 , mac2i ) := Hulpserver2 (c) 3: zoek een i∗ waarvoor mac1i∗ 6= mac1i∗ 4: return cnew := πi1∗ + πi2∗ mod p
Algorithm 6.3 Hulpserver(c) par par 1: mi := [c · zi ]p mod 2 par 2: πi := Enc(mi , pk) par 3: maci := MAC(c, k) ⊕ ([c · zi ]p ≥ 0) 4: return (πi , maci )
6.3
Minimale initiële homomorfe schema’s
We proberen in deze sectie initiële homomorfe schema’s op te stellen zodat ze net alle multiplicatieve circuits met een bepaalde diepte dcircuit homomorf kunnen evalueren, 68
6.4. Performantie
Figuur 6.2: Multiplicatief circuit met een diepte d. De uitgang bit is een veelterm d bestaande uit 22 eentermen van graad 2d .
na een recryptieoperatie. Het spreekt voor zich dat dezelfde circuits, maar dan met optellingen in plaats van vermenigvuldigingen ook zullen kunnen worden geëvalueerd, zie hoofdstuk 3. Op deze manier zullen we dan proberen nagaan wat het optimale initiële schema is. We starten met te bepalen hoe homomorf deze initiële schema’s moeten zijn zodat ze multiplicatieve circuits van diepte dcircuits kunnen evalueren na een recryptieoperatie. De veelterm van een multiplicatief circuit van diepte dcircuit bestaat uit d 22 circuit eentermen van graad 2dcircuit , zie figuur 6.2. Uit hoofdstuk 3 blijkt dat we nu moeten hebben dat 2t ≥ c2
dcircuit
q
dcircuit
(22
),
opdat de decryptie correct verloopt. Hieruit volgt met c ≈ 8 dat t ≥ 3.5 · 2dcircuit . We zullen tijdbepalingen geven voor dcircuit = {1, 2, 3, 4, 5}, en voor t nemen we t = 2dcircuit +2 . De dimensie van N volgt dan onmiddellijk uit de ongelijkheid N≥
λt , µ log2 (λ)
welke ook komt uit hoofdstuk 3, en die ervoor zorgt dat rooster reductie aanvallen niet mogelijk zijn. We nemen voor n steeds de kleinste macht van 2 die voldoet aan de bovenstaande ongelijkheid, we veronderstellen µ = 0.54.
6.4
Performantie
We geven de performantie van de verschillende minimale systemen in functie van hun homomorfe diepte dcircuit , zie tabel 6.1. We merken op dat de performantie van een volledig homomorf schema grotendeels bepaald is door de verhouding Recrypt/dcircuit . Dit doordat de kost van recryptie veel hoger is dan die van een homomorfe optelling of vermenigvuldiging. Er kunnen na een recryptieoperatie exact dcircuit homomorfe operaties gebeuren, waardoor de verhouding Recrypt/dcircuit een maat is van de 69
6. Recryptie met hulpservers dcircuit 1 2 3 4 5
λ 72 72 72 72 72
t 8 16 32 64 128
N 256 512 1024 2048 4096
KeyGen [s] 0.020 0.050 0.610 9.610 135.350
Recrypt dcircuit [s]
0.270 0.175 0.287 1.300 7.172
Tabel 6.1: Minimale systemen en tijdmetingen. We merken op dat dcircuit = 2 een optimaal systeem oplevert.
snelheid van progressie doorheen een opgegeven circuit. Er is dus een compromis tussen de stijgende complexiteit van het initiële schema in functie van dcircuit en de mogelijkheid om de kost van de recryptieoperatie te spreiden over dcircuit operaties. Uit tabel 6.1 blijkt dat het systeem met een diepte dcircuit = 2 een optimale verhouding Recrypt/dcircuit heeft. In de praktijk echter zou het kunnen dat de diepte dciruit groter moet worden genomen doordat in deze analyse geen rekening is gehouden met de communicatiekost tussen de cliënt en de servers. Het geheugengebruik van dit schema is, door het wegvallen van het SSSP, minder dan in het Smart-Vercauteren schema |pk| ≈ |p| N, |sk| ≈ |p| . Voor het meest interessante geval wanneer N = 512, komt dit neer op een publieke sleutel van slechts 586 [KiB].
Voordelen ten opzichte van klassieke varianten Het grote voordeel van recryptie met de hulpservers is overduidelijk de performantie qua snelheid. Het grootste deel van het werk gebeurt nu door de 2 hulpservers die beide kunnen werken in de klaartekstruimte. De partiële decrypties worden dan in versleutelde vorm terug naar de cliënt gezonden samen met de MACs. De enige homomorfe operatie in de Recrypt methode is de optelling in vergelijking 6.1. Hierdoor is het ruisniveau rrec2 terug bijna gelijk aan renc waardoor veel minder recryptieoperaties vereist zijn. Het is hier natuurlijk ook zo dat rdec = rrec1 omdat recryptie nu gebeurt in de klaartekstruimte en er dus geen afrondingsfouten optreden door het werken met slechts pb bits precisie na de komma.
6.5
Resultaat
In dit hoofdstuk stellen we een nieuw encryptieschema voor dat, met de hulp van 2 vertrouwde hulpservers, een praktische compromis maakt tussen de veiligheid van een volledig homomorf schema en de snelheid van een “normaal” encryptieschema. Dit wordt gerealiseerd door de recryptieoperatie te vervangen door 2 partiële recrypties. 70
6.5. Resultaat De opzet van dit hoofdstuk was een schema ontwikkelen met 3 entiteiten waarbij decryptie van een cijfertekst kon plaatsvinden zonder dat 1 van de 3 entiteiten de volledige private sleutel nodig had. De beschreven constructie voldoet aan laatstgenoemde eigenschappen. We maken hier wel geen vergelijking met de reeds beschreven volledig homomorfe schema’s, vermits de vergelijking per definitie niet eerlijk zou zijn. Nadien werden de schemaparameters gekozen voor optimale homomorfe evaluatie, de optimale constructie kan 2 operaties homomorf evalueren na elke recryptieoperatie. Wel kan worden opgemerkt dat de optimale parameters afhankelijk zijn van het communicatiekanaal tussen de cliënt en de hulpservers.
71
Hoofdstuk
Besluit it hoofdstuk probeert nog eens de belangrijkste bevindingen en opmerkingen te bundelen, en probeert ook toekomstige richtingen van onderzoek aan te wijzen. Dit hoofdstuk bevat echter alleen de nieuwe informatie en resultaten gepresenteerd in deze thesis, dus zonder theorie en achterliggende concepten. Voor meer tekst en uitleg wordt verwezen naar de relevante hoofdstukken in deze thesis.
D
7.1
De Smart-Vercauteren variant
In hoofdstuk 3 wordt het Smart-Vercauteren schema geanalyseerd en geëvalueerd zoals het kan gevonden worden in [SV09, GH10]. Het grote verschil met de beschrijving gegeven in de literatuur is dat, in deze tekst, het SSSP wordt ontworpen in de veronderstelling dat een aanvaller de private sleutel niet in zijn bezit heeft. Hierdoor moest de veiligheidsanalyse, gegeven in [GH10], aangepast worden. De nieuwe schemaparameters maken het index-encoderingsmechanisme, zoals beschreven in [GH10], overbodig. Rekening houdend met alle wijzigingen en nieuwe veiligheidsvoorwaarden worden volgende schema’s vooropgesteld als referentieschema’s.
Klein Middel Groot
λ 72 72 72
µ 2.39 0.59 0.15
N 1024 4096 16384
t 210 210 210
(s, S) (15, 32) (15, 32) (15, 32)
R 2102 2381 2381
Hierin hanteren we een vast veiligheidsniveau λ = 72 en een variabele inschatting (µ) van de haalbaarheid van roosterreductieaanvallen op het schema. Hiermee volgen we dezelfde strategie als voorgesteld in [GH10]. De schema’s worden geïmplementeerd in de programmeertaal Magma en uitgevoerd op machines met elk een Intel Xeon Quad core CPU (X7350) aan een kloksnelheid van 2.93GHz, met 8 GiB werkgeheugen, en Debian GNU/Linux 6 als besturingssysteem, net zoals alle andere implementaties in deze thesis. De resultaten verkregen voor de hierboven voorgestelde testschema’s worden hieronder gegeven. 73
7
7. Besluit KeyGen [s] 29 402 7018
Klein Middel Groot
Enc [s] 0.04 0.29 1.92
Dec [s] 0.05 0.40 2.61
|pk| [MiB] 40 479 6910
Recrypt [s] 5 39 216
We merken dus op dat de afhankelijkheid van de parameter µ groot is. Het nauwkeurig bepalen of schatten van µ is dus nog een belangrijke opdracht. We hopen dat dit probleem het onderzoek naar de echte moeilijkheid van roosterreductieaanvallen in de toekomst zal aanmoedigen.
7.2
De DGHV variant
In hoofdstuk 4 wordt het DGHV schema geanalyseerd en geëvalueerd zoals het kan gevonden worden in [vDGHV09]. Om dezelfde redenen genoemd in vorige sectie, wordt het SSSP hier ook op een andere manier ontworpen. Hierdoor moet weer de veiligheidsanalyse, gegeven in [vDGHV09] aangepast worden. De veiligheidsanalyse moest ook op eenzelfde manier worden uitgevoerd als bij de Smart-Vercauteren variant. Dit om een eerlijke analyse van de schema’s mogelijk te maken. Ook hier valt het index-encoderingsmechanisme, om dezelfde reden als bij de SmartVercauteren variant, weg. Rekening houdend met alle veiligheidsvoorwaarden worden volgende testschema’s vooropgesteld. Deze schema’s zijn compatibel gekozen, qua veiligheid, aan de testschema’s voorgesteld in vorige sectie. We geven ze hieronder mee. Klein Middel Groot
λ 72 72 72
µ 2.39 0.59 0.15
α 11 11 11
ρ 72 72 72
η 2500 2500 2500
γ ×106 27.7 112.3 441.8
(s, S) (15, 32) (15, 32) (15, 32)
Hierin hanteren we een vast veiligheidsniveau λ = 72 en een variabele inschatting (µ) van de haalbaarheid van roosterreductieaanvallen op het schema. Daar deze schema’s equivalent zijn qua veiligheid kunnen ze vergeleken worden met de schema’s voorgesteld in de vorige sectie. De belangrijkste resultaten worden in onderstaande tabel samengevat.
Klein Middel Groot
KeyGen [s] 39 161 649
Enc [s] 773 4283 21912
Dec [s] 0.14 0.65 2.85
Recrypt [s] 3680 20243 95228
|pk| [GiB] 01.62 06.56 25.82
Een vergelijking van deze resultaten en de resultaten gegeven in de vorige sectie leert ons dat dit schema veel minder performant is dan de Smart-Vercauteren variant. In [vDGHV09] wordt echter het tegendeel beweerd. Maar een nauwkeurige analyse van hun testschema’s leert ons dat de vergelijking in [vDGHV09] helemaal niet eerlijk is 74
7.3. De SIMD variant gebeurd. Het belangrijkste besluit van dit hoofdstuk is dus dat, zowel op vlak van tijdsefficiëntie als geheugengebruik, dit schema zijn meerdere moet erkennen in het Smart-Vercauteren schema.
7.3
De SIMD variant
De schema’s beschreven in zowel hoofdstuk 3 als ook in hoofdstuk 4 kunnen elk slechts 1 bit versleutelen in een cijfertekst. Gezien de hoge computationele kost van een recryptieoperatie, en het feit dat een cijfertekst vrij veel geheugen opeist (≈ 100 KiB in het Smart-Vercauteren schema), bespreken we in hoofdstuk 5 de SIMD variant [SV11]. Deze variant laat SIMD operaties toe, waardoor 1 cijfertekst nu meerdere databits kan versleutelen. We bespreken 3 versies van het Recrypt algoritme, gaande van een naiëve tot een complexe implementatie. Ook stellen we hier een nieuwe versie (v4) voor die, bij een hoog parallellisme l, zeer competitief is ten opzichte van de eerste 3 bestaande recryptieversies, op vlak van zowel tijdscomplexiteit als geheugengebruik. Als testschema’s beschouwen we onderstaande tabel. m 127 585 511 1023 2255
l 18 24 48 60 80
t 380 380 380 380 380
S 32 32 32 32 32
s 15 15 15 15 15
Waarbij l het aantal bits is dat in 1 cijfertekst kan versleuteld worden. De schema’s werden met opzet te klein gekozen om equivalent te zijn aan de schema’s gegeven in vorige secties. Met andere woorden m is te klein, dit doordat de KeyGen procedure zeer traag is in de SIMD variant. Toch kan een vergelijking, weliswaar voor een niet veilige parameter m, met de Smart-Vercauteren variant gemaakt worden. Dit doordat versie 2 van het Recrypt algoritme equivalent is aan recryptie van l SmartVercauteren cijferteksten. Elke recryptieversie die sneller is dan versie 2 is dus performanter dan het gebruik van de Smart-Vercauteren recryptie. Hieronder worden de resultaten samengevat. m
l
127 585 511 1023 2255
18 24 48 60 80
pk2 [MiB] 3.68 10.7 20.5 32.8 163.7
pk3 [MiB] 50.33 155.1 493.2 805.8 2929
pk4 [MiB] 3.58 10.4 19.5 31.2 157.9
v2 [s]
v3 [s]
v4 [s]
9.95 46.27 173.73 318.19 1754.48
1.55 5.31 14.83 26.19 121.85
2.27 7.29 18.39 26.26 110.34
Uit de gegevens in bovenstaande tabel blijkt duidelijk dat de recryptieversies 3 en 4 significant sneller zijn dan recryptieversie 2, en dus sneller dan recryptie van l 75
7. Besluit Smart-Vercauteren cijferteksten met slechts 1 bit aan informatie in de onderliggende boodschap. We halen uit de metingen ook een groot vertrouwen in het feit dat recryptie, voor reële en dus grotere waarden van m, performanter zal zijn dan recryptie van l Smart-Vercauteren cijferteksten. De nieuw voorgestelde recryptieversie 4 is ook duidelijk performanter dan de reeds bestaande recryptieversies, dit vooral door een gelijkaardige tijdsefficiëntie aan te bieden voor een significant kleinere publieke sleutel. Maar is het gebruik van deze SIMD constructie nu werkelijk voordeliger dan de klassieke Smart-Vercauteren variant? Een vaststelling is dat de KeyGen procedure van de SIMD variant veel meer tijd vraagt dan de gelijknamige procedure van het Smart-Vercauteren schema (≈ 100 maal meer tijd). Daar tegenover staat wel dat recryptie, geamortiseerd over de l bits onder de cijfertekst, significant veel sneller kan gebeuren. Ook op vlak van geheugengebruik is dit schema voordeliger, vooral gezien het feit dat het aantal cijferteksten drastisch kan verminderd worden door de SIMD formulering. In het beste geval kunnen in elke cijfertekst nu l databits worden versleuteld. Het antwoord op de vraag of dit schema voordeliger is zal dus afhangen van hoe de vaste kost van sleutelgeneratie kan opgevangen worden door snellere recryptie in het SIMD schema.
7.4
Recryptie met hulpservers
De tijdmetingen van de besproken schema’s in acht genomen, kunnen we stellen dat voorlopig geen van alle als praktisch haalbaar kan worden bestempeld. Daarom wordt in het laatste hoofdstuk 6 een schema voorgesteld, dat met behulp van 2 vertrouwde hulpservers, een pragmatische oplossing voor volledig homomorfe encryptie biedt. Om van homomorfe encryptie te kunnen spreken, moet het echter zo zijn dat geen van de 3 entiteiten (= 2 hulpservers + rekenwolk) de private sleutel in zijn bezit mag krijgen. Het idee van deze constructie is dat beide hulpservers een partiële recryptieoperatie kunnen uitvoeren met behulp van een partiële private sleutel. Het is dan de bedoeling dat de cliënt deze partiële recrypties kan benutten om een volledige recryptie te verkrijgen. De performantie van de constructie voor een variabel aantal toegelaten homomorfe operaties na recryptie is gegeven in onderstaande tabel. Dus een schema met dcircuit = 3 betekent dat slechts om de drie homomorfe vermenigvuldigingen Mult het resultaat moet worden hersleuteld. dcircuit 1 2 3 4 5
λ 72 72 72 72 72
t 8 16 32 64 128
N 256 512 1024 2048 4096
KeyGen [s] 0.020 0.050 0.610 9.610 135.350
Recrypt dcircuit [s]
0.270 0.175 0.287 1.300 7.172
In de vorige volledig homomorfe schema’s moest na elke homomorfe operatie een recryptie plaatsvinden van het resultaat. Hier kiezen we voor het schema waarvoor 76
7.5. Een blik op de toekomst dcircuit = 2. In dit schema is de verhouding tussen het tijdsgebruik van een recryptieoperatie en het aantal toegelaten homomorfe operaties dcircuit minimaal. Met deze keuze zal de homomorfe evaluatie van een gegeven circuit het snelst zijn. Het moet natuurlijk gezegd zijn dat de veiligheidsonderstellingen uitgebreid moeten worden, en dat dus een vergelijking met de performantieresultaten van schema’s in de vorige hoofdstukken nooit eerlijk is. We vermijden dan ook van deze vergelijking.
7.5
Een blik op de toekomst
In hoofdstukken 3 en 4 bestaat er nog geen duidelijke aflijning over wat een redelijke waarde voor de veiligheid parameter µ zou kunnen zijn. Gezien deze parameter een vrij belangrijke invloed heeft op de performantie en veiligheid van de volledig homomorfe schema’s is het van belang dat hierover verder nagedacht wordt. Deze vraag bevindt zich meer in het domein van het onderzoek naar roosterreductiealgoritmen. Een interessant aanknopingspunt is gegeven in [GN08]. Het oplossen van een realistisch probleem met behulp van volledig homomorfe encryptie is tot op heden nog niet gebeurd. Het zou wel interessant zijn om te weten welke problemen oplosbaar zijn in een redelijke tijd aan de hand van gekende schema’s. Bijvoorbeeld, in het geval dat er slechts een beperkt aantal vermenigvuldigingen dient te gebeuren, waardoor het aantal Recrypt operaties beperkt blijft, kan een volledig homomorf schema een praktische oplossing bieden. Echter, wil volledig homomorfe encryptie ooit een volwaardige technologie worden dan is een doorbraak nog steeds noodzakelijk, de huidige schema’s zijn zowel op het vlak van tijd als op geheugen nog steeds te veeleisend.
77
Bijlagen
79
Bijlage
Roosters et onderzoek van wiskundige roosters vormt een belangrijk domein binnen de cryptologie. Roosters hebben hun nut bewezen in zowel de cryptografie, zie bijvoorbeeld het publieke sleutel encryptie schema NTRUEncrypt [HPS98]. Maar ook in de cryptoanalyse heeft het werken met roosterstructuren reeds zijn vruchten afgeworpen, zie bijvoorbeeld de befaamde Coppersmith aanval [Cop97]. Daarom geven we in deze appendix een aantal relevante definities en eigenschappen van rooster structuren nodig in deze thesis. Alles van deze appendix komt uit de referenties [Mol99, Coh95].
H
A.1
Definities en eigenschappen
Roosters worden gedefinieerd als een discrete deelverzameling van de ruimte Rn met een groepsstructuur. Een rooster kan ook beschouwd worden als een geordende betegeling van de ruimte Rn met een eenheidscel. Definitie A.1.1 (Roosters en parallelotopen). Zij l1 , l2 , . . . , lm ∈ Rn (m, n ∈ N, m ≤ n) R-lineair onafhankelijke vectoren. Als L :=
l ∈ Rn en l =
m X
zj lj voor een zj ∈ Z
j=1
= Z [l1 , . . . , lm ] ,
dan wordt L een rooster van dimensie m in Rn genoemd. Als m = n dan wordt L ook een volledig rooster genoemd. De verzameling P=
n X
rj lj : rj ∈ R, 0 ≤ rj ≤ 1 voor j = 1, 2, . . . , n
j=1
wordt het fundamentele parallellepipedum genoemd, of het fundamentele domein van L. De invariant van P is V (P) = det(lj ), we noemen dit het volume van P, of de discriminant van L. 81
A
A. Roosters
Figuur A.1: Een rooster in R2 en 3 verschillende basissen. Het is duidelijk dat basis B1 de meest interessante is.
Een belangrijke eigenschap van roosters is dat ze een discrete deelgroep vormen van Rn . Zie figuur A.1 voor een visuele representatie van een rooster in R2 . We beschouwen hierna alleen nog volledige roosters, dus waarvoor m = n. Stelling A.1.1 (Roosters zijn discreet). Zij L ⊆ Rn , L 6= ∅. Dan is L een rooster als en slechts als L een discrete additieve deelgroep is van Rn . Een rooster wordt gespecificeerd door een basis matrix B, bestaande uit n lineair onafhankelijke basis vectoren bj . Het rooster opgespannen door de basis B wordt genoteerd als L(B). De basis matrix B voor een gegeven rooster L is niet uniek, we gaan daarom op zoek naar die basis matrices die in een bepaald opzicht het interessantst zijn.
A.2
Rooster basissen
Elk rooster L heeft oneindig veel verschillende basissen Bj . Elk van deze basissen is gerelateerd aan elkaar door middel van een unimodulaire transformatie: Bi := Mi,j · Bj met Mi,j ∈ Zm×m en det(Mi,j ) = ±1. In figuur A.1 worden een aantal mogelijke basissen grafisch voorgesteld voor een rooster in R2 . Aangezien het volume van het fundamentele parallellepipedum onafhankelijk is van de gekozen basis, kan eenvoudig worden ingezien dat langere basisvectoren resulteren in een minder orthogonale basis (de hoek tussen de verschillende basisvectoren 82
A.2. Rooster basissen zal klein zijn). Dit geeft ons een maat voor de kwaliteit van een basis. Bijvoorbeeld, een belangrijke maat voor de kwaliteit van een basis bij volledig homomorfe encryptie is rdec , de straal van de grootste bol die nog past in het fundamenteel parallellepipedum van het rooster L. Het is duidelijk dat bij een invariant volume V (L) deze straal rdec groter wordt naarmate de basis Bi orthogonaler is. Definitie A.2.1 (Orthogonaal defect). Het orthogonale defect van een basis B kb1 k . . . kbn k , V (L) geeft een maat voor de kwaliteit van de basis B. De vraag is dus hoe we de optimale basis, de basis met een minimum orthogonaal defect of kortste basisvectoren, kunnen vinden. Dit laatste probleem is gekend als het rooster reductie probleem, gegeven een basis B met gegeven getallen, zoek een equivalente basis met zo kort mogelijke basisvectoren bi . Deze optimale basis wordt ook wel eens Minkowski’s gereduceerde vorm genoemd, basisvector i heeft dan als norm λi (L). Definitie A.2.2 (Rooster minima λi (L)). Voor i ≤ n, λi (L) is de minimum straal r bij welke de bol B(0, r) i lineair onafhankelijke rooster vectoren bevat. In figuur A.1 is het duidelijk dat de zwarte basis een optimale basis is. De optimale basis zoeken voor L wordt echter zeer moeilijk wanneer n groot wordt. In het bijzonder nemen we aan dat voor elke k en (groot genoege) n het een tijd 2k duurt om het SVP of het BDDP te benaderen tot op een factor µ·n
α = 2 k/ log k . Definitie A.2.3 (Approx-SVP). Gegeven een rooster L en een benaderingsfactor α ≥ 1, zoek een niet-nul vector met een norm ≤ α · λ1 (L). Merk op dat het niet altijd makkelijk is om de correctheid van een oplossing na te gaan, vermits λ1 (L) niet noodzakelijk gekend is. Definitie A.2.4 (Approx-BDDP). Gegeven een rooster L, een benaderingsfactor α ≥ 1 en een vector x, zoek een een rooster vector y ∈ L zodat dist(x, y) ≤ α · λ1 (L) (als z’n vector bestaat). We hebben dus dat beide rooster reductie problemen NP-hard zijn. Er bestaan echter wel bruikbare bovengrenzen op deze rooster minima λi (L). Stelling A.2.1 (Minkowski’s convex lichaam stelling). Stel dat L een volledig rooster is, en laat V (P) het volume zijn van het fundamenteel parallellepipedum P van het rooster L. Als S een symmetrische convexe verzameling is in Rn met een volume V (S) zodanig dat V (S) ≥ 2n V (P), dan bestaat er een x ∈ S ∩ L met x 6= 0. 83
A. Roosters Uit Minkowski’s stelling volgt onmiddellijk een bovengrens op λi (L):
λ1 (L) ≤ 2
V (L) vn
1/n
≤
√
nV (L)1/n ,
met vn = π d/2 /Γ(1 + d/2) het volume van de eenheidsbal in Rn . Voor een ‘willekeurig’ rooster worden deze grenzen verwacht om strak te zijn: λ1 ≈ λ2 ≈ · · · ≈ λn ≈ V (L)1/n , met andere woorden de bovengrens op λi is een goede schatting van de lengte van de korste vectoren in L.
A.3
De Hermite normaal vorm
Net zoals de Minkowski gereduceerde vorm een canonieke vorm is voor de basis matrix B, is ook de HNF een canonieke vorm van de basis matrix B. De Minkowski gereduceerde vorm was in een bepaalde zin de optimale basis, de HNF wordt door sommige auteurs de slechtste basis genoemd. Daarom werd de HNF vooral gebruikt als publieke voorstelling voor een rooster L, terwijl de Minkowski gereduceerde vorm eerder als private representatie zou kunnen dienen. Aangezien alle basissen Bi kunnen voorgesteld worden door een matrix met gehele coëfficienten, kan de HNF worden gezien als een canonieke vorm voor een matrix net zoals bijvoorbeeld de echolonvorm. De HNF vorm is uniek bepaald voor elk rooster L. Definitie A.3.1 (Hermite normaal vorm). Voor elke n × m matrix A met gehele getallen, de HNF van A is de unieke matrix H = (hi,j ) zodat er een unimodulaire n×n matrix U bestaat met U A = H en waarbij H voldoet aan volgende 2 voorwaarden: 1. Er bestaat een sequentie van gehele getallen j1 < · · · < jn zodat voor alle 0 ≤ i ≤ n geldt dat hi,j = 0 voor alle j < ji (rij echelon structuur). 2. Voor 0 ≤ k < i ≤ n hebben we dat 0 ≤ hk,ji < hi,ji (het pivot element is het grootst element in zijn kolom en de elementen boven de pivot zijn groter of gelijk aan 0.) Opmerking. Dus de HNF is een generalisatie over Z van de rij gereduceerde echelon vorm van een matrix over Q. Net zoals het berekenen van de echolonvorm een basis operatie is voor vele algoritmen die werken met vector ruimten, is het berekenen van de HNF een basis operatie wanneer we werken met modules over Z. Er bestaan snelle algoritmen om deze canonieke vorm te berekenen voor een willekeurige matrix M , zie bijvoorbeeld [PS10]. Een voorbeeld(je) genomen uit dezelfde bron toont aan dat deze vorm meestal aanleiding geeft tot een zeer groot orthogonaal defect. 84
A.3. De Hermite normaal vorm Voorbeeld. De HNF van de matrix
A=
is
A=
−5 8 −3 −9 5 5 −2 8 −2 −2 8 5 7 −5 −8 4 3 −4 1 −1 6 0 8 −3 1 0 0 0
0 1 0 0
3 1 4 0
237 299 90 103 −130 40 352 −450 135 486 −627 188
.
Merk op dat de elementen in de HNF veel groter zijn de elementen van A. Een heuristische vaststelling hierbij is: voor een willekeurige n × m matrix A met n ≤ m is het aantal cijfers van de elementen in de meest rechtse m − n + 1 kolommen van de bijhorende matrix H ongeveer gelijk aan het aantal cijfers van de determinant van de linkse n × n submatrix van A. Deze vaststelling maakt onmiddellijk duidelijk waarom de HNF basis van een rooster L als zeer slecht wordt beschouwd, de basisvectoren bi zijn zeer lang en het orthogonaal defect dus zeer groot.
85
Bijlage
CD-ROM Op de bijgeleverde CD-ROM is alle gebruikte Magma code terug te vinden.
87
B
Bijlage
IEEE artikel
89
C
1
A fair efficiency comparison of existing fully homomorphic encryption schemes Bart P.G. Van Parys
Abstract—In 2009 Gentry came up with the first construction of a fully homomorphic encryption (FHE) scheme based on ideal lattices, hereby ending the nearly 40 year old quest of finding such scheme. Since then, a number of fully homomorphic encryption schemes have been constructed. However, a fair comparison of these constructions has never been conducted. In this paper we compare 2 fundamentally different constructions: the Smart-Vercauteren scheme and the DGHV scheme. The conducted timings suggest that the Smart-Vercauteren scheme is considerably faster then the DGHV scheme, this is in contrast to what is suggested in literature. Furthermore, we consider a fully homomorphic encryption scheme that supports single instruction multiple data (SIMD) operations. Also this scheme is compared to both the SmartVercauteren and the DGHV scheme, whereby we consider 3 different methods for recrypting messages. We also suggest a new recryption method, which seems very attractive when the used level of parallelization is high. Especially in terms of memory usage this method seems to be very competitive. Index Terms—Computer security, Cryptography, Fully homomorphic encryption
F
I. I NTRODUCTION
Irst of all, in this paper FHE is considered a subclass of asymmetric encryption, i.e. a FHE scheme allows computation on encrypted data with only knowledge of the public key. In a FHE scheme the ciphertext space is homomorph to the plaintext space, with the decryption function Dec as the homomorphism. In other words, Dec(c1 ⊕ c2 , sk) = Dec(c1 , sk) + Dec(c2 , sk) and Dec(c1 ⊗c2 , sk) = Dec(c1 , sk)×Dec(c2 , sk), with ⊕, ⊗ and +, × addition and multiplication in the ciphertext and plaintext space respectively. Using this property we can evaluate any circuit1 on encrypted data, using only the public key. This notion of FHE came to existence under the name privacy homomorphism as introduced by Rivest, Adleman and Dertouzous [2]. Since then, a vast number of killer applications have been identified that could be solved using FHE. But it was not until the breakthrough of Gentry [3] that such an encryption scheme had been found. Since 2009, a number of FHE schemes have been constructed [4], [5], [6]. The Smart-Vercauteren scheme is, when closely examined, a particular instance of the abstract construction that Gentry describes in [3]. This concrete scheme is especially tailored for better performance by choosing the lattices of [3] in an intelligent way. However, the scheme is described by means of number fields in [4]. Important optimizations and 1 A circuit in computer theory is a theoretical structure simulating a real circuit, in which input values enter in one part of the circuit, go through gates which do some computation and output an answer [1].
implementation results are given in [7], but care should be taken when comparing both descriptions, since in the latter, the scheme is described with the use of lattices. The DGHV scheme is ought to give a conceptually simpler FHE scheme. The description is given in [5], the conceptual simplicity follows from the fact that the scheme merely uses integers to achieve FHE. From the timing results given in [5] one should conclude that, next to being more simple, this last scheme is also more performant then the first. However, question marks should be placed next to this conclusion since the comparison can hardly be called fair. The big disadvantage of both the Smart-Vercauteren and the DGHV scheme is the fact that one ciphertext encrypts only a one bit message. Since the ciphertext expansion of both schemes can be well over a hundred thousand, memory usage tends to become a problem. A scheme that provides SIMD operations is described in [6]. The scheme also provides time efficiency advantages, since less Recrypt operations will be necessary during evaluation of a given circuit. However, a fair comparison of these schemes remains to be done, that will be the main purpose of this article. All schemes were implemented in Magma, a high level scripting language [8], and evaluated using compatible security assumptions. II. T HE ROAD TO FULLY HOMOMORPHIC ENCRYPTION Since all known FHE schemes are based on the original abstract construction given in [3], we try to give an informal explanation of how a FHE scheme based on this abstract construction looks like. Those schemes depend on three important cornerstones to achieve FHE. On a very high level the construction looks as follows. Cornerstone II-A consists of selecting a somewhat homomorphic encryption (SHE) scheme E, i.e. an asymmetric encryption scheme that can evaluate a limited set of circuits CE . Cornerstone II-B consists of making the SHE scheme bootstrappable. We demand that the decryption function plus an extra operation, which itself can be described by a circuit, can be evaluated by E. This will enable us to make progress through the to be evaluated circuit using the Recrypt procedure. Cornerstone II-C is needed to make the scheme E bootstrappable. This is done by transforming the decryption function to make decryption less complex, thereby enabling the SHE scheme to evaluate the transformed decryption function plus an extra operation.
2
A. Somewhat homomorphic encryption As said, all known FHE scheme have a SHE scheme at their core. Principally the choice is wide open. Gentry noticed that encryption schemes for which the decryption function can be expressed as a low degree polynomial2 in the bits of the private key are favourable. As such the scheme E consists of 5 fundamental functions. scheme E Key generation Decryption Encryption Addition Multiplication SHE
KeyGen(λ) Dec(c, sk) Enc(m, pk) Add(c1 , c2 , pk) Mult(c1 , c2 , pk)
The SHE scheme of the Smart-Vercauteren scheme is based on ideals in number fields. The exact description is not relevant here, but important to note is that a ciphertext is a number modulo a public integer p. The plaintext space is restricted to one bit, hence m ∈ {0, 1}. The decryption function is given as Dec(c, sk) = [cz]p mod 2, and it should be noted that this SHE scheme is in itself not bootstrappable, squashing is necessary. The SHE scheme of the SIMD scheme is very similar to the Smart-Vercauteren scheme. Again the ciphertext is an integer modulo p, but here the plaintext space is not restricted to Z2 . The plaintext space is equal to Fl2n , where l denotes the parallelism of the scheme. Decryption is similar as in the Smart-Vercauteren scheme but is adjusted to the bigger plaintext space. Decryption is given as Dec(c, sk) =
N −1 X
[czi ]p xi
mod 2,
i=0
and yields a polynomial in Z[x]/(F (x)) with F (x) a certain monic irreducible polynomial of degree N . And Z[x]/(F (x)) is homomorph to Fl2n . But again this SHE scheme is in itself not bootstrappable. The SHE scheme of the DGHV scheme is only based on integers, hence this scheme gives a conceptually simple FHE scheme. Here the plaintext space is again Z2 . Decryption is similar as in the Smart-Vercauteren case and is given as Dec(c, sk) = [c]p mod 2, the associated decryption circuit is less complex but nevertheless still not bootstrappable. B. Bootstrapping Why is this bootstrappability condition a sufficient condition to assure that a SHE scheme can be stated as allowing FHE? Before we tackle that question, let us define the Recrypt procedure. The recrypt procedure is no more and no less than the homomorphic evaluation3 of the decryption circuit function of the SHE scheme. We illustrate this process in figure 1. So the Recrypt([m]pk , [sk]pk , pk) procedure is able to return a new encryption of a message m, and has as inputs an encryption of m, an encryption of the bits of the representation 2 We assume addition ⊕ and multiplication ⊗ to be the fundamental gates which make up the circuit. 3 Evaluation of a polynomial using the Add and the Mult procedures.
Fig. 1. Recryption for a general decryption function Dec. The dark rectangles visualize data encrypted under the public key pkA . The output of the Recrypt circuit is a new ciphertext of the message m under pkA . In practice the pre-encryption of the old ciphertext can be omitted.
of the private key in the plaintext space4 and the public key itself. Let us now return to the question how this property of the SHE scheme could enable us to evaluate any circuit. Suppose we are given a circuit C that should be homomorphically evaluated on the encrypted data Ψ. Of course, if C ∈ CE than bootstrappability is not needed, so let us assume that C ∈ / CE . Then we can construct a circuit C ∗ , which is equivalent to C but is in CE . How do we transform C in C ∗ ? For every gate in the given circuit C, do the following: replace the gate by the decryption circuit of the to be used SHE scheme augmented5 with the replaced gate. Then correctness follows directly from the bootstrappability property of the used SHE scheme. This can be seen when we consider the use of the Recrypt procedure. We know that recryption plus one extra addition or multiplication is correct for all possible allowed ciphertexts. Now, since every gate is replaced with a Recrypt operation and an additional operation yielding, by definition, an allowed ciphertext, we have then that the circuit C ∗ will be correctly evaluated and hence C ∗ ∈ CE . In practice, for all mentioned schemes, the condition for whether a given circuit C is an element of CE is predominantly determined by the multiplicative depth of the circuit C. The depth of the given circuit C is denoted as d. Let dDec denote the depth of the decryption circuit (after squashing), then in practice we choose dmax = dDec + 1, as this yields the most performant schemes. C. Squashing As already mentioned, the SHE schemes are not bootstrappable by themselves. In [3], Gentry suggested lowering the decryption circuit complexity by starting the decryption by the encryptor using some hint about the private key f (sk, r). With r the random coins of the procedure producing the hint (KeyGen). The decryption circuit is transformed, using what Gentry calls a squashing operation, into a new decryption circuit of lower complexity. This process is visually represented in figure 2. Of course,it should be hard to exploit the extra information f (sk, r). This will require an additional security constraint. In practice, for all mentioned schemes, the transformation is done by hiding the private key in a subset sum problem 4 We
assume these ciphertexts to be computed during key generation. means do decryption before the replaced gate.
5 Augmentation
3
We implemented all optimizations bar the index encoding mechanism and we sticked to the naive polynomial evaluation method used in the Enc procedure. This mechanism is a tradeoff between the speed of recryption and the size of the public key (≈ s · S · |p|), which can become exceedingly large. Since the vast reduction of S, the necessity of the trade-off is less stringent. This reduces the complexity of the Recrypt circuit, and has the positive effect of allowing lower t, see “The bitsize t of the generating polynomial” in [7]. Adapting to these changes, but otherwise following the same security constraints as in [7], we propose following schemes:
Fig. 2. The squashing transformation. The initial decryption circuit Dec is divided into a computational intensive circuit Dec1 evaluated without the use of the private key, and a shallow circuit Dec2 evaluated with the use the private key.
(SSSP). The particularities of this transformation can be found in for example [4], and are not repeated here. III. I MPLEMENTATION We’re not going to give an exact description of how these mentioned FHE schemes work. But we limit ourselves to describing which optimizations and trade-offs, mentioned in the relevant articles, were taken account for in our implementation. Also in each of the following subsections we use, as much as possible, notation compatible with the relevant article. A. The Smart-Vercauteren scheme The scheme and optimizations are described in [7]. The main difference with our implementation concerns the selection of the SSSP. The authors consider a lattice reduction attack on the SSSP, but this attack assumes that the attacker has knowledge of the private key. This odd assumption is also criticised in [6]. More in particular it is stated that “If the adversary knows the private key, then recovering the solution of the SSSP should nevertheless be hard”. The main critique on this idea is the following: which attacker would ever attack the SSSP assuming he already is in possession of the private key? Taking a more pragmatic view on security, and therefore ignoring this last assumption, has however far reaching consequences. In [7] the parameter S of the subset is chosen big enough to withstand a birthday and a lattice reduction attack. Since those attacks are not possible in the more pragmatic view S should only obey S s ≥ 2λ . We have implemented a security level λ = 72 for all FHE schemes. Also assuming s = 15 for all schemes, we have selected S = 32. Notice that S had to be chosen much bigger in [7].
S M B
λ 72 72 72
µ 2.39 0.59 0.15
N 1024 4096 16384
t 210 210 210
(s, S) (15, 32) (15, 32) (15, 32)
B. The DGHV scheme The scheme and optimizations are described in [5]. Also here the SSSP is selected differently and the index encoding mechanism is omitted, for reasons stated above. To allow a fair comparison, we make the security assumptions as much as possible compatible with the reasoning followed in [7]. Therefore we take the same assumption on the hardness of bounded distance decoding problems (BDDPs) and shortest vector problems (SVPs). We assume that in time 2k a BDDP or SVP can be approximated to a factor of at most µ·N
2 k/ log(k) , with µ the lattice reduction hardness factor and N the dimension of the lattice problem. In the following we give the relevant security constraints using this assumption. a) Searching for the private key: Deduction of the private key out of the public key is an instance of the approximate greatest common divisor problem. In [5] an attack using lattice reduction is given. Applying the same reasoning, but with the altered SVP hardness assumption, gives us the following security constraint γ≥
η2 · λ , µ · log(λ)
with γ the bit length of the public integers qi and η the bit length of the public integer p. b) One-wayness of encryption: In the DGHV scheme the ciphertext is generated using aPsparse sum of the public integers xi , c = m + 2 · r + 2 u∈S xu mod x0 . In [5] an attack using lattice reduction is given. Applying the same reasoning, but with the altered SVP hardness assumption, gives us the following security constraint τ2 ≥
γ·λ , µ · log(λ)
with τ the number of public integers xi . Adapting to these changes, but otherwise following the same security constraints as in [5], we propose following schemes:
4
λ 72 72 72
S M B
µ 2.39 0.59 0.15
α 11 11 11
ρ 72 72 72
η 2500 2500 2500
γ 27.7 112.3 441.8
(s, S) (15, 32) (15, 32) (15, 32)
in which γ is given in [MiB]. C. The SIMD scheme The scheme and optimizations are described in [6]. We implemented all optimizations and Recrypt versions mentioned in this article. However we propose a fourth recryption method, which solves the problem of having to encrypt the bits of [sk]pk l times. The next part is again compatible with notation given in [6]. An alternative method for doing a recryption goes as follows: we have that (i )
qk 2 :=
S−1 X k=0
(i )
σk,j ⊗ Γn,l (0, . . . , 0, 1, 0, . . . , 0) · bk,j2 ,
where σk,j are the bits of the private key encrypted under (i ) pk and bk,j2 for i2 = [1, . . . , l] are the (plaintext) bits of the squashing information. The key to this alternative method is that we represent the squashing information directly as elements of Fl2n . Therefore, we define simd yk,i
=
l−1 X
i2 =0
bsimd k,i
=
l−1 X
i2 =0
(i )
yk,i2 · Γn,l (0, . . . , 0, 1, 0, . . . , 0) |α , (i )
bk,i2 · Γn,l (0, . . . , 0, 1, 0, . . . , 0) |α ,
explicitly making use of the SIMD properties of the SHE scheme. Such that we can compute qksimd :=
S−1 X k=0
slower than the equivalent procedure in the Smart-Vercauteren scheme. We will compare this scheme with the other schemes by comparing the second version of the recryption procedure with the third and the alternative version. This is possible by the fact that the recryption in the second version is practically the same as n · l recryptions of the n · l Smart-Vercauteren ciphertexts. We propose following schemes: m 127 585 511 1023 2255 2047
T alg4 ≈ s · S · (Tb + T⊕ ) · l · pb + s · S · (T⊕ + T⊗ ) pb
with T⊗ the time it takes to do a multiplication in Zp . Now it can be seen that this method requires slightly more operations (depending on l) since T alg4 − T alg3 ≈ pb · s · (T⊕ (S − l) + S · T⊗ ) .
But the alternative method is much more memory efficient, since it requires only 1 encryption of σk,j and the precomputation of Γn,l (0, . . . , 0, 1, 0, . . . , 0). Computing bsimd k,j , in both the original and alternative version, requires nearly the same number of operations. But computation in the latter version is actually much more memory friendly and hence faster. One major drawback of the SIMD scheme is the slow KeyGen procedure, which can be up to a 100 times
t 380 380 380 380 380 380
S 32 32 32 32 32 32
s 15 15 15 15 15 15
For practical reasons (see KeyGen timings) the lattice dimension m was chosen to be to small to be called secure, so comparison will be based on extrapolated results. Also we assume n = 1, since this will cause no efficiency difference between the different versions. IV. E VALUATION As already said, all mentioned FHE schemes were implemented using the high level scripting language Magma [8]. The implemented code was run on machines with each an Intel Xeon Quad core CPU (X7350) running at 2.93GHz and 8 GiB of memory, running Debian GNU/Linux 6. We start with giving the obtained performance measurements. As these methods are inherently random, the results are subjected to random variation, but the relative difference was seldom bigger then 5 %. A. Smart-Vercauteren scheme The results for the schemes given in section III-A, timing results are given in seconds and size results are given in [MiB], see [9].
σk,j ⊗ bsimd k,j ,
after which the rest of the operations are the same as in the 1 bit Smart-Vercauteren recryption procedure. The time necessary to compute qksimd is then
l 18 24 48 60 80 176
S M B
KeyGen [s] 29 402 7018
Enc [s] 0.04 0.29 1.92
Dec [s] 0.05 0.40 2.61
Recrypt [s] 5 39 216
|pk| [MiB] 40 479 6910
It can be seen from the implementation results that Enc and Dec have a negligible impact on timing results, and hence are not further discussed. B. DGHV scheme The results for the schemes given in section III-C, timing results are given in seconds and size results are given in [MiB], see [9].
S M B
KeyGen [s] 39 161 649
Enc [s] 773 4283 21912
Dec [s] 0.14 0.65 2.85
Recrypt [s] 3680 20243 95228
|pk| [GiB] 01.62 06.56 25.82
It can be seen from the implementation results that Dec has a negligible impact on timing results, and hence is not further discussed.
5
C. SIMD scheme The results for the schemes given in section III-C, timing results are given in seconds and size results are given in [MiB], see [9]. m 127 585 511 1023 2255 2047
V2 [s] 10 46 173 318 1754 5206
V3 [s] 2 5 15 26 121 316
V4 [s] 2 7 18 26 110 248
|pk2 | [MiB] 3.68 10.7 20.5 32.8 163.7 244.8
|pk3 | [MiB] 50.33 155.1 493.2 805.8 2929 7658
|pk4 | [MiB] 3.58 10.4 19.5 31.2 157.9 229.3
We notice immediately that the SIMD formulation of the Recrypt procedures pays of in versions V3 and V4 when looking at the timing results. However the public key size grows beyond control in version V3 , a problem that is solved by our alternative version V4 . Key generation however remains quite slow: m 127 585 511 1023 2255 2047
KeyGen V2 [s] 16.9 222.9 821.1 2237 40137 79096
KeyGen V3 [s] 31.6 293.2 1171 3012 48474 105408
KeyGen V4 [s] 23.4 256.4 1011 2806 47110 101900
scheme, or the Smart-Vercauteren scheme will depend on the number of recryptions that needs to be done. VI. C ONCLUSION Concerning the comparison between the Smart-Vercauteren and the DGHV scheme, we conclude that the former is superior to the latter, both in time efficiency and memory consumption. The difference with the conclusion in [5] is due to an unfair comparison between the 2 schemes when evaluating the security of both schemes. Concerning the SIMD scheme, we have shown that the alternative recryption method is in all cases less memory consuming for similar time efficiency. Especially in situations were the needed parallelism is high, this alternative version becomes very attractive. When comparing the SIMD scheme and the SmartVercauteren scheme, a distinction has to be made between the Recrypt methods and the KeyGen methods. The Recrypt method is for both the V3 and V4 version of the SIMD scheme faster than n · l recryptions of ciphertexts using the Smart-Vercauteren scheme. Naturally the SIMD formulation requires less ciphertexts, and hence less memory to store data. However, the KeyGen method is in the SIMD scheme much slower than in the Smart-Vercauteren scheme. So the question of whether to use the SIMD scheme, or the Smart-Vercauteren scheme will depend on the number of recryptions that needs to be done.
V. D ISCUSSION
R EFERENCES
When comparing the results obtained in section IV-A and IV-B, it is immediately clear that the Smart-Vercauteren scheme is superior to the DGHV scheme. The difference between this analysis and the one given in [5] is explained by the fact that, when translated to our security assumptions, they compare a DGHV scheme chosen assuming µ ≈ 28 to a Smart-Vercauteren scheme chosen assuming µ = {0.14, 0.54, 2.34}. The conclusion of our analysis therefore states that the Smart-Vercauteren variant is both faster and less memory consuming. By not implementing the more complex method for batch evaluation of polynomials, as given in [7], the public key size in the Smart-Vercauteren scheme grows faster for changing µ than the public key size in the DGHV scheme. Implementing the more complex method could resolve this problem, but this will have its repercussions on the speed of encryption. Comparing the SIMD scheme with the Smart-Vercauteren scheme is a bit more difficult. The question is whether the SIMD construction offers an alternative over working with n · l different Smart-Vercauteren ciphertexts. The Recrypt procedure of version V2 is as time consuming as recrypting n · l different ciphertexts. Therefore recryption timings of V2 shall be used as the control. The results offered in section IV-C show clearly that, for m < 2047, versions V3 and V4 outperform n · l recryptions of the Smart-Vercauteren scheme. However, when turning to the KeyGen procedure, we notice that the SIMD scheme is, compared to the Smart-Vercauteren scheme, very slow. So the question of whether to use the SIMD
[1] Wikipedia, “Circuit — Wikipedia, the free encyclopedia,” 2011, [Online; accessed 04-June-2011]. [Online]. Available: http://en.wikipedia.org/wiki/Circuit (computer theory) [2] R. Rivest, L. Adleman, and M. Dertouzos, “On data banks and privacy homomorphisms,” Foundations of Secure Computation, pp. 169–180, 1978. [3] C. Gentry, “A fully homomorphic encryption scheme,” Ph.D. dissertation, Stanford University, 2009. [4] N. Smart and F. Vercauteren, “Fully homomorphic encryption with relatively small key and ciphertext sizes,” Cryptology ePrint Archive, Report 2009/571, 2009, http://eprint.iacr.org/. [5] M. van Dijk, C. Gentry, S. Halevi, and V. Vaikuntanathan, “Fully homomorphic encryption over the integers,” Cryptology ePrint Archive, Report 2009/616, 2009, http://eprint.iacr.org/. [6] N. Smart and F. Vercauteren, “Fully homomorphic simd operations,” Cryptology ePrint Archive, Report 2011/133, 2011, http://eprint.iacr.org/. [7] C. Gentry and S. Halevi, “Implementing gentry’s fully homomorphic encryption scheme,” August 2010, preliminary Report. [8] W. Bosma, J. Cannon, and C. Playoust, “The Magma algebra system. I. The user language,” J. Symbolic Comput., vol. 24, no. 3-4, pp. 235–265, 1997, computational algebra and number theory (London, 1993). [Online]. Available: http://dx.doi.org/10.1006/jsco.1996.0125 [9] NIST, “Prefixes for binary multiples,” 2000, [Online; accessed 31-May2011]. [Online]. Available: http://physics.nist.gov/cuu/Units/binary.html
Bibliografie [BCP97]
Wieb Bosma, John Cannon, and Catherine Playoust. The Magma algebra system. I. The user language. J. Symbolic Comput., 24(3-4):235– 265, 1997. Computational algebra and number theory (London, 1993).
[BMM00]
J. Buchmann, M. Maurer, and B Möller. Cryptography based on number fields with large regulator. Journal de Théorie des Nombres de Bordeaux 12, 2000.
[Coh95]
Henri Cohen. A Course in Computational Algebraic Number Theory. Springer, 1995. ISBN: 3-5405-5640-0.
[Cop97]
Don Coppersmith. Small solutions to polynomial equations, and low exponent rsa vulnerabilities. Journal of Cryptology, 10:233–260, 1997. 10.1007/s001459900030.
[DH76]
Whitfield Diffie and Martin E. Hellman. New directions in cryptography, 1976.
[Gen09a]
Craig Gentry. A Fully Homomorphic Encryption Scheme. PhD thesis, Stanford University, 2009.
[Gen09b]
Craig Gentry. Fully homomorphic encryption using ideal lattices. In Proceedings of the 41st annual ACM symposium on Theory of computing, STOC ’09, pages 169–178, New York, NY, USA, 2009. ACM.
[GH10]
Craig Gentry and Shai Halevi. Implementing gentry’s fully homomorphic encryption scheme. Preliminary Report, August 2010.
[GN08]
Nicolas Gama and Phong Q. Nguyen. Predicting lattice reduction. In Proceedings of the theory and applications of cryptographic techniques 27th annual international conference on Advances in cryptology, EUROCRYPT’08, pages 31–51, Berlin, Heidelberg, 2008. Springer-Verlag. 97
Bibliografie [HPS98]
Jeffrey Hoffstein, Jill Pipher, and Joseph Silverman. Ntru: A ring-based public key cryptosystem. In Joe Buhler, editor, Algorithmic Number Theory, volume 1423 of Lecture Notes in Computer Science, pages 267–288. Springer Berlin / Heidelberg, 1998. 10.1007/BFb0054868.
[LMSV10]
J. Loftus, A. May, N.P. Smart, and F. Vercauteren. On cca-secure fully homomorphic encryption. Cryptology ePrint Archive, Report 2010/560, 2010. http://eprint.iacr.org/.
[Mol99]
Richard A. Mollin. Algebraic Number Theory. Chapman & Hall / CRC, 1999. ISBN: 0-8493-3989-8.
[NIS00]
NIST. Prefixes for binary multiples, 2000. [Online; accessed 31-May2011].
[PS10]
Clément Pernet and William Stein. Fast computation of hermite normal forms of random integer matrices. Journal of Number Theory, 130(7):1675 – 1683, 2010.
[RAD78]
R. Rivest, L. Adleman, and M Dertouzos. On data banks and privacy homomorphisms. Foundations of Secure Computation, 1978.
[RSA78]
R. L. Rivest, A. Shamir, and L. Adleman. A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM, 21:120–126, 1978.
[SA64]
Irene A Stegun and Milton Abramowitz. Handbook of mathematical functions with formulas, graphs, and mathematical tables. Dover books on intermediate advanced mathematics. US. Nat. Bureau Stand., New York, NY, 1964.
[SV09]
N.P. Smart and F. Vercauteren. Fully homomorphic encryption with relatively small key and ciphertext sizes. Cryptology ePrint Archive, Report 2009/571, 2009. http://eprint.iacr.org/.
[SV11]
N.P. Smart and F. Vercauteren. Fully homomorphic simd operations. Cryptology ePrint Archive, Report 2011/133, 2011. http://eprint. iacr.org/.
[vDGHV09] Marten van Dijk, Craig Gentry, Shai Halevi, and Vinod Vaikuntanathan. Fully homomorphic encryption over the integers. Cryptology ePrint Archive, Report 2009/616, 2009. http://eprint.iacr.org/. [Wik11]
98
Wikipedia. Public-key cryptography — Wikipedia, the free encyclopedia, 2011. [Online; accessed 17-May-2011].
K.U.Leuven Faculteit Ingenieurswetenschappen
2010 – 2011
Fiche masterproef Student: Bart P.G. Van Parys Titel: Volledig Homomorfe Encryptie Engelse titel: Fully Homomorphic Encryption UDC : 621.3 Korte inhoud: Recent in 2009, heeft Gentry het eerste volledig homomorfe encryptie schema uitgevonden. Hiermee eindigde hij de zoektocht van bijna 40 jaar naar een eerste volledig homomorf schema. Sindsdien zijn er een aantal volledig homomorfe schema’s opgesteld. Echter, een vergelijking tussen deze constructies heeft nog niet plaatsgevonden. Het eerste doel van deze masterproef is dan ook om de voorgestelde schema’s aan een eerlijke vergelijking te onderwerpen. Meer in het bijzonder worden in deze thesis 2 fundamentele schema’s vergeleken: de Smart-Vercauteren variant en de DGHV variant. De Smart-Vercauteren variant is een concrete instantie van het oorspronkelijke Gentry schema, beschreven in getallenvelden. De DGHV variant is een schema dat enkel gebruikmaakt van gehele getallen. Uit de gedane tijdmetingen valt te besluiten dat de Smart-Vercauteren variant performanter is dan de DGHV variant, ondanks wat de desbetreffende auteurs publiceerden. De SIMD variant is een volledig homomorf schema dat SIMD operaties toelaat. Deze variant is een natuurlijke veralgemening van de achterliggende idee gebruikt in de Smart-Vercauteren variant. Ook deze variant wordt vergeleken met de SmartVercauteren en DGHV variant; we beschouwen hierbij 3 verschillende versies om een boodschap te hersleutelen. We stellen ook een nieuwe hersleutelversie voor, die zeer performant blijkt wanneer het beoogde parallellisme groot is. Ook qua geheugen is deze versie zeer competitief in vergelijking met de andere versies. Er kan opgemerkt worden dat zelfs het meest performante schema beschreven in de literatuur bezwaarlijk praktisch performant kan worden genoemd. Daarom wordt finaal een praktisch schema voorgesteld dat, gebruikmakend van 2 vertrouwde hulpservers, wel praktisch haalbaar kan worden genoemd. Ook dit schema is voor een groot stuk gebaseerd op de Smart-Vercauteren variant. Wel kan opgemerkt worden dat dit schema natuurlijk extra veronderstellingen omtrent de veiligheid zal moeten gebruiken.
Thesis voorgedragen tot het behalen van de graad van Master in de ingenieurswetenschappen: wiskundige ingenieurstechnieken Promotor: Prof. Dr. Ir. Bart Preneel Assessoren: Prof. Dr. Ir. M. Van Barel Prof. Dr. Ir. J. Vandewalle Begeleiders: Dr. Ir. F. Vercauteren Ir. J. Hermans
