Glömsk överföring

Oblivious transfer (ofta förkortad som OT - oblivious transfer) - i kryptografi , en typ av dataöverföringsprotokoll där sändaren sänder en möjlig information till mottagaren, men inte kommer ihåg (är glömsk) vilka delar som överfördes, om någon .

Den första formen av glömsk överföring introducerades 1981 av Michael O. Rabin 1 . I denna form sänder sändaren ett meddelande till mottagaren med en sannolikhet på 1/2, utan att komma ihåg om meddelandet togs emot av mottagaren eller inte. Den omedvetna Rabin-algoritmen är baserad på RSA -kryptosystemet. En mer användbar form av det glömska protokollet kallas 1-2 glömsk överföring eller "1 av 2 glömsk överföring", utvecklades senare av Shimon Ewen, Oded Goldreich och Abraham Lempel med målet att skapa ett protokoll för konfidentiella datorprotokoll.. Detta protokoll generaliserades senare till "Glömsk överföring 1 av n", där användaren fick exakt 1 information och servern inte visste vilken; dessutom visste användaren ingenting om de återstående delarna som inte togs emot.

Under det fortsatta arbetet blev glömska protokoll ett av de grundläggande och viktigaste problemen inom kryptografi. De anses vara den viktigaste frågan inom krypteringsområdet på grund av vikten av applikationer som byggs ovanpå dem. I synnerhet har glömska protokoll gjort protokoll för konfidentiell beräkning möjliga . fyra

Rabins omedvetna överföringsalgoritm

I det omedvetna Rabin-dataöverföringsprotokollet genererar avsändaren RSA publika moduler N = pq där p och q är stora primtal och exponenten e är coprime till ( p -1)( q -1). Avsändaren krypterar meddelandet m som m e mod N .

Avsändaren skickar N , e och m e mod N till mottagaren.
Mottagaren väljer en slumpmässig x mod N och skickar x 2 mod N till avsändaren.
Avsändaren hittar kvadratroten y av x 2 mod N och skickar y till mottagaren.

Om avsändaren hittar ett y som varken är x eller -x mod N , kan mottagaren faktorisera N och därigenom avkoda m e för att få m . (mer detaljerat Rabins kryptosystem )

Men om y är lika med x eller - x mod N kommer mottagaren inte att ha någon information om m . Eftersom varje kvadratisk rest mod N har 4 kvadratrötter är chansen att mottagaren kommer att dechiffrera m 1/2.

Glömskt protokoll 1 till 2

I denna version av protokollet skickar avsändaren två meddelanden m 0 och m 1 , och mottagaren har bit b , och vill gärna ta emot m b , utan att avsändaren vet b , medan avsändaren vill vara säker på att mottagaren tagit emot bara ett av två meddelanden. 5

Avsändaren har två meddelanden, , och vill skicka ett enda meddelande till mottagaren, men vill inte veta vilket mottagaren kommer att ta emot. ${\displaystyle m_{0},m_{1))$
Avsändaren genererar ett RSA-nyckelpar som innehåller moduler , en offentlig exponent och en dold . $N$ $e$ $d$
Avsändaren genererar också två slumpmässiga värden och skickar dem till mottagaren tillsammans med de offentliga modulerna och exponenten $x_{0},x_{1}$
Mottagaren väljer (1, 0) och väljer antingen den första eller den andra . $b$ ${\displaystyle x_{b))$
Mottagaren genererar ett slumpmässigt värde och krypterar beräkningen som returneras till avsändaren. $k$ ${\displaystyle x_{b))$ $v=(x_{b}+k^{e})\mod N$
Avsändaren vet inte vilken och mottagaren har valt och försöker dekryptera båda slumpmässiga meddelanden och får två möjliga värden : och . En av dem kommer att matcha , vara korrekt avkodad, medan den andra kommer att vara ett slumpmässigt värde som inte avslöjar någon information om . $x_{0}$ $x_{1}$ $k$ $k_{0}=(v-x_{0})^{d}\mod N$ $k_{1}=(v-x_{1})^{d}\mod N$ $k$ $k$
Avsändaren krypterar båda hemliga meddelanden med alla möjliga nyckel , och skickar båda till mottagaren. ${\displaystyle m'_{0}=m_{0}+k_{0))$ ${\displaystyle m'_{1}=m_{1}+k_{1))$
Mottagaren vet vilket av de två meddelandena som kan dekrypteras med , och han får bara dekryptera ett meddelande. $k$ $m_{b}=m'_{b}-k$

Glömskt 1-ut- n - protokoll och glömskt k - ut - n -protokoll

Det glömska 1-ut- n - protokollet och det glömska k - ut - n -protokollet kan definieras som en generalisering av det glömska 1-ut-2-protokollet. Avsändaren har n meddelanden och mottagaren har index i ; mottagaren vill ta emot endast det i -te meddelandet från listan, utan att avsändaren känner till i , och mottagaren tar endast emot detta meddelande. 6

Denna typ av protokoll generaliserades senare till k - out - n , där mottagaren tar emot en uppsättning av k av n meddelandesamlingar. En uppsättning av k meddelanden kan tas emot samtidigt, eller så kan de begäras i ordning, med varje efterföljande begäran som bygger på den tidigare begäran.

Se även

Anteckningar

Länkar

↑ Michael O. Rabin. "Hur man utbyter hemligheter genom omedveten överföring." Teknisk rapport TR-81, Aiken Computation Laboratory, Harvard University, 1981.Skannad handskrift på eprint.iacr.org arkiv Arkiverad23 november 2021 påWayback Machine. Maskinskriven version tillgänglig påDoustis hemsida Arkiverad2 juli 2013 påWayback Machine(Alternativ länk på Google Docs).
↑ Joe Kilian. "Founding Cryptography on Oblivious Transfer", Proceedings, 20th Annual ACM Symposium on the Theory of Computation (STOC), 1988.Uppsats på ACM-portalen (prenumeration krävs)
↑ Gilles Brassard,Claude CrepeauochJean-Marc Robert. "Allt-eller-inget avslöjande av hemligheter." In Advances in Cryptology: CRYPTO '86, volym 263 av LNCS, sidorna 234-238. Springer, 1986.
↑ Moni NaorochBenny Pinkas. "Omedveten överföring med adaptiva frågor." In Advances in Cryptology: CRYPTO '99, volym 1666 av LNCS, sidorna 573-590. Springer, 1999.