Problém Yaos Millionaires - Yaos Millionaires problem - Wikipedia

Problém Yao's Millionaires je bezpečný výpočet více stran problém zavedený v roce 1982 počítačovým vědcem a výpočetním teoretikem Andrew Yao. Problém pojednává o dvou milionářích, Alice a Bobovi, kteří mají zájem vědět, který z nich je bohatší, aniž by odhalili jejich skutečné bohatství.

Tento problém je analogický obecnějšímu problému, kde jsou dvě čísla ${ displaystyle a}$ a ${ displaystyle b}$ a cílem je zjistit, zda je nerovnost ${ displaystyle a geq b}$ je true nebo false bez odhalení skutečných hodnot ${ displaystyle a}$ a ${ displaystyle b}$ .

Problém milionářů je důležitým problémem kryptografie, jehož řešení se používá v elektronický obchod a dolování dat. Komerční aplikace někdy musí porovnávat čísla, která jsou důvěrná a jejichž bezpečnost je důležitá.

Pro problém bylo zavedeno mnoho řešení, mezi nimiž bylo první řešení, které představil sám Yao, exponenciální v čase a prostoru.^[1]

Protokoly a důkazy

Protokol Hsiao-Ying Lin a Wen-Guey Tzeng

Nechat ${ displaystyle s = s_ {n} s_ {n-1} ldots s_ {1} in {0,1 } ^ {n}}$ být binární řetězec délky n.

Označte 0 kódování s tak jako ${ displaystyle S_ {s} ^ {0} = {s_ {n} s_ {n-1} ldots s_ {i + 1} 1 mid s_ {i} = 0; 1 leq i leq n }}$ a 1-kódování s tak jako ${ displaystyle S_ {s} ^ {1} = {s_ {n} s_ {n-1} ldots s_ {i} mid s_ {i} = 1; 1 leq i leq n }.}$

Potom protokol^[2] je založeno na následujícím nároku:

Předpokládat, že A a b jsou binární řetězce délky n bity.

Pak

{ displaystyle a> b}

pokud sady

{ displaystyle S_ {a} ^ {1}}

a

{ displaystyle S_ {b} ^ {0}}

mají společný prvek (kde A a b jsou binární kódování odpovídajících celých čísel).

Protokol využívá tuto myšlenku k praktickému řešení problému Yao's Millionaires provedením a soukromá množinová křižovatka mezi ${ displaystyle S_ {a} ^ {1}}$ a ${ displaystyle S_ {b} ^ {0}}$ .

Protokol Ioannidis a Ananth

Protokol^[3] používá variantu lhostejný přenos, nazvaný 1-2 zapomenutý převod. V tom přenosu jeden bit se přenáší následujícím způsobem: odesílatel má dva bity ${ displaystyle S_ {0}}$ a ${ displaystyle S_ {1}}$ . Přijímač si vybere ${ displaystyle i in {0,1 }}$ a odesílatel odešle ${ displaystyle S_ {i}}$ s lhostejným přenosovým protokolem takovým

přijímač neobdrží žádné informace o ${ displaystyle S _ {(1-i)}}$ ,
hodnota ${ displaystyle i}$ není vystaven odesílateli.

Pro popis protokolu je Alice číslo označeno jako ${ displaystyle a}$ Bobovo číslo jako ${ displaystyle b}$ , a předpokládá se, že délka jejich binární reprezentace je menší než ${ displaystyle d}$ pro některé ${ displaystyle d in mathbb {N}}$ . Protokol provede následující kroky.

Alice vytvoří matici ${ displaystyle K}$ velikosti ${ displaystyle d krát 2}$ z ${ displaystyle k}$ -bitová čísla, kde ${ displaystyle k}$ je délka klíče v lhostejném protokolu přenosu. Kromě toho si vybere dvě náhodná čísla ${ displaystyle u}$ a ${ displaystyle v}$ , kde ${ displaystyle 0 leq u <2k}$ a ${ displaystyle v leq k}$ .
${ displaystyle K_ {ijl}}$ ${ displaystyle K_ {ijl}}$ bude ${ displaystyle l}$ $l$ -tý bit čísla, které se objeví v buňce ${ displaystyle K_ {ij}}$ $K _ {{ij}}$ (kde ${ displaystyle l = 0}$ $l = 0$ označuje nejméně významný bit ). Navíc, ${ displaystyle a_ {i}}$ $a_ {i}$ je označen jako ${ displaystyle i}$ $i$ -tý kousek Aliceho čísla ${ displaystyle a}$ $A$ . Pro každého ${ displaystyle i}$ $i$ , ${ Displaystyle 1 leq i leq d}$ $1 leq i leq d$ Alice provádí následující akce.
1. Za každý kousek ${ displaystyle j geq v}$ ona nastaví ${ displaystyle K_ {i1j}}$ a ${ displaystyle K_ {i2j}}$ na náhodné bity.
2. Li ${ displaystyle a_ {i} = 1}$ , nechť ${ displaystyle l = 1}$ , jinak nech ${ displaystyle l = 2}$ a pro každého ${ displaystyle j, 0 leq j leq 2 cdot i-1}$ soubor ${ displaystyle K_ {ilj}}$ na náhodný bit.
3. Pro ${ displaystyle m = 2 cdot i}$ soubor ${ displaystyle K_ {il (m + 1)} = 1}$ a ${ displaystyle K_ {ilm}}$ na ${ displaystyle a_ {i}}$ .
4. Pro každého ${ Displaystyle i, 1 leq i$ , ${ displaystyle S_ {i}}$ bude náhodný ${ displaystyle k}$ -bitové číslo a ${ displaystyle S_ {d}}$ bude další počet ${ displaystyle k}$ bity, kde všechny bity kromě posledních dvou jsou náhodné a poslední dva jsou počítány jako ${ displaystyle S_ {d (k-1)} = 1 oplus bigoplus _ {j = 1} ^ {d-1} S_ {j (k-1)} oplus bigoplus _ {j = 1} ^ {d} K_ {j1 (k-1)}}$ a ${ displaystyle S_ {d (k-2)} = 1 oplus bigoplus _ {j = 1} ^ {d-1} S_ {j (k-2)} oplus bigoplus _ {j = 1} ^ {d} K_ {j1 (k-2)}}$ , kde ${ displaystyle bigoplus}$ je bitový XOR úkon.
5. Pro ${ displaystyle l = 1,2}$ soubor ${ displaystyle K '_ {ij} = operatorname {rot} (K_ {il} oplus S_ {i}, u)}$ . Kde ${ displaystyle operatorname {rot} (x, t)}$ označuje bitová rotace z ${ displaystyle x}$ nalevo od ${ displaystyle t}$ bity.
Pro každého ${ displaystyle i}$ , ${ displaystyle 0 leq i leq d}$ Bob převody ${ displaystyle K '_ {il}}$ s lhostejným přenosovým protokolem, kde ${ displaystyle l = b_ {i} +1}$ , a ${ displaystyle b_ {i}}$ je ${ displaystyle i}$ -tý kousek ${ displaystyle b}$ .
Alice pošle Bobovi ${ displaystyle N = operatorname {rot} left ( bigoplus _ {j = 1} ^ {d} S_ {j}, u right)}$ .
Bob vypočítá bitovou XOR všech čísel, která dostal v kroku 3 a ${ displaystyle N}$ od kroku 4. Bob skenuje výsledek zleva doprava, dokud nenajde velkou sekvenci nulových bitů. Nechat ${ displaystyle c}$ být kousek napravo od této sekvence ( ${ displaystyle c}$ je nenulová). Pokud bit vpravo od ${ displaystyle c}$ rovná se tedy 1 ${ displaystyle a geq b}$ , v opačném případě ${ displaystyle a$ .

Důkaz

Správnost

Bob vypočítá konečný výsledek z ${ displaystyle N oplus bigoplus _ {i = 1} ^ {d} K '_ {i (b_ {i} +1)} = operatorname {rot} left ( bigoplus _ {i = 1} ^ {d} K_ {i (b_ {i} +1)}, u vpravo)}$ a výsledek závisí na ${ displaystyle c = bigoplus _ {i = 1} ^ {d} K_ {i (b_ {i} +1)}}$ .K., a proto C také lze rozdělit na 3 části. Levá část nemá vliv na výsledek. Pravá část obsahuje všechny důležité informace a uprostřed je posloupnost nul, která odděluje tyto dvě části. Délka každého oddílu o C je spojeno se systémem zabezpečení.

Pro každého i, pouze jeden z ${ displaystyle K_ {i1}, K_ {i2}}$ má nenulovou pravou část a je ${ displaystyle K_ {i1}}$ -li ${ displaystyle a_ {i} = 1}$ , a ${ displaystyle K_ {i2}}$ v opačném případě. Kromě toho, pokud ${ displaystyle i> j}$ , a ${ displaystyle K_ {il}}$ má tedy nenulovou pravou část ${ displaystyle K_ {il} oplus K_ {jl}}$ má také nenulovou pravou část a dva bity nejvíce vlevo této pravé části budou stejné jako jedna z ${ displaystyle A_ {il}}$ . Výsledkem je, že pravá část C je funkce záznamů, které Bob přenesl, odpovídají jedinečným bitům v A a ba jediné bity v pravé části v C které nejsou náhodné, jsou dvě úplně vlevo, přesně ty bity, které určují výsledek ${ displaystyle a_ {i}> b_ {i}}$ , kde i je bit nejvyššího řádu, ve kterém A a b lišit. Nakonec, pokud ${ displaystyle a_ {i}> b_ {i}}$ , pak tyto dva kousky zcela vlevo budou 11 a Bob na to odpoví ${ displaystyle a geq b}$ . Pokud jsou bity 10, pak ${ displaystyle a_ {i}$ , a on odpoví ${ displaystyle a$ . Li ${ displaystyle a = b}$ , pak nebude žádná pravá část C, a v tomto případě dva nejvíce nalevo bity dovnitř C bude 11 a bude označovat výsledek.

Bezpečnostní

Informace, které Bob posílá Alici, jsou zabezpečené, protože jsou zasílány nepochopitelným přenosem, který je bezpečný.

Bob dostane od Alice 3 čísla:

${ displaystyle operatorname {rol} (K_ {i (1 + b_ {i})} oplus S_ {i}, u)}$ . Pro každého ${ displaystyle i}$ Bob obdrží jedno takové číslo a ${ displaystyle S_ {i}}$ je náhodný, takže se neprovádějí žádné zabezpečené informace.
N. Toto je XOR náhodných čísel, a proto neodhalí žádné informace. Relevantní informace se odhalí až po výpočtu C.
C. Totéž platí pro C. Levá část C je náhodný a pravá část je také náhodná, s výjimkou dvou bitů zcela vlevo. Dedukce jakékoli informace z těchto bitů vyžaduje hádání některých dalších hodnot a šance na správné hádání je velmi nízká.

Složitost

The složitost z protokol je ${ displaystyle O (d ^ {2})}$ . Alice konstrukty dčíslo délky pro každý bit Aa Bob vypočítá XOR d časy d-číselná čísla. Složitost těchto operací je ${ displaystyle O (d ^ {2})}$ . Součástí komunikace je také ${ displaystyle O (d ^ {2})}$ . Složitost protokolu je tedy ${ displaystyle O (d ^ {2}).}$

Viz také

Kryptografie
RSA
Bezpečné výpočty více stran
Socialistický milionář, varianta, ve které si milionáři přejí zjistit, zda je jejich štěstí stejné.

externí odkazy

Jednoduchý popis problému Milionář

Reference

^ Yao, Andrew C. (listopad 1982). Msgstr "Protokoly pro bezpečné výpočty". FOCS. 23. výroční sympozium o základech informatiky (FOCS 1982): 160–164. doi:10.1109 / SFCS.1982,88.
^ Lin, Hsiao-Ying; Tzeng, Wen-Guey (06.06.2005). Efektivní řešení problému milionářů založené na homomorfním šifrování. Aplikovaná kryptografie a zabezpečení sítě. Přednášky z informatiky. 3531. 456–466. CiteSeerX 10.1.1.75.4917. doi:10.1007/11496137_31. ISBN 978-3-540-26223-7.
^ Ioannidis, I .; Grama, A. (2003). Efektivní protokol pro problém milionářů Yao. 36. výroční mezinárodní konference na Havaji o systémových vědách, 2003. Sborník příspěvků. IEEE. CiteSeerX 10.1.1.110.8816. doi:10.1109 / hicss.2003.1174464. ISBN 978-0769518749.

[protocols-for-secure-computations-1] Yao, Andrew C. (listopad 1982). Msgstr "Protokoly pro bezpečné výpočty". FOCS. 23. výroční sympozium o základech informatiky (FOCS 1982): 160–164. doi:10.1109 / SFCS.1982,88.

[2] Lin, Hsiao-Ying; Tzeng, Wen-Guey (06.06.2005). Efektivní řešení problému milionářů založené na homomorfním šifrování. Aplikovaná kryptografie a zabezpečení sítě. Přednášky z informatiky. 3531. 456–466. CiteSeerX 10.1.1.75.4917. doi:10.1007/11496137_31. ISBN 978-3-540-26223-7.

[3] Ioannidis, I .; Grama, A. (2003). Efektivní protokol pro problém milionářů Yao. 36. výroční mezinárodní konference na Havaji o systémových vědách, 2003. Sborník příspěvků. IEEE. CiteSeerX 10.1.1.110.8816. doi:10.1109 / hicss.2003.1174464. ISBN 978-0769518749.

[1]

[2]

[3]