Există o mulțime de întrebări aici despre detaliile și modalitățile de utilizare a „circuitelor zdrobite”, dar nu am văzut nimic care să definească ce circuite zdrențuite sunt .

Ce anume este un circuit defect? Pentru ce sunt destinate să fie utilizate? Care sunt limitările lor?

Eticheta pentru circuitele zdrobite spune doar că sunt folosite în calculul multipartit securizat. Cu toate acestea, acest răspuns afirmă că „sunt adecvate numai pentru calculul cu două părți?

Această întrebare caută definirea unui „circuit”. Care este diferența dintre un circuit și un circuit defect?

Comentarii

  • Veți găsi o bună expunere a lui Yao ' protocolul de circuite defectuoase pentru calcule securizate de două părți în această carte . ' este scump, dar biblioteca dvs. universitară locală ar putea să o aibă.
  • Vă sugerez acest videoclip , și diapozitive

Răspuns

Un circuit este doar o modalitate de a reprezenta un calcul. Nu există nimic specific criptografic despre un circuit. Înseamnă doar un calcul în linie dreaptă (fără construcții de buclă sau de control al fluxului) care constă doar din operații pe biți , cum ar fi AND, OR, NOT.

A circuitul zdrențuit este o modalitate de a „cripta un calcul” care dezvăluie doar ieșirea calculului, dar nu dezvăluie nimic despre intrări sau orice valori intermediare . Folosim termenul „circuit”, deoarece circuitele zdrobite funcționează luând calculul care vă interesează, exprimat ca un circuit și apoi făcând câteva lucruri criptografice pentru fiecare operație (ȘI, SAU, NU) în circuit .

Dacă vrem să fim puțin mai preciși, o „schemă de gârlare” constă din:

  • (Garble) O modalitate de a converti un (simplu) circuit $ C $ într-un circuit zdrobit $ \ widehat C $.

  • (Codificare) O modalitate de a converti orice intrare (simplă) $ x $ pentru circuit într-o intrare zdrobită $ \ widehat x $. Aveți nevoie de caracterul aleatoriu secret care a fost folosit pentru a distruge circuitul pentru a codifica $ x $ în $ \ widehat x $.

  • (Evaluare) O modalitate de a lua o circuit $ \ widehat C $ și garbled input $ \ widehat x $ și calculați ieșirea circuitului $ C (x) $. Oricine poate face acest lucru, nu trebuie să știți $ x $ sau caracterul secret aleatoriu din interiorul $ \ widehat C $ pentru a evalua și învăța $ C (x) $.

Simplific puțin aici. Dar ideea principală a securității este că $ \ widehat C $ și $ \ widehat x $ împreună nu scurg mai multe informații decât $ C (x) $. În special, nu dezvăluie nimic despre $ x $, totuși permit calculul $ C (x) $ să se facă (fără să știe). Aceasta este ceea ce vreau să spun prin „criptarea unui calcul”.

Aplicația principală pentru circuite zdrobite este calculul securizat cu două părți. Imaginați-vă că Alice are intrare privată $ x $ și Bob are intrare privată $ y $. Sunt de acord cu unele funcții $ f $ și sunt de acord că ambii vor să învețe $ f (x, y) $, dar nu doresc ca adversarul lor să învețe ceva mai mult decât $ f (x, y ) $. Pentru a realiza acest lucru, pot face următoarele (acesta este protocolul clasic al lui Yao):

  1. Părțile convin asupra unui mod de a exprima $ f $ ca (simplu) ) circuit. Alice distruge circuitul $ f \ mapsto \ widehat f $. Ea îi trimite lui $ \ widehat f $ lui Bob, precum și propriul ei „intrare greșită” $ \ widehat x $.

  2. Alice știe cum să codeze orice intrare pentru $ f $ în o intrare „zdrențuită”, dar numai Bob știe intrarea sa privată $ y $. Deci, părțile aranjează ca Bob să ridice o versiune eronată $ \ widehat y $ fără ca Alice să afle ce a fost $ y $. Acest lucru se poate face cu un primitiv numit transfer ignorant.

  3. Acum Bob are circuitul zgârcit $ \ widehat f $ și o intrare zgârcită $ \ widehat x, \ widehat y $ pentru acel circuit. El poate apoi să execute procedura de evaluare și să învețe $ f (x, y) $. El poate dezvălui $ f (x, y) $ lui Alice.

Putem argumenta că protocolul nu dezvăluie mai mult de $ f (x, y) $ în următoarele mod:

  • Alice nu vede nimic altceva decât răspunsul final $ f (x, y) $ în acest protocol (securitatea transferului neștiut asigură că nu învață nimic în pas 2).

  • Chiar dacă Bob vede $ \ widehat f $, $ \ widehat x $ și $ \ widehat y $, securitatea circuitelor zgârcite asigură că aceste valori nu sunt ” Nu dezvălui nimic dincolo de $ f (x, y) $.

Această abordare funcționează atunci când Alice & Bob este semi-onest (adică respectă protocolul conform instrucțiunilor). Dar când Alice este rău intenționată, ea poate distruge o altă funcție $ f „$ în loc de $ f $ pe care au convenit-o.Deci, trebuie adăugate alte lucruri la protocol pentru a preveni acest lucru, atunci când dorim securitate împotriva adversarilor rău intenționați.

Material de referință:

Comentarii

  • Cum face Bob să râdă y fără să știți întâmplarea secretă pe care Alice a ales-o când a venit cu schema de gâlbâială?
  • Codificarea gâlgată funcționează bit-by-bit. Luați-l pe Bob primul bit. Alice se poate gândi în sinea ei: " dacă Bob are bitul de intrare 0, atunci codificarea lui zgârcită ar trebui să fie $ G_0 $. Dacă are bitul de intrare 1, atunci codificarea sa greșită ar trebui să fie de $ G_1 $. " Transfer ignorat este o primitivă în care Alice furnizează două șiruri $ G_0, G_1 $ ca intrare. Bob oferă un pic $ b $ ca intrare și învață $ G_b $ (dar nu și celălalt $ G_ {1-b} $). Alice nu ' nu învață $ b $. Părțile pot efectua un transfer indiferent pentru fiecare bit de intrare Bob '. În ceea ce privește cum funcționează cu adevărat transferul ignorant, aceasta este o altă întrebare;)
  • Pe lângă Yao ' circuitul zdrențuit poate nu poate fi reutilizat. Puteți, vă rog, să vă rezolvați încrederea că " Este permisă atribuirea unor chei diferite de fiecare dată când se execută un circuit defect sau cheile sunt fixate pentru bitul de intrare 0 și 1 "

Lasă un răspuns

Adresa ta de email nu va fi publicată. Câmpurile obligatorii sunt marcate cu *