Hva er egentlig en “ forvrengt krets ”?

En krets er bare en måte å representere en beregning på. Det er ikke noe spesielt kryptografisk om en krets. Det betyr bare en lineær beregning (ingen looping- eller flow-control-konstruksjoner) som består av bare operasjoner på bits , som AND, OR, NOT.

A forvrenget krets er en måte å «kryptere en beregning» som bare avslører utdataene fra beregningen, men avslører ingenting om inngangene eller noen mellomverdier . Vi bruker begrepet «krets» fordi forvanskede kretser fungerer ved å ta beregningen du bryr deg om, uttrykt som en krets , og deretter gjøre noen kryptografiske ting for hver operasjon (AND, OR, NOT) i kretsen .

Hvis vi ønsker å være litt mer presise, består et «garblingskjema» av:

• (Garble) En måte å konvertere en (vanlig) krets $ C $ til en forvrengt krets $ \ widehat C $.

• (Encode) En måte å konvertere en hvilken som helst (vanlig) inngang $ x $ for kretsen til en forvrengt inngang $ \ widehat x $. Du trenger den hemmelige tilfeldigheten som ble brukt til å tømme kretsen for å kode $ x $ til $ \ widehat x $.

• (Evaluer) En måte å ta en forvirret krets $ \ widehat C $ og garbled input $ \ widehat x $ og beregne kretsutgangen $ C (x) $. Alle kan gjøre dette, du trenger ikke å vite $ x $ eller den hemmelige tilfeldigheten i $ \ widehat C $ for å evaluere og lære $ C (x) $.

Jeg forenkler litt her. Men hovedideen for sikkerhet er at $ \ widehat C $ og $ \ widehat x $ sammen ikke lekker mer informasjon enn $ C (x) $. Spesielt avslører de ingenting om $ x $, men likevel tillater beregningen $ C (x) $ å bli gjort (uvitende). Dette er det jeg mener med «kryptering av en beregning».

Hovedapplikasjonen for forvanskede kretsløp er sikker beregning av to parter. Tenk deg at Alice har private input $ x $ og Bob har private input $ y $. De er enige om en eller annen funksjon $ f $ og er enige om at de begge vil lære $ f (x, y) $, men vil ikke at motstanderen skal lære noe mer enn $ f (x, y ) $. For å oppnå dette kan de gjøre følgende (dette er Yaos klassiske protokoll):

1. Partene er enige om en måte å uttrykke $ f $ som en (vanlig ) krets. Alice gnister kretsen $ f \ mapsto \ widehat f $. Hun sender $ \ widehat f $ til Bob, så vel som sin egen «forvrengte inngang» $ \ widehat x $.

2. Alice vet hvordan hun skal kode alle innganger for $ f $ til en «forvrengt» innspill, men bare Bob kjenner sin private innspill $ y $. Så festene arrangerer at Bob henter en forvrengt versjon $ \ widehat y $ uten at Alice lærer hva $ y $ var. Dette kan gjøres med en primitiv kalt oblivious transfer.

3. Nå har Bob den forvanskede kretsen $ \ widehat f $, og en forvrenget inngang $ \ widehat x, \ widehat y $ for den kretsen. Deretter kan han kjøre evalueringsprosedyren og lære $ f (x, y) $. Han kan avsløre $ f (x, y) $ til Alice.

Vi kan argumentere for at protokollen ikke avslører mer enn $ f (x, y) $ i det følgende måte:

• Alice ser ikke noe annet enn det endelige svaret $ f (x, y) $ i denne protokollen (sikkerheten ved glemsom overføring sørger for at hun ikke lærer noe i trinn 2).

• Selv om Bob ser $ \ widehat f $, $ \ widehat x $ og $ \ widehat y $, sikrer sikkerheten til forvanskede kretser at disse verdiene ikke » t avslører noe utover $ f (x, y) $.

Denne tilnærmingen fungerer når Alice & Bob er semi-ærlig (dvs. de følger protokollen som beskrevet). Men når Alice er ondsinnet, kan hun glise en annen funksjon $ f «$ i stedet for $ f $ som de ble enige om.Så andre ting må legges til i protokollen for å forhindre at dette skjer, når vi ønsker sikkerhet mot ondsinnede motstandere.

Referansemateriale:

• Yao Construction og dens bevis på sikkerhet (video), Yehuda Lindell
• Et bevis på Yaos protokoll for 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 Optimization , en video av meg De første lysbildene dekker den «klassiske» konstruksjonen av forvrengte kretsløp.

Kommentarer

• Hvordan gobler Bob y uten å vite den hemmelige tilfeldigheten som Alice valgte da hun kom opp med ordren?
• Den forvrengede kodingen fungerer bit for bit. Ta Bob s første bit. Alice kan tenke for seg selv: " hvis Bob har inngangsbit 0, så skal den forvanskede kodingen være $ G_0 $. Hvis han har inngangsbit 1, bør den forvrengte kodingen være $ G_1 $. " Oblivious transfer er en primitiv der Alice gir to strenger $ G_0, G_1 $ som innspill. Bob gir litt $ b $ som input og lærer $ G_b $ (men ikke den andre $ G_ {1-b} $). Alice lærer ikke ' $ b $. Partene kan utføre en glemsk overføring for hver bit av Bob ' s innspill. Når det gjelder hvordan glemsom overføring egentlig fungerer, er det et annet spørsmål;)
• Ved siden av Yao ' s forvrengte krets kan ' t gjenbrukes. Kan du løse min misforståelse om at " Er det tillatt å tildele forskjellige nøkler hver gang når en forvrengt krets utføres eller nøklene er faste for inngangsbit 0 og 1 "