Confidential Computing Protocol

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 27. november 2017; checks kræver 7 redigeringer .

I kryptografi er en fortrolig beregningsprotokol (også sikker, sikker eller hemmelig multi-party computation, eng. sikker multi-party computation ) en kryptografisk protokol , der tillader flere deltagere at udføre en beregning, der afhænger af de hemmelige inputdata for hver af dem , på en sådan måde, at ingen deltager var i stand til at få information om en andens hemmelige input. Det fortrolige computerproblem blev først rejst af Andrew Yao i 1982 i en artikel [1]. To millionærer, Alice og Bob, ønsker at finde ud af, hvem af dem der er rigere, mens de ikke ønsker at afsløre den nøjagtige mængde af deres rigdom. Yao foreslog i sin artikel en original måde at løse dette problem på, som senere blev kendt som problemet med millionærer . Meget senere, i 2004, leverede Yehuda Lindell og Benny Pinkas et matematisk strengt bevis på rigtigheden af Yaos protokol i [2] . Problemet med fortrolig beregning er tæt forbundet med problemet med hemmelig deling .

Formaliseret problemformulering

N deltagere p 1 , p 2 , …, p N deltager i fortrolig beregning . Hver deltager har hemmelige inputdata henholdsvis d1 , d2 , … , dN . Deltagerne ønsker at finde værdien F(d 1 , d 2 , …, d N ) , hvor F er en beregnelig funktion af N argumenter kendt af alle deltagere . Det antages, at der vil være semi-ærlige lovovertrædere blandt deltagerne , det vil sige dem, der trofast følger protokollen, men forsøger at få yderligere information fra eventuelle mellemliggende data.

Sikkerhedskrav

Sikkerhedskrav til fortrolige computerprotokoller har typisk forskellige sikkerhedskrav afhængigt af situationen. Her er de vigtigste krav.

Fortrolighed. Ingen af deltagerne skal kunne modtage mere information, end de er foreskrevet.
Rigtigheden. Hver deltager skal være garanteret at modtage de korrekte data.
Garanteret information. Deltagere bør ikke være i stand til at forhindre andre deltagere i at få outputtet.

Et eksempel på en løsning på problemet med millionærer

Lad millionærerne Alice og Bob ønsker at finde ud af, hvis formue er størst uden at afsløre den nøjagtige mængde af deres formuer. Antag, at Alice har i million og Bob har j , hvor 1<i og j<10 . For det første vil Alice og Bob have brug for et stærkt offentlig nøglekryptosystem , såsom RSA [3] . Lad E a være en vilkårlig krypteringsfunktion for nøglen a , og D a være den private nøgledekrypteringsfunktion for den offentlige nøgle a . Lad en være Alices offentlige nøgle. Så ser protokollen sådan ud:

Bob vælger et tilfældigt heltal x fra N bit og beregner fortroligt k=E a (x) ;
Bob sender et nummer k-j+1 til Alice ;
Alice betragter fortroligt værdierne y u =D a (k-j+u) for u=1,2,…,10 ;
Alice vælger et tilfældigt primtal p fra N/2 bit, så tallene z u =y u mod(p) afviger med mindst 2 modulo p for alle u og sender tallet p til Bob;
Alice sender numrene z 1 , z 2 , …, z i efterfulgt af tallene z i+1 +1, …, z 10 +1 ; tal tages modulo p;
Bob, som ved hvor mange penge han har ( j ), sammenligner tallet j med tallet x mod p valgt i første trin, og hvis de er lige store, så konkluderer Bob, at i ⩾ j , og i < j ellers;
Bob rapporterer resultatet til Alice.

Det kan ses, at protokollen giver dig mulighed for entydigt at bestemme, hvis tilstand er større, og samtidig kan deltagerne ikke finde ud af hinandens tilstande.

Implementeringer

Der er to forskellige tilgange til implementering af protokollen. Den første tilgang er normalt baseret på hemmelig deling og arbejder på repræsentationen af den beregnede funktion i form af et aritmetisk kredsløb ( eng. aritmetisk kredsløb ), som for eksempel i BGW (Ben-Or, Goldwasser og Wigderson) [ 4] og CCD (Chaum, Crepeau og Damgard [5] . Denne tilgang anvendes normalt, når det er kendt, at flertallet af deltagere er ærlige (hvilket kun er muligt, hvis antallet af deltagere er mere end to). En anden tilgang er at repræsentere funktionen som et logisk diagram . Denne tilgang blev brugt af Andrew Yao , da han konstruerede et forvrænget kredsløb ( engelsk forvansket kredsløb ) [6] såvel som i GMW-protokollen (Goldreich, Micali og Wigderson) [7] .

Den aritmetiske skemametode er bedre egnet til at udføre additions- og multiplikationsoperationer (hvor deltagerne har andele af hemmeligheden, og hemmeligheden kun kan genskabes, hvis der modtages information fra hver af deltagerne), men er dårligt egnet til at udføre sammenligningsoperationer. Denne tilgang har opnået stor succes i SIMAP-projektet [8] .

Den logiske kredsløbsmetode udfører additioner og multiplikationer med mindre effektivitet, men kan nemt udføre binære operationer såsom sammenligninger. Denne anden tilgang, som Andrew Yaos tohåndssystem er baseret på, blev implementeret af Mulchy i fairplay-systemet [9 ] . Dette system giver også mulighed for at implementere den nødvendige funktionalitet, repræsenteret af et programmeringssprog på højt niveau i form af en logisk løkke, som derefter fortolkes af runtime-miljøet og udføres sikkert. Der er også et system "FairplayMP" [10] , som er en udvidelse af "Fairplay", hvis der er mere end to deltagere. En væsentlig fordel ved metodebaserede systemer med logiske kredsløb er, at de udføres i et konstant antal informationsudvekslinger, mens fordelen ved systemer baseret på aritmetiske kredsløb er evnen til at udføre regneoperationer (addition og multiplikation) meget hurtigt.

Protokoleksempel

Lad os for nemheds skyld antage, at to deltagere deltager i beregningen, det vil sige N=2 , og deltagerne skal beregne funktionen F .

Lad os repræsentere funktionen F i form af et logisk kredsløb , det vil sige, vi vil repræsentere inputdataene for funktionen F i binær form, og selve funktionen implementeres ved hjælp af operationerne AND, OR og NOT. Derefter føres bits af alle argumenter for funktionen F til indgangen af det logiske kredsløb , og selve kredsløbet består af logiske porte AND, OR og NOT, og ved udgangen producerer det resultatet af funktionen F i binært format.
Deltager p 1 genererer for hver ledning i det logiske kredsløb to forskellige tilfældige tal k 0 u k 1 . Tallene repræsenterer henholdsvis det krypterede nul og et på den ledning.
Deltager p 1 opretter en krypteret beregningstabel for hvert skema. For en binær ELLER-port vil en sådan tabel se sådan ud:

Indgangsledning w 1	Indgangsledning w 2	Udgangsledning w 3	Krypteret beregningstabel
${\displaystyle k_{1}^{0))$	$k_{2}^{0}$	${\displaystyle k_{3}^{0))$	$c_{1}=E_{k_{1}^{0}}(E_{k_{2}^{0}}(k_{3}^{0}))$
${\displaystyle k_{1}^{0))$	${\displaystyle k_{2}^{1))$	${\displaystyle k_{3}^{1))$	$c_{2}=E_{k_{1}^{0}}(E_{k_{2}^{1}}(k_{3}^{1}))$
${\displaystyle k_{1}^{1))$	$k_{2}^{0}$	${\displaystyle k_{3}^{1))$	$c_{3}=E_{k_{1}^{1}}(E_{k_{2}^{0}}(k_{3}^{1}))$
${\displaystyle k_{1}^{1))$	${\displaystyle k_{2}^{1))$	${\displaystyle k_{3}^{1))$	$c_{4}=E_{k_{1}^{1}}(E_{k_{2}^{1}}(k_{3}^{1}))$

Her menes resultatet af kryptering af værdien x med nøglen k , og - henholdsvis dekrypteringen af chifferteksten y med nøglen k . Du bør vælge et symmetrisk krypteringsskema , som har en ekstra egenskab: Hvis du forsøger at dekryptere teksten med den forkerte nøgle, returnerer algoritmen en fejl. $E_{k}(x)$ $D_{k}(y)$

Betydningen af denne tabel er som følger: hvis vi kender de krypterede værdier af signalet k 1 u k 2 på inputtrådene til henholdsvis ventilen w 1 u w 2 , så kan vi beregne den krypterede signalværdi ved at beregne værdien for alle i =1...4 . I tre ud af fire tilfælde skulle der opstå en fejl, og i det resterende fjerde får vi den krypterede værdi k 3 af signalet ved portudgangen. $d_{i}=D_{k_{2}}(D_{k_{1}}(c_{i}))$

Deltager p 1 sender det logiske kredsløb og krypterede beregningstabeller for alle kredsløb til deltager p 2 .
Deltager p 1 sender til deltager p 2 de krypterede værdier af inputsignalerne for de input, der svarer til inputdata for deltager p 1 .
For hver inputledning w i , der svarer til inputdata p 2 , sender deltager p 1 et nummer til deltager p 2 ved brug af glemsom overførselsprotokol , hvor b i er værdien af den hemmelige inputdatabit for deltager p 2 . Ved en sådan overførsel kender deltageren p 1 ikke værdien af b i . Da for hver ledning dets egne tilfældige tal, som er nul og en, tidligere blev valgt tilfældigt, vil deltager p 2 ikke være i stand til at finde ud af, hvilket tal der er nul, og hvilket er et for inputtrådene for deltager p 1 , og derfor vil ikke være i stand til at finde ud af input deltagerdata p 1 . $k_{i}^{b_{i))$
Nu har medlem p 2 et krypteret logisk kredsløb og krypterede værdier af alle inputledninger. Den beregner i krypteret form (som beskrevet ovenfor) alle kredsløbets porte efter hinanden og sender derefter det krypterede resultat til deltageren p 1 .
Deltager p 1 dekrypterer resultatet og rapporterer det til deltager p 2 .

Anvendte protokoller

Glemsom transmission kan være en vigtig komponent i den fortrolige computerprotokol .
Virtual Participant Protocol - En protokol, der skjuler deltagernes identitet [11] .
Sikker sum protokoller tillader samarbejdende deltagere at beregne nogle funktioner ud fra deres individuelle oplysninger uden at afsløre disse oplysninger til hinanden [12] .

Praktisk anvendelse

Elektronisk afstemning . For eksempel kan hver deltager stemme for eller imod, så vil resultatet af afstemningen af n deltagere være funktionen F(x 1 , …,x n ) , hvor x i kan tage værdierne 0 (imod) og 1 (til).
Elektroniske auktioner. Hver deltager byder x i , og funktionen F(x 1 , …,x n ) returnerer tallet for det maksimale x i .
Statistikker. Lad os sige, at eleverne vil vide deres bedste eller gennemsnitlige karakter uden at vise karakterer til hinanden.
Databaser . Lad os f.eks. sige, at brugeren ønsker at forespørge i en database og få et svar uden at afsløre forespørgslen. Ejeren af serveren med databasen ønsker, at ingen andre oplysninger end svaret på anmodningen skal nå frem til brugeren, når de fremsætter anmodninger. I dette tilfælde vil både brugeren og serveren være deltagere i den fortrolige computerprotokol.
Distribueret certifikatmyndighed . Antag, at du skal oprette en certificeringsmyndighed, der udsteder certifikater til brugere, og signerer dem med en hemmelig nøgle. For at beskytte nøglen kan nøglen deles mellem flere servere, så hver server beholder sin egen del af nøglen. Så opstår problemet: hvordan man udfører en kryptografisk operation (i dette eksempel udstedelse af en signatur) uden at overføre alle dele af nøglen til én computer. Dette problem løses ved at bruge en privat beregningsprotokol, hvor input til den private beregningsfunktion er nøgledelene og den signerede meddelelse, og outputtet er den signerede meddelelse.

Noter

↑ 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-Party Computation, Cryptology ePrint Archive, Report 2004/175
↑ Løsning på millionærens problem arkiveret 19. maj 2008.
↑ M. Ben-Or, S. Goldwasser og A. Wigderson. Fuldstændighedsteoremer for ikke-kryptografisk fejltolerant distribueret beregning. I 20. 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 og T. Toft. Sikker multiparty-beregning går livet ud. I finansiel kryptografi og datasikkerhed – FC 2009
↑ A. Yao. Hvordan man genererer og udveksler hemmeligheder. I 27. FOCS, 162-167, 1986.
↑ Goldreich, S. Micali og A. Wigderson. Sådan spiller du ethvert mentalt spil - En fuldstændighedsteorem for protokoller med ærligt flertal. I 19. STOC, 218-229, 1987.
↑ P. Bogetoft, I. Damgard, T. Jakobsen, K. Nielsen, J. Pagter. og T. Toft. En praktisk implementering af sikre beregningsauktioner baseret på flerparts heltal. I Financial Cryptography and Data Security - FC 2006, Springer-Verlag LNCS 4107, 142-147, 2006.
↑ D. Malkhi, N. Nisan, B. Pinkas og Y. Sella. Fairplay er et sikkert to-parts beregningssystem. I Proc. af 13. USENIX Security Symposium, 2004.
↑ A. Ben-David, N. Nisan og B. Pinkas. FairplayMP: et system til sikker multi-party beregning. I computer- og kommunikationssikkerhed - 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 og 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