Vad är exakt en “ förvrängd krets ”?

En krets är bara ett sätt att representera en beräkning. Det finns inget specifikt kryptografiskt om en krets. Det betyder bara en rätlinjig beräkning (inga looping- eller flödeskontrollkonstruktioner) som består av bara operationer på bitar , som AND, OR, NOT.

A förvrängd krets är ett sätt att ”kryptera en beräkning” som bara avslöjar utdata från beräkningen, men avslöjar ingenting om ingångarna eller några mellanliggande värden . Vi använder termen ”krets” eftersom förvrängda kretsar fungerar genom att ta den beräkning du bryr dig om, uttryckt som en krets och sedan göra några kryptografiska saker för varje operation (AND, OR, NOT) i kretsen .

Om vi vill vara lite mer exakta, består ett ”garblingschema” av:

• (Garble) Ett sätt att konvertera en (vanlig) kretsar $ C $ till en förvrängd krets $ \ widehat C $.

• (Encode) Ett sätt att konvertera valfri (vanlig) ingång $ x $ för kretsen till en förvrängd ingång $ \ widehat x $. Du behöver den hemliga slumpmässigheten som användes för att klumpa ihop kretsen för att koda $ x $ till $ \ widehat x $.

• (Utvärdera) Ett sätt att ta en förvrängd krets $ \ widehat C $ och garbled matar in $ \ widehat x $ och beräknar kretsutgången $ C (x) $. Vem som helst kan göra det, du behöver inte veta $ x $ eller den hemliga slumpmässigheten i $ \ widehat C $ för att utvärdera och lära dig $ C (x) $.

Jag förenklar lite här. Men huvudidén med säkerhet är att $ \ widehat C $ och $ \ widehat x $ tillsammans inte läcker ut mer information än $ C (x) $. I synnerhet avslöjar de ingenting om $ x $, men ändå tillåter beräkningen $ C (x) $ att göras (omedvetet). Detta är vad jag menar med ”kryptering av en beräkning”.

Huvudapplikationen för förvrängda kretsar är säker tvåpartsberäkning. Tänk dig att Alice har privat input $ x $ och Bob har privat input $ y $. De är överens om någon funktion $ f $ och håller med om att de båda vill lära sig $ f (x, y) $, men vill inte att deras motståndare ska lära sig något mer än $ f (x, y ) $. För att uppnå detta kan de göra följande (detta är Yaos klassiska protokoll):

1. Parterna är överens om ett sätt att uttrycka $ f $ som en (vanlig ) krets. Alice gnistrar kretsen $ f \ mapsto \ widehat f $. Hon skickar $ \ widehat f $ till Bob såväl som sin egen ”förvrängda inmatning” $ \ widehat x $.

2. Alice vet hur man kodar alla ingångar för $ f $ till en ”förvrängd” ingång, men bara Bob känner till sin privata inmatning $ y $. Så parterna ordnar för Bob att plocka upp en förvrängd version $ \ widehat y $ utan att Alice lär sig vad $ y $ var. Detta kan göras med en primitiv som kallas oblivious transfer.

3. Nu har Bob den förvrängda kretsen $ \ widehat f $ och en förvrängd ingång $ \ widehat x, \ widehat y $ för den kretsen. Han kan sedan köra utvärderingsproceduren och lära sig $ f (x, y) $. Han kan avslöja $ f (x, y) $ för Alice.

Vi kan hävda att protokollet avslöjar högst $ f (x, y) $ i följande sätt:

• Alice ser inget annat än det slutliga svaret $ f (x, y) $ i detta protokoll (säkerheten vid glömsk överföring säkerställer att hon inte lär sig något i steg 2).

• Även om Bob ser $ \ widehat f $, $ \ widehat x $ och $ \ widehat y $, säkerställer säkerheten hos förvrängda kretsar att dessa värden inte ” t avslöjar något utöver $ f (x, y) $.

Detta tillvägagångssätt fungerar när Alice & Bob är semi-ärlig (dvs. de följer protokollet enligt instruktionerna). Men när Alice är illvillig kan hon gnugga någon annan funktion $ f ”$ istället för $ f $ som de kom överens om.Så andra saker måste läggas till i protokollet för att förhindra att detta händer när vi vill ha säkerhet mot skadliga motståndare.

Referensmaterial:

• Yao Construction och dess bevis på säkerhet (video), Yehuda Lindell
• Ett bevis på Yaos protokoll för säker tvåpartsberäkning , Yehuda Lindell & Benny Pinkas
• Foundations of Garbled Circuits , Mihir Bellare, Viet Tung Hoang, Phillip Rogaway
• En kort historia över praktiska optimeringar av förgrenade kretsar , en video av mig De första flera bilderna täcker den ”klassiska” konstruktionen av förvrängda kretsar.

Kommentarer

• Hur gnistrar Bob y utan att känna till den hemliga slumpmässigheten som Alice valde när hon kom fram till det gnistrande systemet?
• Den förvrängda kodningen fungerar bit för bit. Ta Bob s första bit. Alice kan tänka för sig själv: " om Bob har inmatad bit 0, bör hans förvrängda kodning vara $ G_0 $. Om han har inmatningsbit 1 bör hans förvrängda kodning vara $ G_1 $. " Oblivious transfer är en primitiv där Alice ger två strängar $ G_0, G_1 $ som ingång. Bob ger lite $ b $ som input och lär sig $ G_b $ (men inte den andra $ G_ {1-b} $). Alice lär sig inte ' $ b $. Parterna kan utföra en omedveten överföring för varje bit av Bob ' s ingång. När det gäller hur glömsk överföring verkligen fungerar, det är en annan fråga;)
• Bredvid Yao ' s förvrängda krets kan ' ska inte återanvändas. Kan du snälla lösa min förvirring att " Är det tillåtet att tilldela olika nycklar varje gång när en förvrängd krets körs eller tangenterna är fixerade för ingångsbit 0 och 1 "