Was genau ist eine “ verstümmelte Schaltung ”?

Eine -Schaltung ist nur eine Möglichkeit, eine Berechnung darzustellen. Eine Schaltung ist nicht spezifisch kryptografisch. Dies bedeutet lediglich eine geradlinige Berechnung (keine Schleifen- oder Flusssteuerungskonstrukte), die nur aus Operationen an Bits wie AND, OR, NOT besteht.

A verstümmelte Schaltung ist eine Möglichkeit zum „Verschlüsseln einer Berechnung“, bei der nur die Ausgabe der Berechnung angezeigt wird, jedoch nichts über die Eingaben oder Zwischenwerte . Wir verwenden den Begriff „Schaltung“, weil verstümmelte Schaltungen funktionieren, indem sie die Berechnung, die Ihnen wichtig ist, ausgedrückt als Schaltung , und dann für jede Operation (UND, ODER, NICHT) in der Schaltung einige kryptografische Aufgaben ausführen .

Wenn wir etwas genauer sein wollen, besteht ein „Verstümmelungsschema“ aus:

• (Verstümmelung) Eine Möglichkeit, eine (Ebene) umzuwandeln Schaltung $ C $ in eine verstümmelte Schaltung $ \ widehat C $.

• (Encode) Eine Möglichkeit, eine beliebige (einfache) Eingabe $ x $ umzuwandeln für die Schaltung in einen verstümmelten Eingang $ \ widehat x $. Sie benötigen die geheime Zufälligkeit, mit der die Schaltung verstümmelt wurde, um $ x $ in $ \ widehat x $ zu kodieren.

• (Auswerten) Eine Möglichkeit, ein verstümmelt zu nehmen Schaltung $ \ widehat C $ und verstümmelte Eingabe $ \ widehat x $ und Berechnung der Schaltungsausgabe $ C (x) $. Jeder kann dies tun, Sie müssen $ x $ oder die geheime Zufälligkeit in $ \ widehat C $ nicht kennen, um $ C (x) $ zu bewerten und zu lernen.

Ich vereinfache hier ein wenig. Die Hauptidee der Sicherheit ist jedoch, dass $ \ widehat C $ und $ \ widehat x $ zusammen nicht mehr Informationen als $ C (x) $ verlieren. Insbesondere enthüllen sie nichts über $ x $, erlauben jedoch die Berechnung von $ C (x) $ (ohne es zu merken). Dies ist, was ich mit „Verschlüsseln einer Berechnung“ meine.

Die Hauptanwendung für verstümmelte Schaltkreise ist die sichere Zwei-Parteien-Berechnung. Stellen Sie sich vor, Alice hat eine private Eingabe $ x $ und Bob hat eine private Eingabe $ y $. Sie sind sich über eine Funktion $ f $ einig und sind sich einig, dass sie beide $ f (x, y) $ lernen wollen, aber nicht, dass ihr Gegner etwas mehr als $ f (x, y) lernt ) $. Um dies zu erreichen, können sie Folgendes tun (dies ist Yaos klassisches Protokoll):

1. Die Parteien vereinbaren einen Weg, $ f $ als (einfach) auszudrücken ) Schaltkreis. Alice verstümmelt die Schaltung $ f \ mapsto \ widehat f $. Sie sendet $ \ widehat f $ an Bob sowie ihre eigene „verstümmelte Eingabe“ $ \ widehat x $.

2. Alice weiß, wie man eine Eingabe für $ f $ codiert eine „verstümmelte“ Eingabe, aber nur Bob kennt seine private Eingabe $ y $. Also arrangieren die Parteien, dass Bob eine verstümmelte Version $ \ widehat y $ abholt, ohne dass Alice erfährt, was $ y $ ist. Dies kann mit einem Grundelement erfolgen, das als vergessene Übertragung bezeichnet wird.

3. Jetzt hat Bob die verstümmelte Schaltung $ \ widehat f $ und eine verstümmelte Eingabe $ \ widehat x, \ widehat y $ für diese Schaltung. Er kann dann das Bewertungsverfahren ausführen und $ f (x, y) $ lernen. Er kann Alice $ f (x, y) $ offenbaren.

Wir können argumentieren, dass das Protokoll im Folgenden nicht mehr als $ f (x, y) $ enthüllt Weg:

• Alice sieht in diesem Protokoll nichts anderes als die endgültige Antwort $ f (x, y) $ (die Sicherheit der ahnungslosen Übertragung stellt sicher, dass sie nichts im Gleichschritt lernt 2).

• Obwohl Bob $ \ widehat f $, $ \ widehat x $ und $ \ widehat y $ sieht, stellt die Sicherheit verstümmelter Schaltkreise sicher, dass diese Werte nicht “ t enthüllt nichts über $ f (x, y) $ hinaus.

Dieser Ansatz funktioniert, wenn Alice & Bob halb ehrlich ist (dh sie folgen dem Protokoll wie angewiesen). Aber wenn Alice bösartig ist, kann sie eine andere Funktion $ f „$ anstelle der $ f $, auf die sie sich geeinigt haben, verstümmeln.Daher müssen dem Protokoll andere Dinge hinzugefügt werden, um dies zu verhindern, wenn wir Sicherheit gegen böswillige Gegner wünschen.

Referenzmaterial:

• Die Yao-Konstruktion und ihr Sicherheitsnachweis (Video), Yehuda Lindell
• Ein Beweis des Yao-Protokolls für eine sichere Zwei-Parteien-Berechnung , Yehuda Lindell & Benny Pinkas
• Grundlagen verstümmelter Schaltkreise , Mihir Bellare, Viet Tung Hoang, Phillip Rogaway
• Eine kurze Geschichte praktischer Optimierungen für verstümmelte Schaltkreise , ein Video von mir Die ersten Folien befassen sich mit der „klassischen“ Konstruktion verstümmelter Schaltkreise.

Kommentare

• Wie verstümmelt Bob y ohne die geheime Zufälligkeit zu kennen, die Alice gewählt hat, als sie das Verstümmelungsschema entwickelt hat?
• Die verstümmelte Codierung funktioniert Stück für Stück. Nehmen Sie Bob s erstes Bit. Alice kann sich denken: " Wenn Bob das Bit 0 eingegeben hat, sollte seine verstümmelte Codierung $ G_0 $ sein. Wenn er Bit 1 eingegeben hat, sollte seine verstümmelte Codierung $ G_1 $ sein. " Oblivious transfer ist ein Grundelement, bei dem Alice zwei Zeichenfolgen $ G_0, G_1 $ bereitstellt als Eingabe. Bob liefert ein bisschen $ b $ als Eingabe und lernt $ G_b $ (aber nicht das andere $ G_ {1-b} $). Alice lernt nicht ' $ b $. Die Parteien können für jedes Bit der Eingabe von Bob ' eine unbewusste Übertragung durchführen. Was wie ahnungslose Übertragung wirklich funktioniert, ist eine andere Frage;)
• Neben Yao ' kann die verstümmelte Schaltung ' darf nicht wiederverwendet werden. Können Sie bitte meine Verwirrung auflösen, dass " es möglich ist, jedes Mal, wenn eine verstümmelte Schaltung ausgeführt wird oder unterschiedliche Schlüssel für die Eingangsbits 0 und 1 festgelegt werden, unterschiedliche Schlüssel zuzuweisen? >