Hvad er et “ forvansklet kredsløb ”?

Et kredsløb er bare en måde at repræsentere en beregning på. Der er ikke noget specifikt kryptografisk ved et kredsløb. Det betyder bare en lineær beregning (ingen looping- eller flowkontrolkonstruktioner), der kun består af operationer på bits , som AND, OR, NOT.

A forvansket kredsløb er en måde at “kryptere en beregning”, der kun afslører output fra beregningen, men afslører intet om input eller eventuelle mellemværdier . Vi bruger udtrykket “kredsløb”, fordi forvanskede kredsløb fungerer ved at tage den beregning, du holder af, udtrykt som et kredsløb og derefter lave nogle kryptografiske ting for hver operation (AND, OR, NOT) i kredsløbet .

Hvis vi vil være lidt mere præcise, består en “garblingskema” af:

• (Garble) En måde at konvertere en (almindelig) kredsløb $ C $ til et forvrænget kredsløb $ \ widehat C $.

• (Encode) En måde at konvertere enhver (almindelig) input $ x $ for kredsløbet til et forvansket input $ \ widehat x $. Du har brug for den hemmelige tilfældighed, der blev brugt til at forvride kredsløbet for at kode $ x $ til $ \ widehat x $.

• (Evaluer) En måde at tage en forvansket på kredsløb $ \ widehat C $ og forvansket input $ \ widehat x $ og beregne kredsløbsoutputtet $ C (x) $. Enhver kan gøre dette, du behøver ikke at vide $ x $ eller den hemmelige tilfældighed inde i $ \ widehat C $ for at evaluere og lære $ C (x) $.

Jeg forenkler lidt her. Men hovedideen med sikkerhed er, at $ \ widehat C $ og $ \ widehat x $ sammen ikke lækker mere information end $ C (x) $. Især afslører de intet om $ x $, men alligevel tillader de, at beregningen $ C (x) $ udføres (uden glemsel). Dette er hvad jeg mener med “kryptering af en beregning”.

Hovedapplikationen til forvanskede kredsløb er sikker topartsberegning. Forestil dig, at Alice har private input $ x $, og Bob har private input $ y $. De er enige om en eller anden funktion $ f $ og er enige om, at de begge vil lære $ f (x, y) $, men ikke ønsker, at deres modstander skal lære noget mere end $ f (x, y ) $. For at opnå dette kan de gøre følgende (dette er Yaos klassiske protokol):

1. Parterne er enige om en måde at udtrykke $ f $ som en (almindelig ) kredsløb. Alice vinder kredsløbet $ f \ mapsto \ widehat f $. Hun sender $ \ widehat f $ til Bob såvel som sin egen “forvanskede input” $ \ widehat x $.

2. Alice ved, hvordan man koder ethvert input for $ f $ til et “forvrænget” input, men kun Bob kender hans private input $ y $. Så parterne sørger for, at Bob henter en forvrænget version $ \ widehat y $ uden Alice at lære, hvad $ y $ var. Dette kan gøres med en primitiv kaldet glemsom overførsel.

3. Nu har Bob det forvanskede kredsløb $ \ widehat f $ og en forvansket input $ \ widehat x, \ widehat y $ til det kredsløb. Han kan derefter køre evalueringsproceduren og lære $ f (x, y) $. Han kan afsløre $ f (x, y) $ til Alice.

Vi kan argumentere for, at protokollen ikke afslører mere end $ f (x, y) $ i det følgende måde:

• Alice ser ikke andet end det endelige svar $ f (x, y) $ i denne protokol (sikkerheden ved glemsom overførsel sikrer, at hun ikke lærer noget i trin 2).

• Selvom Bob ser $ \ widehat f $, $ \ widehat x $ og $ \ widehat y $, sikrer sikkerheden ved forvanskede kredsløb, at disse værdier ikke ” t afslører noget ud over $ f (x, y) $.

Denne tilgang fungerer, når Alice & Bob er semi-ærlige (dvs. de følger protokollen som beskrevet). Men når Alice er ondsindet, kan hun goble en anden funktion $ f “$ i stedet for $ f $, som de blev enige om.Så andre ting skal tilføjes til protokollen for at forhindre, at dette sker, når vi ønsker sikkerhed mod ondsindede modstandere.

Reference materiale:

• Yao-konstruktionen og dens bevis på sikkerhed (video), Yehuda Lindell
• Et bevis på Yaos protokol til sikker topartsberegning , Yehuda Lindell & Benny Pinkas
• Fundamenter for forvanskede kredsløb , Mihir Bellare, Viet Tung Hoang, Phillip Rogaway
• En kort historie om praktiske garbled kredsløbsoptimeringer , en video af mig De første flere dias dækker den “klassiske” konstruktion af forvanskede kredsløb.

Kommentarer

• Hvordan gobler Bob y uden at kende den hemmelige tilfældighed, som Alice valgte, da hun kom op med forvanskningsskemaet?
• Den forvrængede kodning fungerer lidt efter lidt. Tag Bob s første bit. Alice kan tænke for sig selv: " hvis Bob har input bit 0, skal hans forvanskede kodning være $ G_0 $. Hvis han har input bit 1, skal hans forvrængede kodning være $ G_1 $. " Glemløs overførsel er en primitiv, hvor Alice giver to strenge $ G_0, G_1 $ som input. Bob giver lidt $ b $ som input og lærer $ G_b $ (men ikke den anden $ G_ {1-b} $). Alice lærer ikke ' $ b $. Parterne kan udføre en glemsom overførsel for hver bit af Bob ' s input. Hvad angår hvordan glemsom overførsel virkelig fungerer, er det et andet spørgsmål;)
• Ved siden af Yao ' s forvanskede kredsløb kan ' t genbruges. Kan du venligst løse min misforståelse om, at " Er det tilladt at tildele forskellige nøgler hver gang, når forvansket kredsløb udføres, eller nøgler er faste til input bit 0 og 1 "