Homomorf kryptering

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 28 mars 2015; kontroller kräver 44 redigeringar .

Homomorf kryptering  är en form av kryptering som gör att du kan utföra vissa matematiska operationerchiffertexten och få ett krypterat resultat som matchar resultatet av operationer som utförs på klartexten . En person kunde till exempel lägga till två krypterade siffror utan att känna till de dechiffrerade siffrorna, och sedan kunde en annan person dechiffrera den krypterade summan - få det dechiffrerade beloppet utan att ha de dechiffrerade talen. Homomorf kryptering skulle tillåta olika tjänster att tillhandahållas utan att tillhandahålla offentliga användardata för varje tjänst.

Det finns kryptosystem delvis homomorfa och helt homomorfa. Ett delvis homomorft kryptosystem låter dig utföra endast en av operationerna - antingen addition eller multiplikation . Ett helt homomorft kryptosystem stöder båda operationerna, det vill säga det uppfyller egenskaperna hos homomorfism med avseende på både multiplikation och addition.

Historik

Begreppet "homomorf kryptering" bildades först [1] 1978 av Ronald Rivest , Leonard Adleman och Michael Dertouzos  , författarna till RSA-algoritmen ett år efter utvecklingen av algoritmen. De föreslog möjligheten att utföra godtyckliga operationer på krypterad data utan att dekryptera den.

Vid den tiden var försöken att skapa ett helt homomorft kryptosystem inte framgångsrika. Till exempel, 1982, föreslog Shafi Goldwasser och Silvio Micali ett krypteringssystem som är homomorft under multiplikation och som kan kryptera bara en bit. Ett annat kryptosystem homomorft med avseende på multiplikation föreslogs 1999 av Pascal Peyet .

2005 föreslog Dan Bone , Yu Jin Guo och Kobi Nissim [2] ett kryptosystem baserat på användningen av bilinjära parningar på elliptiska kurvor , vilket tillåter ett obegränsat antal additionsoperationer och en multiplikationsoperation.

Problemet med att skapa ett kryptosystem som är homomorft med avseende på både additions- och multiplikationsoperationer har förblivit olöst i över 30 år.

2009 underbyggde Craig Gentry , en doktorand vid Stanford University och en praktikant vid IBM , teoretiskt den grundläggande möjligheten att skapa ett helt homomorft krypteringskryptosystem och föreslog ett sådant system . Det föreslagna systemet kan användas för att säkerställa konfidentialitet för data under alla typer av databehandling i opålitliga miljöer, till exempel i moln eller distribuerad datoranvändning.

Snart dök det upp arbete som föreslog prestandaförbättrande modifieringar av Gentrys kryptosystem .

Kryptografer arbetar på alternativa sätt att bygga helt homomorfa kryptosystem, som att använda symmetrisk kryptering istället för kryptering med offentlig nyckel, använda polynom i en eller flera variabler, använda matrispolynom.

Allmän syn på homomorf kryptering

Homomorf kryptering är en form av kryptering som gör att en specifik algebraisk operation kan utföras på klartexten genom att utföra en algebraisk operation på chiffertexten.

Låt vara  krypteringsnyckeln,  vara vanlig text (meddelande) som ska krypteras och vara  funktionen som utför krypteringen.

En funktion kallas homomorf med avseende på operationen " " (addition eller multiplikation) över klartexter (meddelanden) och om det finns en effektiv algoritm (kräver ett polynomantal resurser och körs i polynomtid ), som, efter att ha mottagit ett par av chiffertexter i formen och som indata producerar en krypterad text (chiffertext, kryptogram) så att när de krypteras kommer klartext att erhållas [3] .

I praktiken övervägs oftare följande specialfall av homomorf kryptering.

Låt för den givna krypteringsfunktionen och operationen " " på klartexter och det finns en operation " " på chiffertexter, så att klartexten extraheras från chiffertexten när den dekrypteras . Detta kräver att givet , , , men med en okänd nyckel , skulle det vara omöjligt att effektivt kontrollera att chiffertexten erhölls från och .

Alla standardkrypteringssystem kan beskrivas genom att beskriva tre operationer: en nyckelgenereringsoperation ( keyGen ), en krypteringsoperation ( encypt ) och en dekrypteringsoperation ( decrypt ) [4] .

För att beskriva ett homomorft krypteringssystem, utöver de tre operationerna som anges ovan, är det nödvändigt att beskriva beräkningsoperationen ( eval ). Användningen av homomorf kryptering innebär användning av en sekvens av fyra operationer: nyckelgenerering, kryptering, beräkning, dekryptering:

  1. nyckelgenerering  - generering av klienten av en offentlig nyckel ( public key ) (för att dekryptera den krypterade klartexten) och en hemlig nyckel ( hemlig nyckel ) (för att kryptera den vanliga texten);
  2. kryptering  - klient kryptering av klartext ( ren text ) med hjälp av en hemlig nyckel  - beräkning av chiffertext ( chiffertext ) ; skicka klientens chiffertext och publik nyckel till servern;
  3. beräkning  - ta emot funktionen av servern , använda och utföra beräkningar på chiffertexten ; sända resultatet av servern till klienten;
  4. dekryptering  - dekryptering av klienten av värdet som tas emot från servern med .

Låt vara  krypteringsfunktionen;  - expansionsfunktion; och  — klartexter; symbolerna " " och " " betecknar multiplikations- och additionsoperationer på chiffertexter, motsvarande operationer för multiplikation och addition på vanlig text.

Ett krypteringssystem är homomorft med avseende på multiplikationsoperationen (har multiplikativa homomorfa egenskaper) om

Ett krypteringssystem är homomorft med avseende på additionsoperationen (har additiva homomorfa egenskaper) om

Ett krypteringssystem är homomorft med avseende på multiplikations- och additionsoperationer, det vill säga helt homomorft (har både multiplikativa och additiva homomorfa egenskaper) om

Om ett kryptosystem med dessa egenskaper kan kryptera två bitar, blir det möjligt att beräkna vilken boolesk funktion som helst , eftersom operationerna addition och multiplikation bildar en Turing-komplett bas över bitarna, och därmed vilken annan beräkningsbar funktion som helst .

Applikationer

Molntjänster

Homomorf kryptering öppnar upp för nya möjligheter för att bevara integriteten, tillgängligheten och konfidentialitet för data när den bearbetas i molnsystem. Inom cloud computing , där prestanda är en högsta prioritet, bör olika algoritmer användas, som var och en bäst utför uppgiften. Till exempel, för multiplikationsoperationer av krypterad data, är det tillrådligt att använda RSA-algoritmen eller ElGamal-algoritmen , och för tillägg, Peye- algoritmen . Vid användning av ett helt homomorft krypteringssystem bör antalet operationer som kan utföras på data begränsas, eftersom som ett resultat av beräkningarna ackumuleras vissa fel . Om felvärdet överstiger värdet för den hemliga parametern är det möjligt att data inte kan dekrypteras korrekt.

Elektronisk röstning

Elektronisk röstning  är ett annat lovande användningsområde för homomorf kryptering. Systemet kommer att kunna kryptera väljarnas röster och utföra beräkningar på krypterad data, samtidigt som väljarnas anonymitet bibehålls. Till exempel, i Benalos e-röstningsschema, inkluderar röstningsprocessen följande steg [5] :

  1. varje röstande deltagare i systemet delar upp sin röst (hemlig) i komponenter (delvisa hemligheter) enligt motsvarande hemlighetsdelningsschema med tillägget homomorfism-egenskap och skickar partiella hemligheter till valda representanter;
  2. företrädare lägger ihop sina röster; schemat är homomorft, och därför är röstsummorna delvis hemligheter av motsvarande valresultat;
  3. huvudförvaltaren beräknar den slutliga röstsumman med hjälp av den uppsättning delröster som den har fått av de förtroendevalda.

Betrakta ett exempel på hur detta tillvägagångssätt kan implementeras.

Låt det finnas en uppsättning kandidater från vilka listan som ingår i omröstningen bildas. Omröstningsinitiatorn har ett kryptosystem som är homomorft med avseende på additionsoperationen, fördelar bland deltagarna i den hemliga omröstningen den offentliga nyckeln till det homomorfa krypteringssystemet och valsedeln som en vektor där  är efternamnet på den -e kandidaten. Var och en av väljarna gör en vektor av preferenser där var och en av väljarna , med hjälp av den offentliga nyckeln, krypterar vektorn element för element och skickar den till initiativtagaren av omröstningen. För att summera resultatet av omröstningen utför han beräkningar på motsvarande element i de mottagna preferensvektorerna och dekrypterar med den hemliga nyckeln . Eftersom kryptosystemet är homomorft med avseende på additionsoperationen, kommer indexen för de största elementen i den resulterande vektorn att vara indexen för de vinnande kandidaterna.

Säker informationssökning

Homomorf kryptering kan ge användare möjligheten att extrahera information från sökmotorer med bibehållen konfidentialitet: tjänster kommer att kunna ta emot och bearbeta förfrågningar, samt utfärda bearbetningsresultat utan att analysera och fixa deras verkliga innehåll. Till exempel kan en metod för att extrahera poster från en databas genom deras index representeras enligt följande.

Låt vara  indexet för posten som ska hämtas; ;  - alla indexerade poster från databasen.

Sedan, för att välja önskad post, är det nödvändigt att beräkna följande funktion :

Om alla är krypterade med ett homomorft kryptosystem kan man beräkna homomorfiskt över chiffertexter. För att göra detta räcker det för klienten att bit för bit kryptera indexet för posten han behöver och skicka det till servern. Resultatet av en homomorfisk utvärdering av en funktion över chiffertexter kommer att vara det önskade chiffervärdet för posten som begärs av klienten. Uppenbarligen måste ett kryptosystem ha både multiplikativa och additiva homomorfa egenskaper.

Skydd av trådlösa decentraliserade kommunikationsnätverk

Trådlösa decentraliserade självorganiserande nätverk ( MANET ) är nätverk som består av mobila enheter. Varje sådan enhet kan självständigt röra sig i vilken riktning som helst och, som ett resultat, ofta bryta och upprätta förbindelser med närliggande enheter. Ett av huvudproblemen med att bygga MANET är att säkerställa säkerheten för överförda data. För att lösa detta problem kan homomorf kryptering användas, som är inbyggd i routingprotokoll för att förbättra säkerheten. I det här fallet kan operationer på chiffertexter utföras säkert av mellanliggande noder. I synnerhet, för att hitta den optimala vägen mellan två noder, är det nödvändigt att utföra linjära operationer på krypterad data utan att dekryptera den. Närvaron av homomorf kryptering tillåter inte en angripare att hitta en koppling mellan meddelanden som kommer in i noden och meddelanden som lämnar noden. Därför är det inte möjligt att spåra sökvägen till ett meddelande med hjälp av trafikanalys [6] .

Outsourcingtjänster för smartkort

Den nuvarande trenden är att utveckla universella kort med sitt eget operativsystem , som kan utföra en mängd olika funktioner och interagera med flera tjänsteleverantörer. Det har spekulerats i att vissa applikationer kan köras utanför kartan på homomorfiskt krypterade data. Särskilt resurskrävande applikationer, såsom tjänsteleverantörsapplikationer, såväl som biometriska verifieringar ( röst , fingeravtryck eller handskriftsigenkänning ), som vanligtvis kräver en betydande mängd data och ett stort antal relativt enkla operationer, kan använda externa lagringsenheter och externa processorer , kraftfullare än den inbyggda processorn i kortet.

Återkopplingssystem

Homomorf kryptering kan användas till exempel i de så kallade säkra homomorfa återkopplingssystemen när det är nödvändigt att bevara användarens anonymitet och dölja mellanresultaten av beräkningar .  System hjälper till att anonymt samla in feedback (kommentarer) från elever eller lärare om deras arbete. Feedback som tas emot på detta sätt krypteras och lagras för efterföljande beräkningar. Feedbacksystem kan användas för att öka medvetenheten om sakernas tillstånd och för att förbättra prestandan. Det har fastställts att tillförlitlig återkoppling av alla system eller processer endast kan tillhandahållas i fall av att upprätthålla användarens anonymitet, oföränderligheten hos de insamlade uppgifterna och säkerställa säkerheten för intern verksamhet för dataanalys.

Obfuskation för att skydda mjukvaruprodukter

Huvudsyftet med obfuskering är att göra det svårt att förstå hur programmet fungerar. Eftersom alla traditionella datorarkitekturer använder binära strängar, genom att tillämpa helt homomorf kryptering över bitar, kan vilken funktion som helst beräknas. Därför är det möjligt att homomorfiskt kryptera hela programmet så att det behåller sin funktionalitet.

Delvis homomorfa system

Partiellt homomorfa kryptosystem är kryptosystem som är homomorfa med avseende på endast en operation, antingen additionsoperationen eller multiplikationsoperationen. I exemplen nedan betecknar uttrycket användningen av krypteringsfunktionen för att kryptera klartexten (meddelandet) .

RSA-kryptosystemet

RSA - kryptosystemet är ett kryptografiskt system med offentlig nyckel som är homomorft i multiplikation. Låt vara  RSA-modulen,  vara klartext  och vara den offentliga nyckeln (för att kryptera klartexten). Krypteringsfunktionen ser ut som . Låt oss visa homomorfismen genom multiplikation:

Cryptosystem of ElGamal

ElGamal-kryptosystemet är ett alternativ till RSA-kryptosystemet och ger med samma nyckelvärde samma kryptografiska säkerhet . ElGamal förbättrade Diffie-Hellman-algoritmen och erhöll algoritmer för kryptering och för att tillhandahålla autentisering. Ett kryptosystem är ett probabilistiskt krypteringskryptosystem. Dess krypteringsfunktion är homomorf med avseende på klartextmultiplikationsoperationen: ett produktkryptogram kan beräknas som en (parvis) produkt av kryptogram av faktorer. Låt vara  krypteringsfunktionen; och  — klartexter. Om och då kan erhållas i formuläret .

Goldwasser-Micali kryptosystem

I Goldwasser-Micali-kryptosystemet , om modulen är den publika nyckeln, är bitkrypteringsfunktionen för det slumpmässiga elementet . Då är detta kryptosystem homomorft för driften av multiplikation: där symbolen " " anger operationen av additionsmodulo 2 .

Peyes kryptosystem

I Peye-krypteringssystemet , om den publika nyckeln är en modulo och  är ett slumptal, representeras funktionen att kryptera ett meddelande (klartext) som en slumpmässig variabel . Sedan bevisas homomorfismen genom addition enligt följande:

Cryptosystem of Benalo

I Benalos kryptosystem , om den publika nyckeln är en modul , representeras den klartext krypteringsfunktionen som för slumpmässig . Sedan bevisas homomorfismen genom addition enligt följande:

Andra delvis homomorfa kryptosystem

Fullständigt homomorf kryptering

Delvis homomorfa kryptosystem tillåter att utföra homomorfa beräkningar för endast en operation (antingen addition eller multiplikation) av klartext. Ett kryptosystem som stöder både addition och multiplikation (och därmed bevarar strukturen i klartextring ) är känt som helt homomorf kryptering och är kraftfullare. Genom att använda ett sådant system kan vilket schema som helst utvärderas homomorfiskt, vilket möjliggör ett effektivt skapande av program som kan köras på ingångskryptering för att producera utkryptering. Eftersom ett sådant program aldrig kommer att dekryptera sin indata, kan det köras av en opålitlig part utan att visa dess input och interna tillstånd. Förekomsten av ett effektivt och helt homomorft kryptografiskt system skulle få stora praktiska konsekvenser vid outsourcing av privata datorer, till exempel i samband med molnberäkning [7] . Homomorf kryptering skulle tillåta olika tjänster att kombineras till en utan att tillhandahålla data för varje tjänst. Till exempel kan en kombination av olika företags tjänster konsekvent beräkna skatten, tillämpa den aktuella växelkursen, skicka in en transaktionsbegäran, utan att tillhandahålla faktiska uppgifter för var och en av dessa tjänster [8] . Den homomorfa egenskapen hos olika kryptografiska system kan användas för att skapa säkra röstningssystem [9] , kollisionsbeständiga hashfunktioner, sökmotorskyddad information och möjliggöra utbredd användning av offentliga molnberäkningar genom att garantera konfidentialitet för bearbetade data.

Prestandaproblem och lösningar

Ett av de betydande problemen med kända fullt homomorfa kryptosystem är deras extremt låga prestanda. För närvarande finns det två huvudsakliga sätt att förbättra prestandan: användningen av "begränsad fullständigt  homomorf kryptering " [10] och användningen av den så kallade "chiffertextpackningsmetoden" [11] . Den första innebär ett kryptosystem som kan utföra additions- och multiplikationsoperationer, men i ett begränsat antal. Kärnan i den andra är att flera klartexter skrivs till en chiffertext samtidigt, och samtidigt, under en enda operation av en sådan batchchiffertext, bearbetas alla chiffertexter som ingår i den samtidigt.

Se även

Anteckningar

  1. Ronald L. Rivest, Len Adleman, Michael L. Dertouzos. Om databanker och integritetshomomorfismer . Academic Press (1978). Arkiverad från originalet den 25 maj 2013.  
  2. Dan Boneh, Eu-Jin Goh, Kobbi Nissim. Utvärdera 2-DNF-formler på  chiffertexter . Springer-Verlag (2005). Arkiverad från originalet den 25 maj 2013.
  3. Varnovsky, N. P.  Homomorf kryptering / N. P. Varnovsky, A. V. Shokurov // Proceedings of the Institute for System Programming of the Russian Academy of Sciences. – 2006.
  4. Undersökning av olika homomorfa krypteringsalgoritmer och scheman / PV Parmar [et al.] // Intern. J. av datortillämpningar. - 2014. - Vol. 91, nr. åtta.
  5. Shenets, N. N.  Modulär hemlighetsdelning och elektroniskt röstningssystem / N. N. Shenets // Bulletin of BSU. Ser. 1. - 2011. - Nr 1.
  6. Gabidulin, E. M.  Informationssäkerhet i telekommunikationsnätverk / E. M. Gabidulin, N. I. Pilipchuk, O. V. Trushina // Proceedings of the Moscow Institute of Physics and Technology. - 2013. - V. 5, nr 3.
  7. Daniele Micciancio. A First Glimt of Cryptography's Holy Grail  (Eng.) 96. Association for Computing Machinery (1 mars 2010). Arkiverad från originalet den 24 maj 2013.
  8. Craig Stuntz. Vad är homomorf kryptering, och varför ska jag bry mig?  (engelska) (18 mars 2010). Arkiverad från originalet den 24 maj 2013.
  9. Ron Rivest. Lecture Notes 15: Voting, Homomorphic Encryption  (engelska) (29 oktober 2002). Arkiverad från originalet den 24 maj 2013.
  10. Brakerski Z., Gentry C., Vaikuntanathan V. (Leveled) fullständigt homomorf kryptering utan bootstrapping  //  Teoretisk datavetenskap. - 2012. - S. 309-325 .
  11. Burtyka F. B. Paketsymmetrisk helt homomorf kryptering baserad på matrispolynom  // Proceedings of Institute of System Programming. Volym 26. - 2014. - Nr 5 . - S. 99-115 .

Litteratur

Länkar