Co přesně je “ poškozený obvod ”?

A obvod je jen způsob, jak reprezentovat výpočet. Na obvodu není nic konkrétně kryptografického. Znamená to pouze přímočarý výpočet (žádné konstrukce smyček nebo řízení toku) sestávající pouze z operací na bitech , jako AND, OR, NOT.

A poškozený obvod je způsob, jak „zašifrovat výpočet“, který odhalí pouze výstup výpočtu, ale neodhalí nic o vstupech ani o žádných mezilehlých hodnotách . Používáme termín „obvod“, protože zkomolené obvody fungují tak, že vezmeme výpočet, na kterém vám záleží, vyjádřený jako obvod a poté provedete nějaké kryptografické údaje pro každou operaci (AND, OR, NOT) v obvodu .

Chceme-li být trochu přesnější, „garblingové schéma“ se skládá z:

• (Garble) Způsob převodu (plain) obvod $ C $ na zkomolený okruh $ \ widehat C $.

• (Encode) Způsob převodu libovolného (prostého) vstupu $ x $ pro obvod do zkomoleného vstupu $ \ widehat x $. Potřebujete tajnou náhodnost, která byla použita ke garble obvodu k zakódování $ x $ do $ \ widehat x $.

• (Vyhodnotit) Způsob, jak vzít zkomolený obvod $ \ widehat C $ a zkomolený vstup $ \ widehat x $ a výpočet výstupu obvodu $ C (x) $. Může to udělat kdokoli, nemusíte znát $ x $ ani tajnou náhodnost uvnitř $ \ widehat C $, abyste mohli vyhodnotit a naučit se $ C (x) $.

Tady trochu zjednodušuji. Ale hlavní myšlenkou bezpečnosti je, že $ \ widehat C $ a $ \ widehat x $ společně nepropouští více informací než $ C (x) $. Zejména neodhalují nic o $ x $, přesto umožňují provést výpočet $ C (x) $ (zapomněl). To mám na mysli „šifrováním výpočtu“.

Hlavní aplikací pro zkomolené obvody je zabezpečený výpočet dvou stran. Představte si, že Alice má soukromý vstup $ x $ a Bob má soukromý vstup $ y $. Shodují se na nějaké funkci $ f $ a souhlasí s tím, že se oba chtějí naučit $ f (x, y) $, ale nechtějí, aby se jejich oponent naučil něco více než $ f (x, y) ) $. K dosažení tohoto cíle mohou provést následující (jedná se o klasický protokol Yao):

1. Strany se dohodly na způsobu, jak vyjádřit $ f $ jako (prostý ) obvod. Alice omotává okruh $ f \ mapsto \ widehat f $. Pošle Bobovi $ \ widehat f $ a také její vlastní „zkomolený vstup“ $ \ widehat x $.

2. Alice ví, jak zakódovat jakýkoli vstup pro $ f $ do „zkomolený“ vstup, ale pouze Bob zná jeho soukromý vstup $ y $. Takže strany zařídily, aby Bob vyzvedl zkomolenou verzi $ \ widehat y $, aniž by se Alice dozvěděla, co $ y $ bylo. Toho lze dosáhnout primitivem zvaným lhostejný přenos.

3. Nyní má Bob zkomolený obvod $ \ widehat f $ a zkomolený vstup $ \ widehat x, \ widehat y $ pro ten okruh. Poté může spustit proceduru vyhodnocení a naučit se $ f (x, y) $. Může Alici odhalit $ f (x, y) $.

Můžeme tvrdit, že protokol v následujících případech neodhalí více než $ f (x, y) $ způsob:

• Alice v tomto protokolu nevidí nic jiného než konečnou odpověď $ f (x, y) $ (bezpečnost zapomenutého přenosu zajišťuje, že se v kroku nic nenaučí 2).

• Přestože Bob vidí $ \ widehat f $, $ \ widehat x $ a $ \ widehat y $, zabezpečení zkomolených obvodů zajišťuje, že tyto hodnoty nebudou “ t odhalit cokoli jiného než $ f (x, y) $.

Tento přístup funguje, když je Alice & Bob poloviční (tj. dodržují protokol podle pokynů). Ale když je Alice škodlivá, může vydělat nějakou jinou funkci $ f „$ místo $ f $, na kterých se dohodli.Abychom tomu zabránili, je třeba přidat další věci, abychom tomu zabránili, když chceme zabezpečení proti škodlivým útočníkům.

Referenční materiál:

• Konstrukce Yao a její důkaz bezpečnosti (video), Yehuda Lindell
• Protokol protokolu Yao pro zabezpečený výpočet dvou stran Yehuda Lindell & Benny Pinkas
• Základy Garbled Circuits , Mihir Bellare, Viet Tung Hoang, Phillip Rogaway
• Stručná historie praktické optimalizace zkomolených obvodů , moje video . Prvních několik snímků pokrývá „klasickou“ konstrukci poškozených obvodů.

Komentáře

• Jak Bob garbleuje y aniž by věděla o tajné náhodnosti, kterou si Alice vybrala, když přišla se schématem zkomolení?
• Zkomolené kódování funguje bit-by-bit. 36b523ac4 „>