Sarcina milionarilor socialiști

Problema milionarilor socialiști ( SMP , problema Tierce) este o problemă criptografică în care doi milionari vor să afle dacă averea lor este egală fără a dezvălui sumele exacte. Soluția la această problemă este folosită ca protocol criptografic , care permite două părți să autentifice un participant la distanță cu un secret partajat, evitând un atac de tip man-in-the-middle , fără a fi nevoie să compare manual amprentele cheilor publice printr-un alt canal.

Istorie

Problema calculului multilateral securizat a fost ridicată pentru prima dată de Andrew Yao în 1982 [1] . Doi milionari, Alice și Bob, vor să afle care dintre ei este mai bogat, în timp ce nu vor să dezvăluie valoarea exactă a averii lor. Yao a propus în articolul său o modalitate originală de a rezolva problema, care mai târziu a devenit cunoscută sub numele de „ Problema Milionarilor a lui Yao ”. Într-o lucrare din 1996 a lui Markus Jacobsson și Moti Jung, cazul special în care Alice și Bob vor să afle dacă averile lor sunt egale a fost numit Problema milionarului socialist [2] . O altă variantă a numelui este „Tierce problem” (tierce este un joc de pariuri francez): se înțelege că doi jucători vor să afle dacă au aceeași combinație de pariuri [3] .

O soluție eficientă la problema milionarului socialist a fost propusă în 2001 de Fabrice Boudot, Berry Schoenmakers și Jacques Traore [ 4] . A fost implementat în protocolul OTR (Off-the-record) după ce Oliver Goffart a publicat un modul pentru mod_otrserverul ejabberd în 2007 care permite atacuri automate de tip man-in-the-middle împotriva utilizatorilor OTR care nu își verifică reciproc amprentele digitale ale cheii publice [ 4] .

Proprietăți

Alice și Bob cunosc secretele și respectiv. $X$ $y$

Proprietăți care trebuie să fie prezente în protocolul de interacțiune [5] :

Fără scurgere de informații: presupunând că Alice și Bob urmează protocolul cu bună-credință, nu ar trebui să știe nimic mai mult decât dacă secretele lor se potrivesc sau nu.
Confidențialitate: Nimeni altcineva nu ar trebui să cunoască secretele lui Alice și Bob. Un intrus activ, capabil să interfereze în mod arbitrar cu comunicarea lui Alice și Bob, nu trebuie să învețe mai mult decât un intrus pasiv.
Securitate: Nici Alice, nici Bob nu trebuie păcăliți. Dacă unul dintre ei nu respectă protocolul, mai trebuie să învețe secretul interlocutorului doar dacă și se potrivește . $X$ $y$
Simplitate: Protocolul trebuie să fie ușor de implementat și de înțeles, adică Alice și Bob nu trebuie să cheltuiască mult timp, energie și bani pentru a utiliza protocolul.
Depărtare: Alice și Bob nu trebuie să fie fizic în același loc pentru a afla dacă secretele se potrivesc.

Soluție fără criptografie

Soluția problemei poate fi prezentată într-o formă vizuală, fără criptografie .

Situație: Un angajat s-a plâns de o problemă sensibilă lui Alice, un manager al companiei, și a cerut ca identitatea sa să fie păstrată anonimă. Un timp mai târziu, Bob, un alt manager, i-a spus Alicei că cineva i-a plâns, cerându-i și confidențialitate. Alice și Bob vor să stabilească dacă a fost aceeași persoană fără a divulga numele.

cupe

Această metodă necesită să nu fie prea mulți candidați, să zicem douăzeci. Alice și Bob trebuie să ia douăzeci de recipiente identice, de exemplu, pahare de unică folosință, să lipească o etichetă cu un nume pe fiecare ceașcă (una pentru candidat). Alice ar trebui să pună bucata de hârtie împăturită cu cuvântul „da” în paharul persoanei care s-a plâns și bucățile de hârtie cu cuvântul „nu” în celelalte nouăsprezece cești. Bob trebuie să facă la fel. Apoi trebuie să îndepărteze etichetele și să rearanjeze cupele la întâmplare. Dacă într-una dintre cupe sunt două frunze cu cuvântul „da”, atunci aceeași persoană le-a plâns [5] .

Pachetul de cărți

Această metodă este potrivită pentru cazurile în care lista de candidați este mare sau nu este definită. Acesta folosește faptul că numărul de cărți de joc dintr-un pachet obișnuit este de două ori mai mare decât numărul de litere din alfabetul latin. Un pachet de 52 de cărți trebuie împărțit după culoare în două pachete de 26 de cărți. Apoi amestecați fiecare pachet și puneți-l cu fața în jos pe masă. Există 26 de iterații în total. La a treia iterație, Alice scoate cartea de sus din fiecare pachet, le stivuiește față în față și le răstoarnă astfel încât cartea din pachetul roșu să fie deasupra. Apoi ascunde cărțile la spate și le răstoarnă dacă numele angajatului care a reclamat are litera -i în alfabet. După aceea, ea trebuie să-i dea cărțile lui Bob, care trebuie să ascundă cărțile la spatele lui, să le întoarcă dacă există o literă în nume și apoi să le pună pe masă. Procedura trebuie repetată din nou. După aceea, cărțile trebuie împăturite într-o singură grămadă și amestecate. Un cartonaș roșu cu fața în sus semnalează că secretele nu se potrivesc [5] . $i$ $i$ $i$ $26-i$

Soluție criptografică

Datele inițiale

$q$ - un număr prim mare, modulo care se fac toate calculele
$x,y$ , secretele lui Alice și, respectiv, Bob
$g_{1}$ - primul generator

Este necesar să aflați dacă secretele lui Alice și Bob sunt aceleași, . $x=y$

Crearea generatoarelor

Alice alege un număr , Bob alege . Apoi schimbă și (verificând că nu sunt egale cu 1) și ambele calculează (calculele se efectuează modulo , adică = ). $a_{2}$ $b_{2}$ $g_{1}^{a_{2))$ $g_{1}^{b_{2))$ $g_{2}=g_{1}^{a_{2}b_{2}}$ $q$ $g_{2}$ $g_{1}^{a_{2}}{\bmod {q}}$
După aceea, ei repetă procedura, generând altele noi , schimbând și (verificând că nu sunt egale cu 1) și calculând . $a_{3},b_{3)$ $g_{1}^{a_{3))$ $g_{1}^{b_{3))$ $g_{3}=g_{1}^{a_{3}b_{3))$
$a_{3}$ și trebuie reținut pentru utilizare ulterioară. $b_{3}$

„Ambalaj” și $x$ $y$

Alice alege , calculează și . Bob alege , calculează și . Există un schimb . $A$ $P_{a}=g_{3}^{a}$ $Q_{a}=g_{1}^{a}g_{2}^{x}$ $b$ $P_{b}=g_{3}^{b)$ $Q_{b}=g_{1}^{b}g_{2}^{y)$ $P_{a},Q_{a},P_{b},Q_{b)$

Examinare $x=y$

Alice calculează , Bob calculează , ei schimbă aceste valori și calculează . $R_{a}={\Biggl (}{\frac {Q_{a}}{Q_{b}}}{\Biggr )}^{a_{3}}$ $R_{b}={\Biggl (}{\frac {Q_{a}}{Q_{b}}}{\Biggr )}^{b_{3}}$ $R_{ab}=R_{a}^{b_{3}}=R_{b}^{a_{3}}$
În acest moment, ambele părți știu că . $R_{ab}={\Biggl (}{\frac {Q_{a}}{Q_{b}}}{\Biggr )}^{a_{3}b_{3}}=(g_{1 }^{ab}g_{2}^{xy})^{a_{3}b_{3}}=g_{3}^{ab}g_{2}^{(xy)a_{3}b_{3 }}={\Biggl (}{\frac {P_{a}}{P_{b}}}{\Biggr )}(g_{2}^{a_{3}b_{3}})^{xy}$
Adică, pentru a verifica , trebuie să verificați $x=y$ $R_{ab}={\Biggl (}{\frac {P_{a}}{P_{b}}}{\Biggr ))$

Caracteristici de implementare în OTR

OTR utilizează grupul de 1536 de biți descris în RFC 3526, cunoscut și sub numele de grupul Diffie-Hellman 5. Pentru securitate, hash-ul SHA-256 al ID -ului sesiunii, amprentele cheii publice ale ambelor părți și secretele originale ale lui Alice și Bob [4] sunt comparați .

Securitate

Securitatea protocolului se bazează pe ipotezele standard în criptografie [3] :

Ipoteza DL ( logaritmul discret ) pentru grup este că , nu poate fi calculată într-un timp rezonabil. $G_{q)$ $\log _{q}y$ $g,y\in G_{q},g\neq 1$
Ipoteza DH ( Diffie-Hellman ) pentru grup este că este imposibil de calculat , știind că este arbitrar . $G_{q)$ $g^{ab}$ $g,g^{a},g^{b)$ $a,b$
DDH ( decizional Diffie-Hellman ) ipoteza pentru un grup că este imposibil de determinat (care este echivalent cu ) știind pentru arbitrar . $G_{q)$ $c=ab$ $g^{c}=g^{ab)$ $g,g^{a},g^{b},g^{c)$ $a,b,c$

Vezi și

Note

↑ Andrew Chi-Chih Yao. Protocoale pentru calcule sigure // Fundamente ale informaticii. - 1982. Arhivat la 8 august 2017.
↑ Markus Jakobsson, Moti Yung. Demonstrarea fără să știe: Pe dovezitori ignoranți, agnostici și legați la ochi. // Progrese în criptologie—CRYPTO'96. - 1996. - S. 189 . Arhivat din original pe 14 octombrie 2017.
↑ 1 2 3 Fabrice Boudot, Berry Schoenmakers, Jacques Traore. O soluție corectă și eficientă la problema milionarilor socialiști // Matematică aplicată discretă. - 2001. - S. 3 . Arhivat din original pe 22 septembrie 2017.
↑ 1 2 3 Chris Alexander, Ian Goldberg. Autentificare îmbunătățită a utilizatorilor în mesajele Off-The-Record // Confidențialitate în societatea electronică. - 2007. - S. 4, 5 . Arhivat din original pe 29 octombrie 2017.
↑ 1 2 3 Ronald Fagin, Moni Naor, Peter Winkler. Compararea informațiilor fără a le scurge // Comunicațiile ACM. - 1996. - S. 5, 10, 11 . Arhivat din original pe 9 august 2017.