Czym dokładnie jest “ zniekształcony obwód ”?

obwód to tylko sposób na przedstawienie obliczenia. W obwodzie nie ma nic specjalnie kryptograficznego. Oznacza to po prostu obliczenia w linii prostej (bez pętli lub konstrukcji sterujących przepływem) składające się tylko z operacji na bitach , takich jak AND, OR, NOT.

A zniekształcony obwód to sposób na „zaszyfrowanie obliczenia”, który ujawnia tylko wynik obliczeń, ale nie ujawnia niczego o wejściach ani wartościach pośrednich . Używamy terminu „obwód”, ponieważ zniekształcone obwody działają, przyjmując obliczenia, na których Ci zależy, wyrażone jako obwód , a następnie wykonując pewne czynności kryptograficzne dla każdej operacji (AND, OR, NOT) w obwodzie .

Jeśli chcemy być trochę bardziej precyzyjni, „schemat zniekształcania” składa się z:

• (Garble) Sposób konwersji (zwykłego) obwód $ C $ na zniekształcony obwód $ \ widehat C $.

• (Kodowanie) Sposób konwersji dowolnego (zwykłego) wejścia $ x $ dla obwodu w zniekształcone wejście $ \ widehat x $. Potrzebujesz tajnej losowości, która została użyta do zniekształcenia obwodu w celu zakodowania $ x $ w $ \ widehat x $.

• (Oceń) Sposób na zrobienie zniekształconego circuit $ \ widehat C $ i zniekształcony wprowadź $ \ widehat x $ i oblicz wyjście obwodu $ C (x) $. Każdy może to zrobić, nie musisz znać $ x $ ani sekretnej losowości wewnątrz $ \ widehat C $, aby ocenić i nauczyć się $ C (x) $.

Trochę upraszczam. Ale główną ideą bezpieczeństwa jest to, że $ \ widehat C $ i $ \ widehat x $ razem wyciekają nie więcej informacji niż $ C (x) $. W szczególności nie ujawniają niczego na temat $ x $, ale pozwalają na wykonanie obliczenia $ C (x) $ (nieświadomie). To właśnie mam na myśli przez „szyfrowanie obliczeń”.

Głównym zastosowaniem zniekształconych obwodów są bezpieczne dwu-stronne obliczenia. Wyobraź sobie, że Alicja ma prywatne wejście $ x $, a Bob ma prywatne wejście $ y $. Zgadzają się na jakąś funkcję $ f $ i zgadzają się, że obaj chcą się nauczyć $ f (x, y) $, ale nie chcą, aby ich przeciwnik nauczył się czegokolwiek więcej niż $ f (x, y ) $. Aby to osiągnąć, mogą wykonać następujące czynności (jest to klasyczny protokół Yao):

1. Strony uzgadniają sposób wyrażenia $ f $ jako (zwykły ) obwód. Alicja zniekształca obwód $ f \ mapsto \ widehat f $. Wysyła $ \ widehat f $ do Boba, jak również własne „zniekształcone dane wejściowe” $ \ widehat x $.

2. Alicja wie, jak zakodować dowolne wejście dla $ f $ w „zniekształcone” dane wejściowe, ale tylko Bob zna swój prywatny wpis $ y $. Tak więc strony ustalają, że Bob wybierze zniekształconą wersję $ \ widehat y $, a Alice nie dowiedziała się, czym jest $ y $. Można to zrobić za pomocą prymitywnego transferu zwanego nieświadomym.

3. Teraz Bob ma zniekształcony obwód $ \ widehat f $ i zniekształcone dane wejściowe $ \ widehat x, \ widehat y $ dla tego obwodu. Następnie może uruchomić procedurę oceny i nauczyć się $ f (x, y) $. Może ujawnić $ f (x, y) $ Alicji.

Możemy argumentować, że protokół ujawnia nie więcej niż $ f (x, y) $ w następującym sposób:

• Alicja nie widzi niczego poza ostateczną odpowiedzią $ f (x, y) $ w tym protokole (bezpieczeństwo nieświadomego transferu zapewnia, że nie uczy się niczego w kroku 2).

• Mimo że Bob widzi $ \ widehat f $, $ \ widehat x $ i $ \ widehat y $, bezpieczeństwo zniekształconych obwodów zapewnia, że te wartości nie ” t nie ujawniać niczego poza $ f (x, y) $.

To podejście działa, gdy Alicja & Bob jest pół-szczery (tj. przestrzegają protokołu zgodnie z instrukcją). Ale kiedy Alicja jest złośliwa, może przekłamać jakąś inną funkcję $ f „$ zamiast $ f $, na którą się zgodzili.Dlatego do protokołu należy dodać inne rzeczy, aby temu zapobiec, gdy chcemy ochrony przed złośliwymi adwersarzami.

Materiały referencyjne:

• Konstrukcja Yao i jej dowód bezpieczeństwa (wideo), Yehuda Lindell
• Dowód protokołu Yao do bezpiecznych obliczeń dwustronnych , Yehuda Lindell & Benny Pinkas
• Podstawy zniekształconych obwodów , Mihir Bellare, Viet Tung Hoang, Phillip Rogaway
• A Brief History of Practical Garbled Circuit Optimizations , mój film . Kilka pierwszych slajdów dotyczy „klasycznej” konstrukcji zniekształconych obwodów.

Komentarze

• Jak Bob garble y bez znajomości sekretnej przypadkowości, którą wybrała Alicja, kiedy wymyśliła schemat zniekształcania?
• Zniekształcone kodowanie działa bit po bicie. Weź Bob s pierwszy bit. Alicja może sobie pomyśleć: " jeśli Bob ma bit wejściowy 0, to jego zniekształcone kodowanie powinno wynosić $ G_0 $. Jeśli ma wejściowy bit 1, to jego zniekształcone kodowanie powinno wynosić $ G_1 $. " Nieświadomy transfer jest prymitywem, w którym Alicja dostarcza dwa ciągi $ G_0, G_1 $ jako dane wejściowe. Bob podaje trochę $ b $ jako dane wejściowe i uczy się $ G_b $ (ale nie drugiego $ G_ {1-b} $). Alicja nie ' nie uczy się $ b $. Strony mogą wykonać nieświadomy transfer dla każdego bitu danych wejściowych Boba '. Jeśli chodzi o jak nieświadomy transfer naprawdę działa, to inna kwestia;)
• Poza Yao ' zniekształcony obwód może ' nie mogą być ponownie użyte. Czy możesz rozwiązać moje zamieszanie, że " Czy można przypisać różne klawisze za każdym razem, gdy wykonywany jest zniekształcony obwód lub klawisze są ustalone dla bitów wejściowych 0 i 1 "