Che cosè esattamente un “ circuito alterato ”?

Un circuito è solo un modo per rappresentare un calcolo. Non cè niente di specificamente crittografico in un circuito. Significa solo un calcolo lineare (nessun costrutto di loop o controllo del flusso) costituito da sole operazioni su bit , come AND, OR, NOT.

A circuito alterato è un modo per “crittografare un calcolo” che rivela solo loutput del calcolo, ma non rivela nulla sugli input o sui valori intermedi . Usiamo il termine “circuito” perché i circuiti confusi funzionano prendendo il calcolo che ti interessa, espresso come un circuito , e poi facendo alcune cose crittografiche per ogni operazione (AND, OR, NOT) nel circuito .

Se vogliamo essere un po più precisi, uno “schema di garbling” consiste di:

• (Garble) Un modo per convertire un (semplice) circuito $ C $ in un circuito $ \ widehat C $ confuso .

• (Codifica) Un modo per convertire qualsiasi input (semplice) $ x $ per il circuito in un input confuso $ \ widehat x $. Hai bisogno della casualità segreta che è stata utilizzata per confondere il circuito per codificare $ x $ in $ \ widehat x $.

• (Valuta) Un modo per prendere un confuso circuit $ \ widehat C $ e confuso input $ \ widehat x $ e calcolano loutput del circuito $ C (x) $. Chiunque può farlo, non devi conoscere $ x $ o la casualità segreta allinterno di $ \ widehat C $ per valutare e imparare $ C (x) $.

Sto semplificando un po qui. Ma lidea principale della sicurezza è che $ \ widehat C $ e $ \ widehat x $ insieme non perdono più informazioni di $ C (x) $. In particolare, non rivelano nulla su $ x $, tuttavia consentono di eseguire il calcolo $ C (x) $ (inconsapevolmente). Questo è ciò che intendo per “crittografare un calcolo”.

Lapplicazione principale per circuiti confusi è il calcolo sicuro a due parti. Immagina che Alice abbia un input privato $ x $ e Bob abbia un input privato $ y $. Sono daccordo su una qualche funzione $ f $ e concordano sul fatto che entrambi vogliono imparare $ f (x, y) $, ma non vogliono che il loro avversario impari qualcosa più di $ f (x, y ) $. Per ottenere ciò, possono fare quanto segue (questo è il protocollo classico di Yao):

1. Le parti concordano su un modo per esprimere $ f $ come (semplice ) circuito. Alice altera il circuito $ f \ mapsto \ widehat f $. Invia $ \ widehat f $ a Bob così come il suo “input confuso” $ \ widehat x $.

2. Alice sa come codificare qualsiasi input per $ f $ in un input “confuso”, ma solo Bob conosce il suo input privato $ y $. Così le parti fanno in modo che Bob raccolga una versione confusa $ \ widehat y $ senza che Alice impari cosa fosse $ y $. Questo può essere fatto con un primitivo chiamato trasferimento ignaro.

3. Ora Bob ha il circuito confuso $ \ widehat f $ e un input confuso $ \ widehat x, \ widehat y $ per quel circuito. Può quindi eseguire la procedura di valutazione e apprendere $ f (x, y) $. Può rivelare $ f (x, y) $ ad Alice.

Possiamo sostenere che il protocollo non rivela più di $ f (x, y) $ nel seguito modo:

• Alice non vede nientaltro che la risposta finale $ f (x, y) $ in questo protocollo (la sicurezza del trasferimento ignaro assicura che non impari nulla al passo 2).

• Anche se Bob vede $ \ widehat f $, $ \ widehat x $ e $ \ widehat y $, la sicurezza dei circuiti confusi garantisce che questi valori non ” t rivelare qualcosa oltre $ f (x, y) $.

Questo approccio funziona quando Alice & Bob è semi-onesto (cioè, seguono il protocollo come indicato). Ma quando Alice è maliziosa può confondere qualche altra funzione $ f “$ invece della $ f $ concordata.Quindi è necessario aggiungere altre cose al protocollo per evitare che ciò accada, quando vogliamo sicurezza contro avversari dannosi.

Materiale di riferimento:

• The Yao Construction and its Proof Of Security (video), Yehuda Lindell
• A Proof of Yao” s Protocol per Secure Two-Party Computation , Yehuda Lindell & Benny Pinkas
• Foundations of Garbled Circuits , Mihir Bellare, Viet Tung Hoang, Phillip Rogaway
• A Brief History of Practical Garbled Circuit Optimizations , a my video . Le prime numerose diapositive trattano la costruzione “classica” di circuiti confusi.

Commenti

• Come fa Bob a garbare y senza conoscere la casualità segreta che Alice ha scelto quando ha inventato lo schema incomprensibile?
• La codifica confusa funziona bit per bit. Prendi Bob s primo bit. Alice può pensare a se stessa: " se Bob ha il bit di input 0, la sua codifica confusa dovrebbe essere $ G_0 $. Se ha il bit di input 1, la sua codifica confusa dovrebbe essere $ G_1 $. " Trasferimento ignaro è una primitiva in cui Alice fornisce due stringhe $ G_0, G_1 $ come input. Bob fornisce un po $ b $ come input e impara $ G_b $ (ma non laltro $ G_ {1-b} $). Alice non ' impara $ b $. Le parti possono eseguire un trasferimento ignaro per ogni bit di input di Bob '. Per quanto riguarda come il trasferimento ignaro funziona davvero, questa è unaltra domanda;)
• Accanto a Yao ' il circuito confuso può ' non può essere riutilizzato. Puoi risolvere la mia confusione secondo cui " consente di assegnare chiavi diverse ogni volta che viene eseguito un circuito confuso o le chiavi sono fisse per i bit di ingresso 0 e 1 "