Confidential Computing Protocol

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 27 november 2017; kontroller kräver 7 redigeringar .

Inom kryptografi är ett konfidentiellt beräkningsprotokoll (även säker, säker eller hemlig flerpartsberäkning, eng. säker flerpartsberäkning ) ett kryptografiskt protokoll som tillåter flera deltagare att utföra en beräkning som beror på hemliga indata för var och en av dem , på ett sådant sätt att ingen deltagare kunde få någon information om någon annans hemliga input. För första gången togs problemet med konfidentiell data upp av Andrew Yao 1982 i artikeln [1] . Två miljonärer, Alice och Bob, vill ta reda på vem av dem som är rikare, samtidigt som de inte vill avslöja den exakta summan av deras förmögenhet. Yao föreslog i sin artikel ett originellt sätt att lösa detta problem, som senare blev känt som problemet med miljonärer . Långt senare, 2004, gav Yehuda Lindell och Benny Pinkas ett matematiskt rigoröst bevis på riktigheten av Yaos protokoll i [2] . Problemet med konfidentiell beräkning är nära relaterat till problemet med hemlig delning .

Formaliserad problemformulering

N deltagare p 1 , p 2 , …, p N deltar i konfidentiell beräkning . Varje deltagare har hemliga indata di , d2 , …, dN respektive . Deltagarna vill hitta värdet F(d 1 , d 2 , …, d N ) , där F är en beräkningsbar funktion av N argument kända för alla deltagare . Det antas att det kommer att finnas halvärliga brottslingar bland deltagarna , det vill säga de som troget följer protokollet, men försöker få ytterligare information från eventuella mellanliggande data.

Säkerhetskrav

Säkerhetskrav för konfidentiella datorprotokoll har vanligtvis olika säkerhetskrav beroende på situationen. Här är de viktigaste kraven.

Sekretess. Ingen av deltagarna ska kunna få mer information än vad de föreskrivs.
Rätthet. Varje deltagare måste garanteras att få rätt data.
Garanterad information. Deltagare ska inte kunna hindra andra deltagare från att få utdata.

Ett exempel på en lösning på problemet med miljonärer

Låt miljonärerna Alice och Bob vilja ta reda på vems förmögenhet som är större utan att avslöja den exakta summan av deras förmögenheter. För visshetens skull, anta att Alice har i miljon och Bob har j , där 1<i och j<10 . För det första kommer Alice och Bob att behöva ett starkt kryptosystem med publik nyckel , såsom RSA [3] . Låt E a vara en godtycklig krypteringsfunktion för nyckeln a och D a vara den privata nyckeldekrypteringsfunktionen för den publika nyckeln a . Låt en vara Alices publika nyckel. Då ser protokollet ut så här:

Bob väljer ett slumpmässigt heltal x från N bitar och beräknar konfidentiellt k=E a (x) ;
Bob skickar ett nummer k-j+1 till Alice ;
Alice betraktar konfidentiellt värdena y u =D a (k-j+u) för u=1,2,…,10 ;
Alice väljer ett slumpmässigt primtal p från N/2 bitar så att talen z u =y u mod(p) skiljer sig med minst 2 modulo p för alla u och skickar talet p till Bob;
Alice skickar nummer z 1 , z 2 , …, z i följt av nummer z i+1 +1, …, z 10 +1 ; tal tas modulo p;
Bob, som vet hur mycket pengar han har ( j ), jämför talet j med talet x mod p som valts i det första steget, och om de är lika, drar Bob slutsatsen att i ⩾ j , och i < j annars;
Bob rapporterar resultatet till Alice.

Det kan ses att protokollet låter dig entydigt bestämma vems tillstånd som är störst, och samtidigt kan deltagarna inte ta reda på varandras tillstånd.

Implementeringar

Det finns två olika metoder för att implementera protokollet. Det första tillvägagångssättet är vanligtvis baserat på hemlig delning och arbetar med representationen av den beräknade funktionen i form av en aritmetisk krets ( eng. aritmetisk krets ), som till exempel i BGW (Ben-Or, Goldwasser och Wigderson) [ 4] och CCD (Chaum, Crepeau och Damgard [5] . Detta tillvägagångssätt tillämpas vanligtvis när det är känt att majoriteten av deltagarna är ärliga (vilket bara är möjligt om antalet deltagare är fler än två). Ett annat tillvägagångssätt är att representera funktionen som ett logikdiagram . Detta tillvägagångssätt användes av Andrew Yao när han konstruerade en förvrängd krets ( engelsk förvrängd krets ) [6] , såväl som i GMW-protokollet (Goldreich, Micali och Wigderson) [7] .

Det aritmetiska schemametoden är bättre lämpad för att utföra additions- och multiplikationsoperationer (där deltagarna har andelar av hemligheten, och hemligheten endast kan återskapas om information tas emot från var och en av deltagarna), men är dåligt lämpad för att utföra jämförelseoperationer. Detta tillvägagångssätt har nått stora framgångar i SIMAP-projektet [8] .

Den logiska kretsmetoden utför additioner och multiplikationer med mindre effektivitet, men kan enkelt utföra binära operationer såsom jämförelser. Detta andra tillvägagångssätt, som Andrew Yaos tvåhandssystem är baserat på , implementerades av Mulchy i fairplay-systemet [9 ] . Detta system ger också möjligheten att implementera den nödvändiga funktionaliteten, representerad av ett högnivåprogrammeringsspråk i form av en logisk loop, som sedan tolkas av runtime-miljön och exekveras säkert. Det finns också ett system "FairplayMP" [10] , som är en förlängning av "Fairplay" när det gäller fler än två deltagare. En betydande fördel med metodbaserade system med logiska kretsar är att de utförs i ett konstant antal informationsutbyten, medan fördelen med system baserade på aritmetiska kretsar är möjligheten att utföra aritmetiska operationer (addition och multiplikation) mycket snabbt.

Protokollexempel

För enkelhetens skull, låt oss anta att två deltagare deltar i beräkningen, det vill säga N=2 , och deltagarna behöver beräkna funktionen F .

Låt oss representera funktionen F i form av en logisk krets , det vill säga vi kommer att representera indata för funktionen F i binär form, och själva funktionen implementeras med operationerna AND, OR och NOT. Sedan matas bitarna av alla argument för funktionen F till ingången på den logiska kretsen , och själva kretsen består av logiska grindar AND, OR och NOT, och vid utgången producerar den resultatet av funktionen F i binärt format.
Deltagare p 1 genererar för varje tråd i logikkretsen två olika slumptal k 0 u k 1 . Siffrorna representerar den krypterade nollan respektive en på den tråden.
Deltagare p 1 skapar en krypterad beräkningstabell för varje schema. För en binär ELLER-grind skulle en sådan tabell se ut så här:

Ingångskabel w 1	Ingångskabel w 2	Utgångskabel w 3	Krypterad beräkningstabell
$k_{1}^{0}$	$k_{2}^{0}$	$k_{3}^{0}$	$c_{1}=E_{k_{1}^{0}}(E_{k_{2}^{0}}(k_{3}^{0}))$
$k_{1}^{0}$	$k_{2}^{1}$	$k_{3}^{1}$	$c_{2}=E_{k_{1}^{0}}(E_{k_{2}^{1}}(k_{3}^{1}))$
$k_{1}^{1}$	$k_{2}^{0}$	$k_{3}^{1}$	$c_{3}=E_{k_{1}^{1}}(E_{k_{2}^{0}}(k_{3}^{1}))$
$k_{1}^{1}$	$k_{2}^{1}$	$k_{3}^{1}$	$c_{4}=E_{k_{1}^{1}}(E_{k_{2}^{1}}(k_{3}^{1}))$

Här menas resultatet av kryptering av värdet x med nyckeln k , respektive dekrypteringen av chiffertexten y med nyckeln k . Du bör välja ett symmetriskt krypteringsschema , som har ytterligare en egenskap: om du försöker dekryptera texten med fel nyckel, returnerar algoritmen ett fel. $E_{k}(x)$ $D_{k}(y)$

Innebörden av denna tabell är som följer: om vi känner till de krypterade värdena för signalen k 1 u k 2 på ingångstrådarna till ventilen w 1 u w 2 , kan vi beräkna det krypterade signalvärdet genom att beräkna värdet för all i =1...4 . I tre fall av fyra bör ett fel inträffa, och i det återstående fjärde kommer vi att få det krypterade värdet k 3 för signalen vid grindens utgång. $d_{i}=D_{k_{2}}(D_{k_{1}}(c_{i}))$

Deltagare p 1 skickar logikkretsen och krypterade beräkningstabeller för alla kretsar till deltagare p 2 .
Deltagare p 1 skickar till deltagare p 2 de krypterade värdena för ingångssignalerna för de ingångar som motsvarar indata för deltagare p 1 .
För varje ingångsledning w i som motsvarar indata p 2 , skickar deltagare p 1 ett nummer till deltagare p 2 med användning av det glömska överföringsprotokollet , där bi är värdet på den hemliga indatabiten för deltagare p 2 . Med en sådan överföring vet inte deltagaren p 1 värdet av b i . Eftersom för varje tråd dess egna slumptal, som är noll och ett, tidigare valdes slumpmässigt, kommer deltagaren p 2 inte att kunna ta reda på vilket nummer som är noll och vilket som är ett för ingångsledningarna för deltagaren p 1 , och därför kommer inte att kunna ta reda på ingående deltagardata p 1 . $k_{i}^{b_{i))$
Nu har medlem p 2 en krypterad logikkrets och krypterade värden på alla ingångsledningar. Den beräknar i krypterad form (som beskrivits ovan) alla grindar i kretsen efter varandra och skickar sedan det krypterade resultatet till deltagaren p 1 .
Deltagare p 1 dekrypterar resultatet och rapporterar det till deltagare p 2 .

Protokoll som används

Glömsk överföring kan vara en viktig komponent i det konfidentiella dataprotokollet .
Virtual Participant Protocol - Ett protokoll som döljer deltagarnas identitet [11] .
Säkra summaprotokoll tillåter samarbetande deltagare att beräkna vissa funktioner från sin individuella information utan att avslöja denna information för varandra [12] .

Praktisk tillämpning

Elektronisk röstning . Till exempel kan varje deltagare rösta för eller emot, då blir resultatet av omröstningen av n deltagare funktionen F(x 1 , …,x n ) , där x i kan ta värdena 0 (mot) och 1 (för).
Elektroniska auktioner. Varje deltagare bjuder x i , och funktionen F(x 1 , …,x n ) returnerar numret för det maximala x i .
Statistik. Låt oss säga att eleverna vill veta sitt bästa eller genomsnittliga betyg utan att visa betyg för varandra.
Databaser . Låt oss till exempel säga att användaren vill fråga en databas och få ett svar utan att exponera frågan. Ägaren till servern med databasen vill att ingen annan information än svaret på förfrågan ska nå användaren vid förfrågningar. I det här fallet kommer både användaren och servern att delta i det konfidentiella dataprotokollet.
Distribuerad certifikatutfärdare . Anta att du behöver skapa en certifikatutfärdare som kommer att utfärda certifikat till användare och signera dem med någon hemlig nyckel. För att skydda nyckeln kan nyckeln delas upp på flera servrar så att varje server behåller sin egen del av nyckeln. Då uppstår problemet: hur man utför en kryptografisk operation (i det här exemplet, utfärdande av en signatur) utan att överföra alla delar av nyckeln till en dator. Detta problem löses genom att använda ett privat beräkningsprotokoll, där ingången till den privata beräkningsfunktionen är nyckeldelarna och det signerade meddelandet, och utmatningen är det signerade meddelandet.

Anteckningar

↑ Andrew Chi-Chih Yao: Protocols for Secure Computations (Extended Abstract) FOCS 1982: 160-164
↑ Yehuda Lindell, Benny Pinkas: A Proof of Yao's Protocol for Secure Two-Print Computation, Cryptology ePrint Archive, Report 2004/175
↑ Lösning på miljonärens problem arkiverad 19 maj 2008.
↑ M. Ben-Or, S. Goldwasser och A. Wigderson. Fullständighetsteorem för icke-kryptografisk feltolerant distribuerad beräkning. I 20:e STOC, 1-10, 1988.
↑ P. Bogetoft, D. L. Christensen, I. Damgard, M. Geisler, T. Jakobsen, M. Kroigaard, J. D. Nielsen, J. B. Nielsen, K. Nielsen, J. Pagter, M. Schwartzbach och T. Toft. Säker flerpartsberäkning går livet ut. I finansiell kryptografi och datasäkerhet – FC 2009
↑ A. Yao. Hur man genererar och utbyter hemligheter. I 27:e FOCS, 162-167, 1986.
↑ Goldreich, S. Micali och A. Wigderson. Hur man spelar vilket mentalt spel som helst - En fullständighetsteorem för protokoll med ärlig majoritet. I 19:e STOC, 218-229, 1987.
↑ P. Bogetoft, I. Damgard, T. Jakobsen, K. Nielsen, J. Pagter. och T. Toft. En praktisk implementering av säkra beräkningsauktioner baserade på flerparts heltal. In Financial Cryptography and Data Security - FC 2006, Springer-Verlag LNCS 4107, 142-147, 2006.
↑ D. Malkhi, N. Nisan, B. Pinkas och Y. Sella. Fairplay är ett säkert tvåparts beräkningssystem. I Proc. av det 13:e USENIX Security Symposium, 2004.
↑ A. Ben-David, N. Nisan och B. Pinkas. FairplayMP: ett system för säker flerpartsberäkning. Inom dator- och kommunikationssäkerhet - CCS 2008, ACM, 257-266, 2008.
↑ Pathak Rohit, Joshi Satyadhar, Advances in Information Security and Assurance, Springer Berlin / Heidelberg, ISSN 0302-9743 (Print) 1611-3349 (Online), ISBN 978-3-642-02616-4 , DOI 3/971800 7/971800. -642-02617-1
↑ Rashid Sheikh, Brijesh Kumar och Durgesh Kumar Mishra, Privacy Preserving k-secure sum protocols, International Journal of Computer Science and Information Security, ISSN 1947-5500 (Online), Vol.6, No.2, Nov. 2009