Transfer inconștient

Uitând de transfer ( de transfer uitând , în limba engleză) este un primitiv criptografic în cazul în care o transmite informațiile referitoare la expeditor, selectat dintre mai multe posibil transfer la un destinatar, fără ca expeditorul poate cunoaște alegerea destinatarului, sau destinatarul să cunoască informațiile el nu a făcut cere. De exemplu, Wikipedia oferă mai multe articole; cu redirecționarea inconștientă, un utilizator poate solicita vizualizarea unui articol fără ca Wikipedia să poată ști care articol a fost vizualizat.

Această primitivă a fost introdusă în 1981 de Michael Rabin , într-un manuscris intitulat Cum să schimbi secretele cu un transfer ignorant . În versiunea Rabin, bazată pe criptare RSA , expeditorul transmite un mesaj pe care destinatarul îl primește cu o probabilitate de 1/2, fără ca expeditorul să poată ști dacă recepția a avut loc sau nu. În 1985 , lucrările lui Even , Goldreich și Lempel au propus o versiune îmbunătățită a transferului inconștient 1-la-2, care a făcut posibilă efectuarea unui calcul multipart sigur într- un mod sigur . Acest rezultat a fost apoi îmbunătățit de Killian, arătând că transferul inconștient 1-la-2 a fost suficient pentru a evalua multipartit orice funcție în timp polinomial . Acest rezultat este unul dintre motivele interesului existent în jurul acestei primitive.

Definiție

Definiția lui Michael Rabin era pentru un protocol astfel încât expeditorul să trimită un mesaj M destinatarului, dar cu o probabilitate de 1/2 de a pierde mesajul. Expeditorul nu știa dacă mesajul său a sosit în siguranță. Claude Crépeau a arătat că această definiție este echivalentă cu cea utilizată în definiția sa actuală: transferul inconștient 1 dintre 2. Rezultate similare au fost prezentate de Khurana, Maji și Sahai, folosind un canal zgomotos (cu o rată strict de eroare mai mică de 1/2 ) .

1 din 2 transfer inconștient

O schemă de transfer inconștient este dată de doi algoritmi interactive: expeditorul și destinatarul . Expeditorul ia ca intrare două mesaje și , în timp ce destinatarul ia ca intrare un pic σ. Se remarcă interacțiunea dintre cele două părți . $S$ $R$ $M_ {0}$ $M_ {1}$ ${\ displaystyle S ^ {M_ {0}, M_ {1}} \ leftrightarrows R ^ {\ sigma}}$

Conceptele de securitate asociate sunt securitatea expeditorului și securitatea destinatarului.

De securitate destinatarului impune ca distribuții și sunt imposibil de distins . Acest lucru reflectă faptul că expeditorul nu poate ști ce mesaj a solicitat destinatarul. ${\ displaystyle S ^ {M_ {0}, M_ {1}} \ leftrightarrows R ^ {0}}$ ${\ displaystyle S ^ {M_ {0}, M_ {1}} \ leftrightarrows R ^ {1}}$
Securitatea expeditorului ca pentru ea reflectă faptul că expeditorul care a solicitat nu trebuie să fie în măsură să știe nimic despre mesajul de la sfârșitul schimbului. ${\ displaystyle M _ {\ sigma}}$ ${\ displaystyle M_ {1- \ sigma}}$

Alice ( ) $S$				Bob ( ) $R$
Calcule	Secret	Public		Public	Secret	Calcule
Mesaje de trimis	${\ displaystyle M_ {0}, M_ {1}}$
Creați o pereche de chei RSA și trimiteți cheia publică lui Bob	$d$	${\ displaystyle N, e}$	$\ Sageata dreapta$	${\ displaystyle N, e}$		Primirea cheii publice a lui Alice
Generarea a două mesaje aleatorii		$x_ {0}, x_ {1}$	$\ Sageata dreapta$	$x_ {0}, x_ {1}$		Primirea a două mesaje aleatorii
					${\ displaystyle k, \ sigma}$	Alegerea și generarea unui număr aleatoriu ${\ displaystyle \ sigma \ in \ {0,1 \}}$ $k$
		$v$	$\ Sageata stanga$	${\ displaystyle v = (x _ {\ sigma} + k ^ {e}) \ mod N}$		Calculați criptarea cu și trimiteți rezultatul către Alice $k$ ${\ displaystyle x _ {\ sigma}}$
Calculul celor două valori posibile pentru , $k$ dintre care doar una corespunde cu cea a lui Bob	${\ displaystyle {\ begin {align} k_ {0} & = (v-x_ {0}) ^ {d} \ mod N \\ k_ {1} & = (v-x_ {1}) ^ {d} \ mod N \ end {align}}}$
Trimiterea ambelor mesaje lui Bob		${\ displaystyle {\ begin {align} M '_ {0} = M_ {0} + k_ {0} \\ M' _ {1} = M_ {1} + k_ {1} \ end {align}}}$	$\ Sageata dreapta$	${\ displaystyle M '_ {0}, M' _ {1}}$		Primirea ambelor mesaje
					${\ displaystyle M _ {\ sigma} = M '_ {\ sigma} -k}$	Decriptarea mesajului , grație celui ales anterior. ${\ displaystyle M '_ {\ sigma}}$ ${\ displaystyle x _ {\ sigma}}$

Alice oferă să-i trimită lui Bob unul dintre cele două mesaje disponibile și . Bob vrea să aleagă unul dintre cele două mesaje de primit, fără ca Alice să poată ști care dintre ele. $M_ {0}$ $M_ {1}$
Alice generează o pereche de chei RSA, adică un modulo , un exponent public și un exponent privat . $NU$ $e$ $d$
De asemenea, generează două mesaje aleatorii și ea îi trimite lui Bob împreună cu cheia sa publică . $x_ {0}$ $x_ {1}$ ${\ displaystyle (N, e)}$
Bob alege mesajul pe care vrea să îl primească, indicat de . Prin urmare, selectează valoarea corespunzătoare . ${\ displaystyle \ sigma \ in \ {0,1 \}}$ ${\ displaystyle x _ {\ sigma}}$
Bob generează un număr aleatoriu și criptează cu calculul pe care îl trimite la Alice. $k$ $k$ ${\ displaystyle x _ {\ sigma}}$ ${\ displaystyle v = (x _ {\ sigma} + k ^ {e}) \ mod N}$
Pentru Alice, este imposibil să se determine dacă Bob a ales sau să calculeze, deoarece ignoră numărul generat de Bob. Prin urmare, calculează cele două valori posibile pentru de la : și . Una dintre aceste două valori este egală cu cea aleasă de Bob (fără ca Alice să știe care dintre ele), iar cealaltă este o valoare aleatorie care nu furnizează nicio informație, ceea ce garantează siguranța destinatarului. $x_ {0}$ $x_ {1}$ $v$ $k$ $k$ $v$ ${\ displaystyle k_ {0} = (v-x_ {0}) ^ {d} \ mod N}$ ${\ displaystyle k_ {1} = (v-x_ {1}) ^ {d} \ mod N}$ $k$ $k$
Alice ascunde mesajele și cu cele două chei posibile și pentru a da și . Aceste două mesaje sunt trimise lui Bob. $M_ {0}$ $M_ {1}$ $k_ {0}$ $k_ {1}$ ${\ displaystyle M '_ {0} = M_ {0} + k_ {0}}$ ${\ displaystyle M '_ {1} = M_ {1} + k_ {1}}$
Bob decriptează mesajul cu cel ales de el, pentru a obține . Bob nu poate descifra celălalt mesaj. Într-adevăr, ar trebui să fie în măsură să calculeze cealaltă valoare , adică a ceea ce nu poate face fără cheia privată a lui Alice. Acest lucru garantează siguranța expeditorului. ${\ displaystyle M '_ {\ sigma}}$ $k$ ${\ displaystyle M _ {\ sigma} = M '_ {\ sigma} -k}$ $k$ ${\ displaystyle k_ {1- \ sigma}}$

Transfer inconștient 1 între n și k dintre n

Transferul inconștient 1 în n poate fi generalizat din protocolul 1 în 2 detaliat mai sus. Expeditorul are n mesaje și destinatarul alege un index i între 0 și n - 1 corespunzător mesajului pe care dorește să îl primească, fără ca expeditorul să poată ști ce mesaj a fost ales sau destinatarul să poată citi un alt mesaj decât cea pe care a selectat-o. Sunt posibile și alte implementări.

Un alt exemplu de implementare 1 în n

Să presupunem că Alice are secrete binare care sunt fie 0, fie 1. Să presupunem că Bob vrea să știe secretul . Un protocol de transfer inconștient poate fi după cum urmează: $m$ ${\ displaystyle s_ {1}, \ dots, s_ {m}}$ $dacă}$

Alice alege două numere prime și și un număr care nu este un modulo rezidual pătratic și astfel încât simbolul Jacobi este egal cu 1; $p$ $q$ $la$ ${\ displaystyle n = pq}$ ${\ displaystyle \ left ({\ frac {a} {n}} \ right)}$
Alice publică și ; $la$ $nu$
Alice asociază un număr aleatoriu cu fiecare secret și îi trimite lui Bob numerele ; ${\ displaystyle x_ {i} \ neq 0}$ $dacă}$ $m$ ${\ displaystyle y_ {i}: = x_ {i} ^ {2} a ^ {s_ {i}} \ mod n}$
Bob generează un număr aleatoriu și un bit aleatoriu și îi trimite lui Alice numărul ; $r$ ${\ displaystyle b \ in \ {0,1 \}}$ ${\ displaystyle \ delta _ {i} = y_ {i} r ^ {2} a ^ {b}}$
Alice îi spune lui Bob dacă numărul este un reziduu pătratic modulo . Dacă da, atunci altfel . ${\ displaystyle \ delta _ {i}}$ $nu$ ${\ displaystyle s_ {i} = b}$ ${\ displaystyle s_ {i} = 1-b}$

Acest protocol se bazează în esență pe ideea că a decide dacă întregul este un reziduu pătratic modulo ${\ displaystyle \ delta _ {i}}$ $nu$ este ușor dacă factorii primi ai sunt cunoscuți, ca în cazul lui Alice, și imposibil într-un timp rezonabil altfel, ca în cazul lui Bob. $nu$

Comparație cu PIR-uri

Transferul inconștient 1 în n este, prin urmare, mai restrictiv decât protocoalele PIR ( recuperarea informațiilor private (en) ) care necesită doar securitatea destinatarului (expeditorul nu poate ști ce mesaj a fost transmis). Pe de altă parte, protocoalele PIR sunt în general mai economice în ceea ce privește cantitatea de date transmise efectiv. Într-adevăr, în protocolul 1 între n , Alice îi trimite neapărat n mesaje lui Bob (chiar dacă el poate citi doar unul), în timp ce protocoalele PIR sunt adesea subliniate în n .

Generalizare

Gilles Brassard , Claude Crépeau și Jean-Marc Robert au propus o generalizare a transferului k între n , în care destinatarul poate selecta mai multe mesaje dintre cele propuse de expeditor. Cele k Mesajele pot fi primite simultan sau consecutiv, fiecare mesaj nou fiind capabil de a fi ales în funcție de mesajele primite anterior

Interogări adaptive

Note și referințe

Note

(fr) Acest articol este preluat parțial sau în totalitate din articolul Wikipedia în limba engleză intitulat „ Transfer fără cunoștințe ” ( vezi lista autorilor ) .

În această implementare, secretul poate fi doar pe un singur bit, ca un răspuns da / nu la o întrebare închisă.
Acest protocol este dat în scopuri educaționale, este într-adevăr vulnerabil la atacuri.
Această condiție este necesară pentru a se asigura ulterior că Bob nu poate înșela: dacă sau Bob poate ști dacă numerele calculate în restul protocolului nu sunt reziduuri modulo pătratice , în timp ce dacă nu poate concluziona. Pentru mai multe detalii, consultați articolul detaliat . ${\ displaystyle \ left ({\ frac {a} {n}} \ right) = - 1}$ ${\ displaystyle \ left ({\ frac {a} {n}} \ right) = 0}$ $nu$ ${\ displaystyle \ left ({\ frac {a} {n}} \ right) = 1}$
Deci avem ${\ displaystyle \ delta _ {i} = x_ {i} ^ {2} a ^ {s_ {i} + b} r ^ {2}}$
Like , este un pătrat dacă și numai dacă . ${\ displaystyle \ delta _ {i} = x_ {i} ^ {2} a ^ {s_ {i} + b} r ^ {2}}$ ${\ displaystyle \ delta _ {i}}$ ${\ displaystyle s_ {i} + b \ in \ {0.2 \}}$

Referințe

Rabin 1981 , titlul original este How to exchange secrets , dar este citat în mod obișnuit sub acel titlu.
Even, Goldreich și Lempel 1985 .
Killian 1988 .
Crépeau 1987 .
Khurana, Maji și Sahai 2016 .
Naor și Pinkas 2001 .
Camenisch, Neven și shelat 2007 .
Pascal Boyer, Micul companion al numerelor și al aplicațiilor lor , Paris, Calvage și Mounet,2019, 648 p. ( ISBN 978-2-916352-75-6 ) , VI. Criptografie, cap. 7.8 („Transfer inconștient”)
(en) Victor Shoup , O introducere de calcul la teoria numerelor și algebră , Cambridge University Press ,2009, A 2 -a ed. , 580 p. ( ISBN 978-0-521-51644-0 și 0521516447 , OCLC 277069279 , citit online ) , 12. Reciprocitate quadratică și calculul rădăcinilor pătrate modulare, cap. 4 („Testarea reziduității pătratice”) , p. 349.
Gilles Brassard , Claude Crépeau și Jean-Marc Robert , „ Dezvăluirea tuturor secretelor ”, Proceedings on Advances in cryptology - CRYPTO '86 , Springer-Verlag,1987, p. 234–238 ( ISBN 9780387180472 , citit online , accesat la 20 februarie 2019 )
Naor și Pinkas 1999 .

Anexe

Bibliografie

[Camenisch, Neven and shelat 2007] Jan Camenisch, Gregory Neven și abhi shelat, „ Simulatable Adaptive Oblivious Transfer ”, Eurocrypt ,2007, p. 573–590 ( DOI 10.1007 / 978-3-540-72540-4_33 )
[Crépeau 1987] (ro) Claude Crépeau, „ Echivalența dintre două arome de transfer ignorant ” , Crypto ,1987, p. 350–354 ( DOI 10.1007 / 3-540-48184-2_30 )
[Even, Goldreich și Lempel 1985] (ro) Shimon Even, Oded Goldreich și Abraham Lempel, „ Un protocol randomizat pentru semnarea contractelor ” , Communications of the ACM , vol. 28,1985, p. 637–647 ( DOI 10.1145 / 3812.3818 , citiți online [PDF] )
[Khurana, Maji și Sahai 2016] (ro) Dakshita Khurana, Hemanta K. Maji și Amit Sahai, „ Secure Computation from Elastic Noisy Channels ” , Eurocrypt ,2016, p. 184–212 ( DOI 10.1007 / 978-3-662-49896-5_7 , rezumat )
[Killian 1988] (ro) Joe Killian, „ Founding Cryptography on Oblivious Transfer ” , Simpozion despre teoria calculelor (STOC) ,1988, p. 20–31 ( DOI 10.1145 / 62212.62215 )
[Naor și Pinkas 1999] (ro) Moni Naor și Benny Pinkas, „ Transfer ignorat cu interogări adaptative ” , Crypto ,1999, p. 573–590 ( DOI 10.1007 / 3-540-48405-1_36 )
[Naor și Pinkas 2001] (ro) Moni Naor și Benny Pinkas, „ Efficient Oblivious Transfer ” , Simpozionul pe algoritmi discreți (SODA) ,2001, p. 448−457 ( ISBN 0-89871-490-7 , citiți online [ps] )
[Rabin 1981] (ro) Michael O. Rabin, „ How To Exchange Secrets with Oblivious Transfer ” , IACR Museum of Historic Papers ,nouăsprezece optzeci și unu( citiți online [html] )

Articole similare