Yaos miljonärers problem

Yaos miljonärsproblem är ett säkert flerpartsberäkningsproblem som introducerades 1982 av datavetaren och beräkningsteoretikern Andrew Yao . Problemet diskuterar två miljonärer, Alice och Bob, som är intresserade av att veta vem av dem som är rikare utan att avslöja deras faktiska rikedom.

Detta problem är analogt med ett mer generellt problem där det finns två siffror $a$ och $b$ och målet är att avgöra om olikheten $a\geq b$ är sann eller false utan att avslöja de faktiska värdena för $a$ och $b$ .

Miljonärernas problem är ett viktigt problem inom kryptografi , vars lösning används inom e-handel och datautvinning . Kommersiella applikationer måste ibland jämföra nummer som är konfidentiella och vars säkerhet är viktig.

Många lösningar har införts för problemet. Den första lösningen, presenterad av Yao, är exponentiell i tid och rum.

Protokoll och bevis

Hsiao-Ying Lins och Wen-Guey Tzengs protokoll

Låt $s=s_{n}s_{n-1}\ldots s_{1}\in \{0,1\}^{ n}$ vara en binär sträng med längden n .

Beteckna 0-kodning av s som $S_{s}^{0}=\{s_{n}s_{n-1}\ldots s_{i+1}1\mid s_{i}=0;1\ leq i\leq n\}$ och 1-kodning av s som $S_{s}^{1}=\{s_{n}s_{n-1}\ldots s_{i}\mid s_{i}=1;1\leq i\leq n\}.$

Sedan är protokollet baserat på följande påstående:

Antag att a och b är binära strängar med längden n bitar.

Då har $a>b$ om mängderna $S_{a}^{1}$ och $S_{b}^{0}$ ett gemensamt element (där a och b är de binära kodningarna för motsvarande heltal).

Protokollet utnyttjar denna idé till en praktisk lösning på Yaos miljonärers problem genom att utföra en privat uppsättning korsning mellan $S_{a}^{1}$ och $S_{b}^{0}$ .

Ioannidis och Ananths protokoll

Protokollet använder en variant av oblivious transfer , kallad 1-2 oblivious transfer. I den överföringen överförs en bit på följande sätt: en avsändare har två bitar $S_{0}$ och $S_{1}$ . Mottagaren väljer $i\in \{0,1\}$ , och avsändaren skickar $S_{i}$ med det oblivious överföringsprotokollet så att

1. mottagaren får ingen information om $S_{(1-i)}$ ,
2. värdet av $i$ exponeras inte för avsändaren.

För att beskriva protokollet indikeras Alices nummer som $a$ , Bobs nummer som $b$ , och det antas att längden på deras binära representation är mindre än $d$ för vissa $d\in \mathbb {N}$ . Protokollet tar följande steg.

1. Alice skapar en matris $K$ av storleken $d\times 2$ av $k$ -bittal, där $k$ är längden på nyckeln i det oblivious överföringsprotokoll. Dessutom väljer hon två slumpmässiga tal $u$ och $v$ , där $0\leq u<2k$ och $v\leq k$ .
2. $K_{ijl}$ kommer att vara den $l$ -te biten av talet som visas i cell $K_{ij}$ (där $l =0$ indikerar den minst signifikanta biten ). Dessutom betecknas ${\displaystyle a_{i}} som den$$i$ -te biten av Alices tal $a$ . För varje $i$ , $1\leq i\leq d$ utför Alice följande åtgärder.
   1. För varje bit $j\geq v$ sätter hon $K_{i1j}$ och $K_{i2j}$ till slumpmässiga bitar.
   2. Om $a_{i}=1$ , låt $l=1$ , annars låt $l=2$ och för varje $j,\ 0\leq j\leq 2\cdot i-1$ sätter $K_{ilj}$ till en slumpmässig bit.
   3. För $m=2\cdot i$ sätt $K_{il(m+1)}=1$ och $K_{ilm}$ till $a_{i}$ .
   4. För varje $displaystyle i,1\leq i<d} ,$$S_{i}$ kommer att vara ett slumpmässigt $k$ -bittal, och ${ \displaystyle S_{d}}$ kommer att vara ytterligare ett antal $k$ bitar där alla bitar utom de två sista är slumpmässiga, och de två sista beräknas som $S_{d(k-1)}=1\oplus \bigoplus _{j=1}^{ d-1}S_{j(k-1)}\oplus \bigoplus _{j=1}^{d}K_{j1(k-1)}$ och ${\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)}} , där ⨁ {\displaystyle$ \ $}$ är bitvis XOR- operation.
   5. För $l=1,2$ set $K'_{ij}=\operatörsnamn {rot} (K_ {il}\oplus S_{i},u)$ . Där $\operatorname {rot} (x,t)$ indikerar den bitvisa rotationen av $x$ åt vänster med $t$ bitar.
3. För varje $i$ , $0\leq i\leq d$ överför Bob $K'_{il}$ med det omedvetna överföringsprotokollet, där $l=b_{i}+1$ , och $b_{i}$ är den $i$ -te biten av $b$ .
4. Alice skickar till Bob $N=\operatörsnamn {rot} \left(\bigoplus _{j=1}^{d}S_{j},u \right)$ .
5. Bob beräknar den bitvisa XOR av alla siffror han fick i steg 3 och $N$ från steg 4. Bob skannar resultatet från vänster till höger tills han hittar en stor sekvens med nollbitar. Låt $c$ vara biten till höger om den sekvensen ( $c$ är inte noll). Om biten till höger om $c$ är lika med 1, då $a\geq b$ , annars $a<b$ .

Bevis

Rätthet

Bob beräknar slutresultatet från $N\oplus \bigoplus _{i=1}^{d}K'_{i(b_{i}+1)}=\operatörsnamn {rot} \left(\bigoplus _{i=1}^{d}K_{i(b_) {i}+1)},u\right)$ , och resultatet beror på $c=\bigoplus _{i=1}^{d }K_{i(b_{i}+1)}$ . K , och därför även c , kan delas upp i 3 delar. Den vänstra delen påverkar inte resultatet. Den högra delen har all viktig information, och i mitten finns en sekvens av nollor som skiljer de två delarna åt. Längden på varje partition av c är kopplad till säkerhetsschemat.

För varje i har endast en av $K_{i1},K_{i2}$ höger del som inte är noll, och det är $K_{i1}$ om $a_{i}=1$ , och $K_{i2}$ annars. Dessutom, om $i>j$ och $K_{il}$ har en höger del som inte är noll, då $K_{il} \oplus K_{jl}$ har också en högerdel som inte är noll, och de två bitarna längst till vänster i denna högra del kommer att vara samma som den av $A_{il}$ . Som ett resultat är den högra delen av c en funktion av posterna som Bob överförde motsvarar de unika bitarna i a och b , och de enda bitarna i den högra delen i c som inte är slumpmässiga är de två längst till vänster, exakt de bitar som bestämmer resultatet av $a_{i}>b_{i}$ , där i är den högsta ordningens bit där a och b skiljer sig åt. I slutändan, om $a_{i}>b_{i}$ , så blir de två bitarna längst till vänster 11, och Bob kommer att svara att $a\geq b$ . Om bitarna är 10, då ${\displaystyle a_{i}<b_{i}} ,$ och han kommer att svara $a<b$ . Om $a=b$ kommer det inte att finnas någon högerdel i c , och i detta fall kommer de två bitarna längst till vänster i c att vara 11, och kommer att indikera resultatet.

säkerhet

Informationen som Bob skickar till Alice är säker eftersom den skickas genom omedveten överföring, vilket är säkert.

Bob får 3 nummer av Alice:

1. $\operatörsnamn {rol} (K_{i(1+b_{i})}\oplus S_{i},u)$ . För varje $i$ får Bob ett sådant nummer, och $S_{i}$ är slumpmässigt, så ingen säker information omvandlas.
2. N . Detta är en XOR av slumpmässiga tal, och avslöjar därför ingen information. Den relevanta informationen avslöjas först efter beräkning av c .
3. c . Detsamma gäller för c . Den vänstra delen av c är slumpmässig, och den högra delen är också slumpmässig, förutom de två bitarna längst till vänster. Att härleda all information från dessa bitar kräver att man gissar några andra värden, och chansen att gissa dem korrekt är mycket låg.

Komplexitet

Protokollets komplexitet är $O(d^{2$ ) } . Alice konstruerar d -längdsnummer för varje bit av a , och Bob beräknar XOR d gånger av d -längdstalen. Komplexiteten för dessa operationer är $O(d^{2})$ . Kommunikationsdelen tar också $O(d^{2})$ . Därför $O(d^{2}).$ protokollets komplexitet

Se även

• Kryptografi
• RSA
• Säker flerpartsberäkning
• Socialistiskt miljonärsproblem , en variant där miljonärerna vill avgöra om deras förmögenheter är lika.