Confidential Computing Protocol

Salaustekniikassa luottamuksellinen laskentaprotokolla (myös suojattu, suojattu tai salainen monen osapuolen laskenta, eng. suojattu monen osapuolen laskenta ) on salausprotokolla , jonka avulla useat osallistujat voivat suorittaa laskennan, joka riippuu kunkin heidän salaisista syöttötiedoistaan. , siten, että kukaan osallistuja ei voinut saada mitään tietoa jonkun toisen salaisesta syötöstä. Luottamuksellisen tietojenkäsittelyongelman otti ensimmäisen kerran esille Andrew Yao vuonna 1982 artikkelissa [1]  . Kaksi miljonääriä, Alice ja Bob, haluavat selvittää, kumpi heistä on rikkaampi, mutta he eivät halua paljastaa omaisuutensa tarkkaa määrää. Yao ehdotti artikkelissaan alkuperäistä tapaa ratkaista tämä ongelma, joka myöhemmin tunnettiin miljonääriongelmana . Paljon myöhemmin, vuonna 2004, Yehuda Lindell ja Benny Pinkas esittivät matemaattisesti tarkan todisteen Yaon protokollan oikeellisuudesta vuonna [2] . Luottamuksellisen laskennan ongelma liittyy läheisesti salaisen jakamisen ongelmaan .

Virallinen ongelman kuvaus

N osallistujaa p 1 , p 2 , … , p N osallistuu luottamukselliseen laskelmaan . Jokaisella osallistujalla on vastaavasti salainen syöttödata d 1 , d 2 , …, d N. Osallistujat haluavat löytää arvon F(d 1 , d 2 , …, d N ) , jossa F on  kaikkien osallistujien tiedossa N :n argumentin laskettava funktio . Osallistujien joukossa oletetaan olevan puolirehellisiä rikoksentekijöitä , eli niitä, jotka noudattavat uskollisesti protokollaa, mutta yrittävät saada lisätietoa kaikista välitiedoista.

Suojausvaatimukset

Luottamuksellisten laskentaprotokollien turvallisuusvaatimuksilla on tyypillisesti erilaiset turvallisuusvaatimukset tilanteesta riippuen. Tässä ovat tärkeimmät vaatimukset.

• Luottamuksellisuus. Kukaan osallistujista ei saa saada enemmän tietoa kuin heille on määrätty.
• Oikeudenmukaisuus. Jokaiselle osallistujalle on taattava oikeat tiedot.
• Taattua tietoa. Osallistujien ei pitäisi pystyä estämään muita osallistujia saamasta tulosta.

Esimerkki ratkaisusta miljonääriongelmaan

Miljonäärit Alice ja Bob haluavat selvittää, kenen omaisuus on suurempi paljastamatta omaisuutensa tarkkaa määrää. Varmuuden vuoksi oletetaan, että Alicella on i miljoonaa ja Bobilla j , missä 1<i ja j<10 . Ensinnäkin Alice ja Bob tarvitsevat vahvan julkisen avaimen salausjärjestelmän , kuten RSA :n [3] . Olkoon E a  mielivaltainen salausfunktio avaimelle a ja D a  yksityisen avaimen salauksenpurkutoiminto julkiselle avaimelle a . Olkoon  Alicen julkinen avain . Sitten protokolla näyttää tältä:

1. Bob valitsee satunnaisen kokonaisluvun x N bitistä ja laskee luottamuksellisesti k=E a (x) ;
2. Bob lähettää luvun k-j+1 Alicelle ;
3. Alice harkitsee luottamuksellisesti arvoja y u =D a (k-j+u) kun u=1,2,…,10 ;
4. Alice valitsee satunnaisen alkuluvun p N/2 bitistä siten , että luvut z u =y u mod(p) eroavat vähintään 2 modulo p kaikilla u :illa ja lähettää luvun p Bobille;
5. Alice lähettää numerot z 1 , z 2 , …, z i ja sen jälkeen numerot z i+1 +1, …, z 10 +1 ; numerot otetaan modulo p;
6. Bob, joka tietää kuinka paljon hänellä on rahaa ( j ), vertaa lukua j ensimmäisessä vaiheessa valittuun numeroon x mod p , ja jos ne ovat yhtä suuret, niin Bob päättelee, että i ⩾ j ja i < j muuten;
7. Bob raportoi tuloksesta Alicelle.

Voidaan nähdä, että protokollan avulla voit yksiselitteisesti määrittää, kumman tila on suurempi, ja samalla osallistujat eivät voi saada selville toistensa tiloja.

Toteutukset

Protokollan toteuttamiseen on kaksi erilaista lähestymistapaa. Ensimmäinen lähestymistapa perustuu yleensä salaiseen jakamiseen ja toimii lasketun funktion esittämisessä aritmeettisen piirin muodossa ( eng.  aritmetic circuit ), kuten esimerkiksi BGW:ssä (Ben-Or, Goldwasser ja Wigderson) [ 4] ja CCD (Chaum, Crepeau ja Damgard [5] . Tätä lähestymistapaa sovelletaan yleensä, kun tiedetään, että suurin osa osallistujista on rehellisiä (mikä on mahdollista vain, jos osallistujia on enemmän kuin kaksi). Toinen lähestymistapa on esittää funktio logiikkakaaviona . Andrew Yao käytti tätä lähestymistapaa rakentaessaan vääristyneen piirin ( englanniksi  vääristynyt piiri ) [6] sekä GMW-protokollassa (Goldreich, Micali ja Wigderson) [7] .

Aritmeettinen kaavamenetelmä soveltuu paremmin yhteen- ja kertolaskuoperaatioiden suorittamiseen (jossa osallistujilla on osuudet salaisuudesta ja salaisuus voidaan luoda uudelleen vain, jos jokaiselta osallistujalta saadaan tietoa), mutta se soveltuu huonosti vertailuoperaatioiden suorittamiseen. Tämä lähestymistapa on saavuttanut suurta menestystä SIMAP-projektissa [8] .

Logiikkapiirimenetelmä suorittaa yhteen- ja kertolaskuja pienemmällä tehokkuudella, mutta sillä voidaan helposti suorittaa binääritoimintoja, kuten vertailuja. Tämän toisen lähestymistavan, johon Andrew Yaon kahden käden järjestelmä perustuu , Mulchy toteutti fairplay -järjestelmässä [ 9 ] .  Tämä järjestelmä tarjoaa myös mahdollisuuden toteuttaa tarvittavat toiminnot, joita edustaa korkean tason ohjelmointikieli loogisen silmukan muodossa, jonka ajonaikainen ympäristö sitten tulkitsee ja suorittaa turvallisesti. On myös järjestelmä "FairplayMP" [10] , joka on "Fairplay"-järjestelmän laajennus, jos osallistujia on enemmän kuin kaksi. Menetelmäpohjaisten logiikkapiireillä varustettujen järjestelmien merkittävä etu on, että ne suoritetaan jatkuvassa tiedonvaihdossa, kun taas aritmeettisiin piireihin perustuvien järjestelmien etuna on kyky suorittaa aritmeettisia operaatioita (yhdys- ja kertolasku) erittäin nopeasti.

Protokollaesimerkki

Yksinkertaisuuden vuoksi oletetaan, että laskemiseen osallistuu kaksi osallistujaa, eli N=2 , ja osallistujien on laskettava funktio F .

• Esitetään funktio F loogisen piirin muodossa, eli funktion F tulotiedot esitetään binäärimuodossa ja itse funktio toteutetaan operaatioilla AND, OR ja NOT. Sitten funktion F kaikkien argumenttien bitit syötetään logiikkapiirin sisäänmenoon , ja itse piiri koostuu logiikkaporteista AND, OR ja NOT, ja lähdössä se tuottaa funktion F tuloksen binäärimuodossa.
• Osallistuja p 1 generoi jokaiselle logiikkapiirin johtimelle kaksi erilaista satunnaislukua k 0 u k 1 . Numerot edustavat salattua nollaa ja yhtä kyseisessä johdossa.
• Osallistuja p 1 luo salatun laskentataulukon kullekin skeemalle. Binääriselle TAI-portille tällainen taulukko näyttäisi tältä:

Tulojohto w 1	Tulojohto w 2	Lähtöjohto w 3	Salattu laskentataulukko

Tässä tarkoitetaan arvon x salauksen tulosta avaimella k ja  vastaavasti salatekstin y purkamista avaimella k . Sinun tulisi valita symmetrinen salausmalli , jolla on yksi lisäominaisuus: jos yrität purkaa tekstin salauksen väärällä avaimella, algoritmi palauttaa virheen.

Tämän taulukon merkitys on seuraava: jos tiedämme vastaavasti venttiilin w 1 u w 2 tulojohtojen signaalin k 1 u k 2 salatut arvot , voimme laskea salatun signaalin arvon laskemalla arvo kaikille i =1...4 . Kolmessa tapauksessa neljästä pitäisi tapahtua virhe, ja jäljelle jäävässä neljännessä saamme signaalin salatun arvon k 3 portin lähdöstä.

• Osallistuja p 1 lähettää logiikkapiirin ja salatut laskentataulukot kaikille piireille osallistujalle p 2 .
• Osallistuja p 1 lähettää osallistujalle p 2 tulosignaalien salatut arvot niille tuloille, jotka vastaavat osallistujan p 1 syöttötietoja .
• Jokaiselle syöttöjohtimelle w i , joka vastaa syöttödataa p 2 , osallistuja p1 lähettää numeron osallistujalle p2 käyttämällä unohtavaa siirtoprotokollaa , missä b i on osallistujan p 2  salaisen syöttödatabitin arvo . Tällaisella siirrolla osallistuja p 1 ei tiedä b i :n arvoa . Koska kullekin johtimelle valittiin aiemmin satunnaisesti omat satunnaisluvut, jotka ovat nolla ja yksi, niin osallistuja p 2 ei voi saada selville, mikä numero on nolla ja mikä yksi osallistujan p 1 tulojohdoille , ja siksi ei saa selville syötetyt osallistujatiedot p 1 .
• Nyt jäsenellä p 2 on salattu logiikkapiiri ja kaikkien tulojohtojen salatut arvot. Se laskee salatussa muodossa (kuten edellä on kuvattu) kaikki piirin portit peräkkäin ja välittää sitten salatun tuloksen osallistujalle p 1 .
• Osallistuja p 1 purkaa tuloksen ja raportoi sen osallistujalle p 2 .

Käytetyt protokollat

• Unohtunut tiedonsiirto voi olla tärkeä osa luottamuksellista laskentaprotokollaa .
• Virtual Participant Protocol - Protokolla, joka piilottaa osallistujien henkilöllisyyden [11] .
• Turvalliset summaprotokollat ​​mahdollistavat yhteistyön osallistujien laskea joitakin ominaisuuksia yksilöllisistä tiedoistaan ​​paljastamatta näitä tietoja toisilleen [12] .

Käytännön sovellus

• Sähköinen äänestäminen . Esimerkiksi jokainen osallistuja voi äänestää puolesta tai vastaan, jolloin n osallistujan äänestyksen tulos on funktio F(x 1 , …,x n ) , jossa x i voi ottaa arvot 0 (vastaan) ja 1 (for).
• Sähköiset huutokaupat. Jokainen osallistuja tarjoaa x i , ja funktio F(x 1 , …,x n ) palauttaa maksimi x i luvun .
• Tilastot. Oletetaan, että opiskelijat haluavat tietää parhaan tai keskimääräisen arvosanansa näyttämättä arvosanoja toisilleen.
• Tietokannat . Oletetaan esimerkiksi, että käyttäjä haluaa tehdä kyselyn tietokannasta ja saada vastauksen paljastamatta kyselyä. Palvelimen omistaja, jolla on tietokanta, ei halua käyttäjän tavoittavan pyyntöä tehdessään muuta tietoa kuin vastauksen pyyntöön. Tässä tapauksessa sekä käyttäjä että palvelin ovat luottamuksellisen laskentaprotokollan osallistujia.
• Hajautettu varmenteen myöntäjä . Oletetaan, että sinun on luotava varmentaja, joka myöntää käyttäjille varmenteita ja allekirjoittaa ne jollain salaisella avaimella. Avaimen suojaamiseksi avain voidaan jakaa useiden palvelimien kesken siten, että jokainen palvelin säilyttää oman osan avaimesta. Sitten syntyy ongelma: kuinka suorittaa salaustoiminto (tässä esimerkissä allekirjoituksen antaminen) siirtämättä avaimen kaikkia osia yhdelle tietokoneelle. Tämä ongelma ratkaistaan ​​käyttämällä yksityistä laskentaprotokollaa, jossa yksityisen laskentafunktion syöte on avainosat ja allekirjoitettu viesti ja tulos on allekirjoitettu viesti.

Muistiinpanot

1. ↑ Andrew Chi-Chih Yao: Protocols for Secure Computations (Extended Abstract) FOCS 1982: 160-164
2. ↑ Yehuda Lindell, Benny Pinkas: Todiste Yaon suojatun kahden osapuolen laskennan protokollasta, kryptologian ePrint-arkisto, raportti 2004/175
3. ↑ Ratkaisu miljonäärin ongelmaan Arkistoitu 19. toukokuuta 2008.
4. ↑ M. Ben-Or, S. Goldwasser ja A. Wigderson. Täydellisyyslauseet ei-salaukselliseen vikasietoiseen hajautettuun laskentaan. 20. STOC:ssa, 1-10, 1988.
5. ↑ 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 ja T. Toft. Turvallinen monen osapuolen laskenta kestää elämää. Talousalalla kryptografia ja tietoturva – FC 2009
6. ↑ A. Yao. Kuinka luoda ja vaihtaa salaisuuksia. Julkaisussa 27th FOCS, 162-167, 1986.
7. ↑ Goldreich, S. Micali ja A. Wigderson. Kuinka pelata mitä tahansa henkistä peliä - Täydellisyyslause protokollille rehellisellä enemmistöllä. 19. STOC, 218-229, 1987.
8. ↑ P. Bogetoft, I. Damgard, T. Jakobsen, K. Nielsen, J. Pagter. ja T. Toft. Monen osapuolen kokonaislukuihin perustuvien suojattujen laskentahuutokauppojen käytännön toteutus. Talousalalla kryptografia ja tietoturva - FC 2006, Springer-Verlag LNCS 4107, 142-147, 2006.
9. ↑ D. Malkhi, N. Nisan, B. Pinkas ja Y. Sella. Fairplay on turvallinen kahden osapuolen laskentajärjestelmä. Julkaisussa Proc. 13. USENIX Security Symposium, 2004.
10. ↑ A. Ben-David, N. Nisan ja B. Pinkas. FairplayMP: järjestelmä turvalliseen monen osapuolen laskentaan. Tietokone- ja tietoliikenneturvallisuus - CCS 2008, ACM, 257-266, 2008.
11. ↑ Pathak Rohit, Joshi Satyadhar, Advances in Information Security and Assurance, Springer Berlin / Heidelberg, ISSN 0302-9743 (painettu) 1611-3349 (online), ISBN 978-3-642-02616-4 , DOI-3-1/78. -642-02617-1
12. ↑ Rashid Sheikh, Brijesh Kumar ja 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