Confidential Computing Protocol

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt hozzászólók, és jelentősen eltérhet a 2017. november 27-én felülvizsgált verziótól ; az ellenőrzések 7 szerkesztést igényelnek .

A kriptográfiában a bizalmas számítási protokoll (biztonságos, biztonságos vagy titkos többoldalú számítás is, eng. safe multi-party compution ) egy olyan kriptográfiai protokoll , amely lehetővé teszi több résztvevő számára, hogy olyan számítást hajtsanak végre, amely mindegyikük titkos bemeneti adataitól függ. , oly módon, hogy egyetlen résztvevő sem tudott információt szerezni valaki más titkos beviteléről. A bizalmas számítástechnikai problémát először Andrew Yao vetette fel 1982 -ben egy cikkében [1].. Két milliomos, Alice és Bob szeretné kideríteni, melyikük a gazdagabb, vagyonuk pontos összegét azonban nem akarják elárulni. Yao cikkében eredeti megoldást javasolt ennek a problémának a megoldására, amely később milliomosok problémájaként vált ismertté . Jóval később, 2004-ben Yehuda Lindell és Benny Pinkas matematikailag szigorú bizonyítékot szolgáltatott Yao protokolljának helyességére [2] . A bizalmas számítások problémája szorosan összefügg a titkos megosztás problémájával .

Formalizált problémafelvetés

N résztvevő p 1 , p 2 , … , p N részt vesz a bizalmas számításban . Minden résztvevő titkos bemeneti adatokkal rendelkezik d 1 , d 2 , …, d N. A résztvevők meg akarják találni az F(d 1 , d 2 , …, d N ) értéket , ahol F N argumentum kiszámítható függvénye , amelyet minden résztvevő ismer . Feltételezhető, hogy a résztvevők között lesznek félig becsületes elkövetők , vagyis olyanok, akik hűségesen követik a protokollt, de bármilyen köztes adatból igyekeznek további információkat szerezni.

Biztonsági követelmények

A bizalmas számítási protokollok biztonsági követelményei általában a helyzettől függően eltérő biztonsági követelményekkel rendelkeznek. Itt vannak a fő követelmények.

Titoktartás. Egyik résztvevő sem kaphat több információt az előírtnál.
korrektség. Minden résztvevőnek garantálni kell, hogy a helyes adatokat kapja meg.
Garantált információ. A résztvevők nem akadályozhatják meg a többi résztvevőt a kimenet megszerzésében.

Példa a milliomosok problémájának megoldására

A milliomosok, Alice és Bob akarják megtudni, kinek a vagyona nagyobb, anélkül, hogy nyilvánosságra hozzák vagyonuk pontos összegét. A határozottság kedvéért tegyük fel, hogy Alice-nek i milliója van, Bobnak pedig j , ahol 1<i és j<10 . Először is, Alice-nek és Bobnak erős nyilvános kulcsú kriptorendszerre lesz szüksége , mint például az RSA [3] . Legyen E a egy tetszőleges titkosítási függvény az a kulcshoz , és D a az a nyilvános kulcs privát kulcsának dekódoló függvénye . Legyen a Alice nyilvános kulcsa. Akkor a protokoll így néz ki:

Bob kiválaszt egy véletlenszerű x egész számot N bitből, és bizalmasan kiszámítja k=E a (x) ;
Bob k-j+1 számot küld Alice-nek ;
Alice bizalmasan figyelembe veszi az y u =D a (k-j+u) értékeket u=1,2,…,10 esetén ;
Alice kiválaszt egy véletlenszerű p prímszámot N/2 bitből úgy, hogy a z u =y u mod(p) számok legalább 2 modulo p -vel térjenek el minden u -ra , és elküldi a p számot Bobnak;
Alice elküldi a z 1 , z 2 , …, z i számokat, majd a z i+1 +1, …, z 10 +1 számokat ; a számokat modulo p veszik;
Bob, aki tudja, mennyi pénze van ( j ), összehasonlítja a j számot az első lépésben kiválasztott x mod p számmal , és ha egyenlők, akkor Bob arra a következtetésre jut, hogy i ⩾ j , egyébként pedig i < j ;
Bob jelenti az eredményt Alice-nek.

Látható, hogy a protokoll segítségével egyértelműen meghatározható, hogy kinek az állapota nagyobb, ugyanakkor a résztvevők nem tudhatják meg egymás állapotát.

Megvalósítások

Két különböző megközelítés létezik a protokoll megvalósítására. Az első megközelítés általában titkos megosztáson alapul, és a számított függvény aritmetikai áramkör formájában történő ábrázolásán dolgozik ( eng. aritmetic circuit ), mint például a BGW-ben (Ben-Or, Goldwasser és Wigderson) [ 4] és CCD (Chaum, Crepeau és Damgard [5]) . Ezt a megközelítést általában akkor alkalmazzák, ha ismert, hogy a résztvevők többsége őszinte (ami csak akkor lehetséges, ha a résztvevők száma kettőnél több). Egy másik megközelítés a függvény logikai diagramként való ábrázolása . Ezt a megközelítést Andrew Yao használta egy torzított áramkör ( angol garbled circuit ) [6] , valamint a GMW protokollban (Goldreich, Micali és Wigderson) [7] [7] .

Az aritmetikai séma módszer alkalmasabb összeadási és szorzási műveletek végrehajtására (ahol a résztvevők részesedéssel rendelkeznek a titokban, és a titok csak akkor hozható létre, ha minden résztvevőtől információ érkezik), de összehasonlítási műveletek végrehajtására gyengén alkalmas. Ez a megközelítés nagy sikert ért el a SIMAP projektben [8] .

A logikai áramkör módszere kisebb hatékonysággal hajt végre összeadást és szorzást, de könnyen végrehajthat bináris műveleteket, például összehasonlításokat. Ezt a második megközelítést, amelyen Andrew Yao kétkezes rendszere alapul , Mulchy valósította meg a fairplay rendszerben [9 ] . Ez a rendszer lehetővé teszi a szükséges funkcionalitás megvalósítását is, amelyet egy magas szintű programozási nyelv képvisel logikai hurok formájában, amelyet aztán a futási környezet értelmez, és biztonságosan végrehajt. Létezik egy „FairplayMP” [10] rendszer is , amely kettőnél több résztvevő esetén a „Fairplay” kiterjesztése. A logikai áramkörökkel rendelkező módszer alapú rendszerek jelentős előnye, hogy állandó számú információcserében hajtják végre, míg az aritmetikai áramkörökre épülő rendszerek előnye, hogy nagyon gyors számtani műveleteket (összeadás és szorzás) hajtanak végre.

Protokoll példa

Az egyszerűség kedvéért tegyük fel, hogy két résztvevő vesz részt a számításban, azaz N=2 , és a résztvevőknek ki kell számítaniuk az F függvényt .

Ábrázoljuk az F függvényt logikai áramkör formájában , azaz az F függvény bemeneti adatait bináris formában ábrázoljuk, és magát a függvényt az ÉS, VAGY és NEM műveletek segítségével valósítjuk meg. Ekkor az F függvény összes argumentumának bitje a logikai áramkör bemenetére kerül , és maga az áramkör AND, OR és NOT logikai kapukból áll , a kimeneten pedig az F függvény eredményét állítja elő bináris formátumban.
A p 1 résztvevő a logikai áramkör minden vezetékére két különböző k 0 u k 1 véletlenszámot generál . A számok a titkosított nullát és egyet jelentik az adott vezetéken.
A p 1 résztvevő minden egyes sémához titkosított számítási táblázatot készít. Egy bináris VAGY kapu esetén egy ilyen táblázat így néz ki:

Bemeneti vezeték w 1	Bemeneti vezeték w 2	Kimeneti vezeték w 3	Titkosított számítási táblázat
${\displaystyle k_{1}^{0))$	${\displaystyle k_{2}^{0))$	${\displaystyle k_{3}^{0))$	$c_{1}=E_{k_{1}^{0}}(E_{k_{2}^{0}}(k_{3}^{0}))$
${\displaystyle k_{1}^{0))$	$k_{2}^{1}$	${\displaystyle k_{3}^{1))$	$c_{2}=E_{k_{1}^{0}}(E_{k_{2}^{1}}(k_{3}^{1}))$
${\displaystyle k_{1}^{1))$	${\displaystyle k_{2}^{0))$	${\displaystyle k_{3}^{1))$	$c_{3}=E_{k_{1}^{1}}(E_{k_{2}^{0}}(k_{3}^{1}))$
${\displaystyle k_{1}^{1))$	$k_{2}^{1}$	${\displaystyle k_{3}^{1))$	$c_{4}=E_{k_{1}^{1}}(E_{k_{2}^{1}}(k_{3}^{1}))$

Itt az x érték k kulccsal történő titkosításának eredményét , illetve az y titkosított szöveg k kulccsal történő visszafejtésének eredményét jelenti . Válasszon egy szimmetrikus titkosítási sémát , amelynek van egy további tulajdonsága: ha rossz kulccsal próbálja visszafejteni a szöveget, az algoritmus hibát ad vissza. $E_{k}(x)$ $D_{k}(y)$

Ennek a táblázatnak a jelentése a következő: ha ismerjük a k 1 u k 2 jel titkosított értékeit a w 1 u w 2 szelep bemeneti vezetékein , akkor kiszámíthatjuk a titkosított jel értékét a számítással. az összes i értéke =1...4 . Négyből három esetben hiba léphet fel, a maradék negyedikben pedig a jel titkosított k 3 értékét kapjuk a kapukimeneten. $d_{i}=D_{k_{2}}(D_{k_{1}}(c_{i}))$

A p 1 résztvevő elküldi a logikai áramkört és az összes áramkörre vonatkozó titkosított számítási táblázatokat a p 2 résztvevőnek .
A p 1 résztvevő elküldi p 2 résztvevőnek a bemeneti jelek titkosított értékeit azokhoz a bemenetekhez, amelyek megfelelnek a p 1 résztvevő bemeneti adatainak .
A p 2 bemeneti adatoknak megfelelő w i bemeneti vezetékeknél a p 1 résztvevő egy számot küld p 2 résztvevőnek a felejtő átviteli protokoll segítségével , ahol b i a p 2 résztvevő titkos bemeneti adatbitjének értéke . Egy ilyen átvitelnél a p 1 résztvevő nem ismeri b i értékét . Mivel minden vezetékhez korábban véletlenszerűen választották ki a saját véletlenszámait, amelyek nulla és egy, ezért a p 2 résztvevő nem fogja tudni megtudni, melyik szám nulla és melyik az egyes p 1 résztvevő bemeneti vezetékeinél , és ezért nem fogja tudni kideríteni a bemeneti résztvevői adatokat p 1 . $k_{i}^{b_{i))$
Most a p 2 tagnak van egy titkosított logikai áramköre és az összes bemeneti vezeték titkosított értéke. Titkosított formában (a fent leírtak szerint) egymás után kiszámítja az áramkör összes kapuját, majd a titkosított eredményt továbbítja a p 1 résztvevőnek .
A p 1 résztvevő dekódolja az eredményt, és jelenti azt p 2 résztvevőnek .

Használt protokollok

A felejtős adatátvitel a bizalmas számítási protokoll fontos eleme lehet .
Virtual Participant Protocol – Protokoll, amely elrejti a résztvevők személyazonosságát [11] .
A biztonságos összegzési protokollok lehetővé teszik az együttműködő résztvevők számára, hogy egyéni információikból kiszámítsanak bizonyos jellemzőket anélkül, hogy ezeket az információkat felfednék egymásnak [12] .

Gyakorlati alkalmazás

Elektronikus szavazás . Például minden résztvevő szavazhat mellette vagy ellene, ekkor n résztvevő szavazásának eredménye az F(x 1 , …,x n ) függvény lesz , ahol x i veheti fel a 0 (ellen) és 1 értéket. (for).
Elektronikus aukciók. Minden résztvevő x i -t licitál , és az F(x 1 , …,x n ) függvény a maximális x i számot adja vissza .
Statisztika. Tegyük fel, hogy a tanulók a legjobb vagy átlagos osztályzatukat szeretnék tudni anélkül, hogy osztályzatokat mutatnának egymásnak.
Adatbázisok . Tegyük fel például, hogy a felhasználó le akar kérdezni egy adatbázist, és választ szeretne kapni anélkül, hogy felfedné a lekérdezést. Az adatbázissal rendelkező szerver tulajdonosa nem akarja, hogy a kérésre adott válaszon kívül más információ jusson el a felhasználóhoz a kérések során. Ebben az esetben a felhasználó és a szerver is részt vesz a bizalmas számítási protokollban.
Elosztott tanúsító hatóság . Tegyük fel, hogy létre kell hoznia egy hitelesítés-szolgáltatót, amely tanúsítványokat bocsát ki a felhasználóknak, és aláírja őket valamilyen titkos kulccsal. A kulcs védelme érdekében a kulcs felosztható több szerver között, így minden szerver megtartja a saját kulcsrészét. Ekkor felmerül a probléma: hogyan kell végrehajtani egy kriptográfiai műveletet (ebben a példában az aláírás kiadását) anélkül, hogy a kulcs minden részét át kellene vinni egy számítógépre. Ezt a problémát egy privát számítási protokoll segítségével oldják meg, ahol a privát számítási függvény bemenete a kulcselemek és az aláírt üzenet, a kimenet pedig az aláírt üzenet.

Jegyzetek

↑ Andrew Chi-Chih Yao: Protocols for Secure Computations (Extended Abstract) FOCS 1982: 160-164
↑ Yehuda Lindell, Benny Pinkas: A Yao protokolljának bizonyítéka a biztonságos kétoldalú számításokhoz, Cryptology ePrint Archívum, 2004/175-ös jelentés
↑ Megoldás a milliomos problémájára Archiválva : 2008. május 19.
↑ M. Ben-Or, S. Goldwasser és A. Wigderson. Teljességi tételek nem kriptográfiai hibatűrő elosztott számításokhoz. A 20. STOC-ban, 1988. 1-10.
↑ 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 és T. Toft. A biztonságos, többoldalú számítások életre kelnek. Pénzügyi kriptográfiában és adatbiztonságban – FC 2009
↑ A. Yao. Titkok generálása és cseréje. 27. FOCS, 162-167, 1986.
↑ Goldreich, S. Micali és A. Wigderson. Hogyan játssz bármilyen mentális játékot - Teljességi tétel a becsületes többségű protokollokhoz. 19. STOC, 218-229, 1987.
↑ P. Bogetoft, I. Damgard, T. Jakobsen, K. Nielsen, J. Pagter. és T. Toft. A biztonságos számítási aukciók gyakorlati megvalósítása többoldalú egész számok alapján. Pénzügyi kriptográfia és adatbiztonság – FC 2006, Springer-Verlag LNCS 4107, 142-147, 2006.
↑ D. Malkhi, N. Nisan, B. Pinkas és Y. Sella. A Fairplay egy biztonságos, kétoldalú számítási rendszer. In Proc. 13. USENIX Biztonsági Szimpózium, 2004.
↑ A. Ben-David, N. Nisan és B. Pinkas. FairplayMP: rendszer a biztonságos, több résztvevős számításokhoz. In Computer and Communications Security – CCS 2008, ACM, 257-266, 2008.
↑ Pathak Rohit, Joshi Satyadhar, Advances in Information Security and Assurance, Springer Berlin / Heidelberg, ISSN 0302-9743 (nyomtatott) 1611-3349 (online), ISBN 978-3-642-02616-4 , DOI8-7/7. -642-02617-1
↑ Rashid Sheikh, Brijesh Kumar és 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