💻 computer science

Plausible Deniability in Fully Homomorphic Computation

Dieses Paper stellt PD-FHC vor, ein Framework für plausible Abstreitbarkeit in der vollhomomorphen Berechnung, das eine einzelne Fredkin-Gate-Verdrahtung auf RGB-Bildern nutzt, um gleichzeitig einen echten booleschen Schaltkreis und mehrere Täuschungen auszuführen, wodurch es Nutzern ermöglicht wird, Berechnungen an vertrauensunwürdige Clouds auszulagern, während sie informationstheoretische Positionsprivatsphäre sowie die Fähigkeit zur Offenlegung einer verifizierbaren Täuschung unter Zwang beibehalten.

Ursprüngliche Autoren: Shahzad Ahmad, Stefan Rass, Zahra Seyedi

Veröffentlicht 2026-07-13

📖 7 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Shahzad Ahmad, Stefan Rass, Zahra Seyedi

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich vor, Sie sind ein Fotolabortechniker, der eine geheime, private Berechnung an einer Gruppe von Bildern durchführen muss. Vielleicht müssen Sie prüfen, ob ein bestimmtes Maß in einem Foto einen gewissen Grenzwert überschreitet. Aber es gibt einen Haken: Sie müssen diese Fotos an einen Cloud-Computer senden, dem Sie nicht voll vertrauen.

Normalerweise würden Sie Fully Homomorphic Encryption (FHE) verwenden, wenn Sie Ihre Daten geheim halten wollen. Stellen Sie sich das wie das Versetzen Ihrer Fotos in eine unknackbare, leuchtende Glaskiste vor. Die Cloud kann zwar Mathematik mit der Kiste betreiben, aber sie kann nicht hineinsehen. Das Problem ist nur: Die leuchtende Kiste ist ein verdächtiges Signal. Wenn ein herrische, erpressbarer Gegner (wie ein Regierungsagent oder ein strenger Chef) verlangt zu wissen, was Sie tun, kann er auf die leuchtende Kiste zeigen und sagen: „Du machst definitiv geheime Berechnungen! Übergib mir den Schlüssel!“ Sie können es nicht leugnen, weil die Kiste selbst „Geheimnis!“ schreit.

Dieses Paper stellt einen cleveren neuen Trick namens PD-FHC (Plausible Deniability in Fully Homomorphic Computation) vor. Anstatt einer leuchtenden Kiste stellen Sie sich vor, Sie würden Ihre geheime Berechnung in einem riesigen, gewöhnlich aussehenden Bildfilter verstecken.

Der Zaubertrick: Eine Verschaltung, viele Geschichten

So funktioniert der Zaubertrick unter Verwendung einer spielerischen Analogie:

Stellen Sie sich vor, Sie haben ein riesiges Gitter aus 12.000 winzigen Lichtschaltern (das sind die Pixel eines Bildes). Sie möchten eine geheime Berechnung mit einem spezifischen Muster von Schaltern (Ihren „echten“ Schaltkreis) durchführen. Aber Sie wollen auch in der Lage sein, eine andere Geschichte zu erzählen, falls jemand Sie dazu zwingt, zu erklären, was Sie getan haben.

Die Autoren verwenden einen speziellen Typ von Schalter, den Fredkin-Gate. Betrachten Sie ein Fredkin-Gate als einen magischen Verkehrspolizisten für drei Fahrspuren. Er hat ein Kontrollbit (eine kleine Flagge), das entscheidet, was er tut:

Wenn die Flagge unten ist, lässt er die Autos einfach geradeaus fahren.
Wenn die Flagge oben ist, tauscht er die Autos in den beiden Seitenspuren.

Nun, hier ist der geniale Teil: Der Cloud-Anbieter sieht nur die Anweisungen des Verkehrspolizisten (die Verschaltung), nicht die Flaggen.

Das Setup: Sie nehmen Ihre geheime Berechnung und wandeln sie in ein spezifisches Muster von Flaggen um. Sie erfinden auch mehrere „Dekoy“-Berechnungen (wie das Prüfen der Bildhelligkeit oder des Farbgleichgewichts) und wandeln diese in andere Muster von Flaggen um.
Das Einbetten: Sie verstecken die Flaggen für Ihre geheime Berechnung in ein paar spezifischen Lichtschaltern. Sie verstecken die Flaggen für Ihre Dekoy-Berechnungen in anderen Schaltern. Für jeden verbleibenden Schalter im Bild füllen Sie ihn mit zufälligem Rauschen.
Die Aufgabe der Cloud: Sie senden das Bild an die Cloud. Sie sagen ihnen: „Bitte führen Sie dieses spezifische Verkehrspolizei-Muster auf jedem einzelnen Schalter im Bild aus.“ Die Cloud weiß nicht, welche Schalter Ihre Geheimnisse enthalten, welche ein Dekoy enthalten und welche nur zufälliges Rauschen sind. Sie wenden einfach dieselbe Regel auf alle gleichzeitig an.
Das Ergebnis: Da die Flaggen (Kontrollbits) für jede Gruppe von Schaltern unterschiedlich sind, führt der Verkehrspolizier am Ende Ihre geheime Mathematik auf den geheimen Schaltern aus, eine Dekoy-Mathematik auf den Dekoy-Schaltern und zufällige Rausch-Mathematik auf dem Rest.

Der Moment der „Plausiblen Abstreitbarkeit“

Stellen Sie sich nun vor, der erpressbare Gegner taucht auf. „Was haben Sie berechnet?“, verlangt er zu wissen.

Sie können nicht sagen: „Ich habe geheime Mathematik durchgeführt“, denn das ist die Wahrheit. Aber Sie können sagen: „Oh, ich habe nur eine Helligkeitsprüfung auf diesen spezifischen Pixeln durchgeführt!“ Sie zeigen auf einen Ihrer Dekoy-Schaltkreise.

Der Gegner überprüft die Mathematik. Er sieht die versteckten Flaggen, er sieht das Ergebnis und er verifiziert, dass die Mathematik perfekt funktioniert. Er hat keine Möglichkeit zu wissen, dass dies nur ein Dekoy war. Die „echte“ geheime Berechnung bleibt weiterhin unter dem zufälligen Rauschen und den anderen Dekoys verborgen und sieht exakt wie der Rest des Bildes aus.

Was dieses Paper beweist (und was es nicht tut)

Die Autoren sind sehr sorgfältig darin, was sie zu lösen behaupten und was weiterhin ein Mysterium ist.

Was bewiesen wurde:

Das „Positions“-Geheimnis: Wenn Sie Ihr Bild mit zufälligem Rauschen füllen, das dem statistischen Muster Ihrer geheimen Daten entspricht, kann der Cloud-Anbieter nicht erkennen, wo sich Ihre geheimen Schalter befinden. Es ist wie der Versuch, ein bestimmtes Sandkorn an einem Strand zu finden, wenn jedes Korn exakt gleich aussieht. Das Paper beweist, dass unter diesen spezifischen Bedingungen die Chance der Cloud, den richtigen Ort zu erraten, nicht besser als reines Raten ist.
Das „Existenz“-Geheimnis: Wenn Sie gezwungen sind, einige Ihrer Schaltkreise offenzulegen, können Sie die Dekoys offenlegen. Das Paper beweist, dass der Gegner nicht beweisen kann, dass mehr Schaltkreise existieren, als Sie offengelegt haben. Es ist wie ein Magier, der Ihnen ein paar leere Taschen zeigt; Sie können nicht beweisen, dass es eine versteckte Tasche gibt, die er Ihnen nicht gezeigt hat.

Was ausgeschlossen wurde oder nicht gelöst wurde:

Keine „unsichtbare“ Mathematik: Das Paper stellt explizit klar, dass dies nicht verbirgt, dass eine Berechnung stattfindet. Die Cloud weiß, dass eine Berechnung läuft, weil sie diese durchführt. Die Magie liegt nur darin, zu verbergen, welche Berechnung es ist und wo die geheimen Daten liegen.
Keine „magische“ Obfuskation: Die Autoren lehnen die Idee ab, komplexe kryptografische Tricks zu verwenden, um die Struktur des Schaltkreises (die Verschaltung) zu verbergen. Sie geben zu, dass die Verschaltung für die Cloud sichtbar ist. Das Einzige, was verborgen wird, ist die Bedeutung der Gates, die aus den versteckten Flaggen resultiert. Die Verschaltung selbst ist sichtbar.
Kein „perfekter“ Deckmantel für jedes Bild: Sie können nicht einfach ein beliebiges Urlaubsfoto nehmen und Ihr Geheimnis darin verstecken. Das Paper argumenttiert, dass wenn das natürliche „Rauschen“ des Fotos nicht mit dem von Ihnen hinzugefügten Zufallsrauschen übereinstimmt, ein intelligenter Detektor den Unterschied bemerken könnte. Sie benötigen eine Cover-Story, die viel Zufälligkeit erwartet (wie einen Dithering-Dienst oder ein Rausch-Injektions-Tool). Wenn Sie versuchen, Ihr Geheimnis in einem normalen Foto zu verstecken, könnten Sie entdeckt werden.

Wie sicher sind sie sich?

Die Autoren sind sich ihrer Mathematik sehr sicher, aber ehrlich bezüglich der Grenzen.

Die Mathematik: Sie haben bewiesen, dass, wenn Sie ihre Regeln befolgen (das Zufallsrauschen perfekt anpassen), der Vorteil der Cloud, Ihr Geheimnis zu finden, exakt null ist. Das ist keine Vermutung; es ist eine mathematische Gewissheit basierend auf den Eigenschaften des Fredkin-Gates.
Die reale Welt: Sie haben Simulationen (Computertests) mit Bildern von 128x128 Pixeln bis hin zu 512x512 Pixeln und Schaltkreisen von 5 bis 302 Gates durchgeführt. Diese Tests zeigten, dass das System schnell genug arbeitet, um praktikabel zu sein, und mit bestehenden Verschlüsselungswerkzeugen konkurrieren kann.
Die Schwachstelle: Das Einzige, wofür sie keinen harten Beweis haben, ist der „semantische“ Teil. Können Sie immer eine glaubwürdige Dekoy-Geschichte erfinden? Zum Beispiel, wenn Sie behaupten, Sie hätten eine „Bildhelligkeit“ geprüft, sieht die Mathematik dann tatsächlich wie eine Helligkeitsprüfung aus? Das Paper gibt zu, dass dies menschliche Kreativität und Domänenwissen erfordert. Es ist eine „plausible“ Geschichte, aber das Paper beweist nicht, dass man dies perfekt automatisieren kann.

Das Fazkurt (The Bottom Line)

Dieses Paper bietet einen Weg, geheime Mathematik an die Cloud auszulagern, ohne ein leuchtendes „Ich mache Geheimnisse!“-Schild zu hinterlassen. Es verwandelt Ihre geheime Berechnung in eine Nadel im Heuhaufen, wobei der Heuhaufen aus anderen Nadeln besteht, die exakt gleich aussehen. Wenn jemand Sie zwingt, eine Nadel zu zeigen, können Sie ihm eine falsche zeigen, die jeden Test besteht.

Es ist kein magischer Schutzschild, der die Mathematik unsichtbar macht, und es funktioniert nicht, wenn Sie versuchen, es in der falschen Art von Bild zu verstecken. Aber für das richtige Setup bietet es Ihnen eine neue, mächtige Superkraft: die Fähigkeit zu sagen: „Ich habe nur dieses langweilige Ding gemacht“, und die Mathematik, die Ihnen recht gibt.

Technische Zusammenfassung: Plausible Abstreitbarkeit in der vollhomomorphen Berechnung (PD-FHC)

1. Problemstellung

Die Auslagerung von Berechnungen an nicht vertrauenswürdige Cloud-Anbieter setzt Nutzer zwei unterschiedlichen Bedrohungen aus, die bestehende Technologien nicht gleichzeitig adressieren können:

Komputationelle Privatsphäre: Schutz der Daten vor „honest-but-curious“ (ehrlichen, aber neugierigen) Anbietern (adressiert durch vollhomomorphe Verschlüsselung (FHE) und Trusted Execution Environments (TEEs)).
Plausible Abstreitbarkeit (Plausible Deniability): Die Fähigkeit, die Existenz oder die Absicht einer Berechnung glaubhaft zu leugnen, wenn man von einem mächtigen Akteur unter Druck gesetzt wird.

Aktuelle Lösungen weisen kritische Lücken auf:

FHE: Während es Datenwerte verbirgt, ist die Übertragung von Chiffretexten auffällig. Ein koaktiver Akteur kann die Entschlüsselungsschlüssel fordern, und allein die Verwendung von FHE bestätigt, dass eine private Berechnung stattfindet.
TEEs: Diese erzeugen Attestierungsprotokolle, die als unumstößlicher Beweis für die Ausführung dienen. Zudem sind sie anfällig für Seitenkanal-Lecks.
Secure Multi-Party Computation (MPC): Obwohl robust gegenüber der Offenlegung eines einzelnen Anteils einer Partei, ermöglicht MPC den Teilnehmern nicht zu leugnen, dass die Berechnung überhaupt stattfand oder eine andere Berechnung zu substituieren.
Deniable Encryption/Storage: Diese adressieren statische Daten (Nachrichten oder Dateien), dehnen dies jedoch nicht auf dynamische Berechnungsinformationen aus.

Das Paper identifiziert eine Lücke, bei der ein Nutzer eine boolesche Berechnung auslagern muss, während er gleichzeitig die Fähigkeit beibehalten muss, zu verleugnen, was berechnet wurde und gegenüber einem externen Beobachter sogar zu verleugnen, dass überhaupt eine Berechnung stattfand.

2. Methodik

Die Autoren schlagen PD-FHC vor, ein Framework, das boolesche Berechnungen mittels Fredkin-Gates und Least Significant Bit (LSB)-Steganographie in ein Cover-Medium (speziell RGB-Bilder) einbettet.

Kernmechanismus:

Gemeinsame Verdrahtung, variable Semantik: Das Framework nutzt eine einzige, feste Verdrahtung universeller Fredkin-Gates. Ein Fredkin-Gate ist ein reversibles 3-Eingangs-/3-Ausgangs-Gate, bei dem ein Steuerbit bestimmt, ob die beiden Datenbits vertauscht werden.
- Wenn das Steuerbit 0 ist, fungiert das Gate als Durchgang (Pass-through).
- Wenn das Steuerbit 1 ist, vertauscht das Gate die Datenbits.
- Durch das Setzen der Steuerbits via eingebetteter Daten kann dieselbe physische Verdrahtung an verschiedenen Stellen unterschiedliche logische Funktionen (z. B. AND, OR, NOT oder komplexe Schaltkreise) implementieren.
Einbettung an mehreren Orten (Multi-Location Embedding): Der Nutzer (Alice) bettet einen „echten“ Schaltkreis und $L-1$ $L - 1$ „Dekoy“-Schaltkreise (Lockvögel) in die LSBs eines Bildes ein.
- Echter Schaltkreis: Eingebettet an einem geheimen Satz von Positionen $\Lambda_{j^*}$ .
- Dekoy-Schaltkreise: Eingebettet an anderen, disjunkten Positionssätzen $\Lambda_j$ .
- Füll-Bits (Fill Bits): Alle verbleibenden LSB-Positionen werden mit Bits gefüllt, die aus einer spezifischen Verteilung $\pi$ gezogen wurden.
Einheitliche Verarbeitung: Der Cloud-Anbieter (Carol) erhält das Bild und die Verdrahtungsspezifikation ( $C_{obf}$ ). Sie wendet das Fredkin-Gate einheitlich auf jede Pixelposition in Parallelität an. Sie weiß nicht, welche Positionen echte Daten, Dekoy-Daten oder Füllrauschen enthalten.
Reaktion auf Koerzition: Wenn Alice unter Druck gesetzt wird, offenbart sie die Positionssätze, Eingaben und Ausgaben für einen Dekoy-Schaltkreis. Da die Verdrahtung identisch ist und der Dekoy-Schaltkreis verifizierbare Ergebnisse liefert, die konsistent mit dem Output der Cloud sind, kann der Akteur den Dekoy nicht von der echten Berechnung unterscheiden.

Theoretische Grundlagen:

Deniable Computation Medium (DCM): Ein abstraktes Framework, das ein Medium definiert, das über adressierbare Bit-Positionen, Lese- und Schreibfähigkeiten sowie eine Gate-Familie verfügt, die einheitlich angewendet wird.
Matched-Marginal Condition: Für informationstheoretische Sicherheit müssen die Bits an den echten Positionen, Dekoy-Positionen und Füll-Positionen derselben pro-Position-Wahrscheinlichkeitsverteilung $\pi$ folgen. Unter dieser Bedingung ist die LSB-Ebene „austauschbar“, was bedeutet, dass die statistische Verteilung des Bildes invariant gegenüber der Permutation der Positionen ist.

3. Kernbeiträge

Abstraktes Framework: Definition eines Deniable Computation Medium (DCM) und eines Deniable Computation Scheme (DCS), die das Sicherheitsmodell von spezifischen Cover-Medien (z. B. Bilder, Audio, Pakete) trennen.
Formalisierung des Bedrohungsmodells: Ein zweiphasiges Modell, das zwischen unterscheidet:
- Honest-but-Curious (HBC) Cloud: Besorgt um die Komputationelle Privatsphäre (Verbergen der Daten).
- Koaktiver Akteur (Coercive Adversary): Besorgt um die Plausible Abstreitbarkeit (Verbergen der Existenz und der Absicht der Berechnung).
  Die Autoren definieren neuartige Multi-Round Coercion Games, die „Existenz-Unterscheidbarkeit“ (Kann der Akteur beweisen, dass versteckte Schaltkreise existieren?) und „Schaltkreis-Entdeckung“ (Kann der Akteur den echten Schaltkreis unter den enthüllten Dekoys identifizieren?) messen.
Bildbasierte Instanziierung: Eine konkrete Implementierung unter Verwendung von RGB-Bildern und Fredkin-Gates.
- Beweis der Positions-Privatsphäre: Unter der Matched-Marginal-Bedingung beweist das Paper, dass der Cloud-Anbieter einen Vorteil von Null (informationstheoretisch) beim Auffinden der echten Schaltkreispositionen gegenüber dem Zufall hat, unabhängig von der Verteilung $\pi$ .
- Partielle Verschleierung des Schaltkreises: Die Verdrahtung ist sichtbar, aber die Semantik der Gates ist verborgen. Das Paper beweist, dass die Verdrahtung ohne Kenntnis der Steuerbits nichts darüber verrät, welche Funktion berechnet wird.
Implementierung und Benchmarking: Eine Python-Implementierung, die über Schaltkreisgrößen (5–302 Gates) und Bilddimensionen ( $128^2$ bis $512^2$ ) getestet wurde.

4. Ergebnisse

Sicherheitsgarantien:
- Komputationelle Privatsphäre: Die Cloud erfährt nichts über die geheimen Datenwerte oder die spezifische Funktion, sofern die Gate-Familie die statistische Verteilung der nicht-geheimen Positionen bewahrt (eine Eigenschaft, die Fredkin-Gates via Bit-Permutation erfüllen).
- Existenz-Verbergen: Unter der Matched-Marginal-Bedingung ist der Vorteil hinsichtlich der Existenz exakt Null. Ein Akteur kann nicht zwischen einem Bild, das nur Füllbits enthält, und einem Bild, das versteckte Schaltkreise enthält, unterscheiden.
- Schaltkreis-Entdeckung: Der Vorteil bei der Identifizierung des echten Schaltkreises unter den nicht enthüllten Dekoys ist durch die semantische Plausibilität der Dekoys und Seitenkanal-Leckagen begrenzt. Die Positions- und Verdrahtungsvektoren tragen mit Null zum Vorteil des Akteurs bei.
Performance: Die Implementierung zeigt eine wettbewerbsfähige Performance gegenüber TFHE (einer führenden FHE-Bibliothek) für boolesche Schaltkreise, während sie gleichzeitig die Deniability bietet, die FHE nicht bieten kann.
Visuelle Unauffälligkeit: Die Modifikation der LSBs führt zu einer maximalen Verschiebung von $\pm 1$ pro Kanal, was einen PSNR > 50 dB ergibt und die Änderungen visuell unmerklich macht.

5. Bedeutung und Ansprüche

Das Paper beansprucht, das erste Framework zu sein, das gleichzeitig komputationelle Privatsphäre, Existenz-Verbergen (gegenüber externen Beobachtern) und partielle Verschleierung des Schaltkreises (gegenüber dem Cloud-Anbieter) erfüllt.

Bescheidene Ansprüche und Limitationen:

Umfang der Cover-Plausibilität: Die Autoren stellen explizit klar, dass PD-FHC nicht für beliebige Bilder (z. B. Urlaubsfotos) funktioniert. Das Cover-Medium muss legitim hohe Entropie in den LSB-Inputs erwarten (z. B. Dithering, Rauschinjektion oder Verarbeitung im verschlüsselten Bereich). Wenn der deklarierte Dienst natürliche Bilder erwartet, wird die für die Sicherheit erforderliche uniforme LSB-Ebene detektierbar.
Echte Input-Beschränkungen: Die informationstheoretische Garantie eines Null-Vorteils gilt exakt nur dann, wenn die echten Input-Bits des Nutzers ebenfalls derselben Verteilung $\pi$ folgen wie die Dekoy- und Füll-Bits. Bei strukturierten echten Inputs ist der Vorteil durch die statistische Distanz ( $\Delta$ ) zwischen der Verteilung der echten Inputs und $\pi$ begrenzt.
Semantische Plausibilität: Die Sicherheit gegen Schaltkreis-Entdeckung beruht auf der $\epsilon$ -Plausibilität der Dekoy-Schaltkreise. Das Paper gibt zu, dass die Konstruktion semantisch glaubwürdiger Dekoys (z. B. eine Helligkeitsprüfung vs. ein kryptographischer Hash) eine manuelle, domänenspezifische Aufgabe ist und noch nicht automatisiert wurde.
Aktive Angriffe: Das Framework setzt einen „honest-but-curious“ Cloud-Anbieter und passive externe Beobachter voraus. Es schützt nicht vor aktiven Angreifern, die das Bild modifizieren oder die Berechnung verweigern könnten.
Keine kryptographische Obfuskation: Das Paper vermeidet explizit den Anspruch auf kryptographische Schaltkreis-Obfuskation (die Gegenstand von Unmöglichkeitsbeweisen ist). Die „Obfuskation“ ist rein steganographisch und beruht auf den verborgenen Steuerbits, die die Semantik der Gates variieren.

Zusammenfassend bietet PD-FHC einen neuartigen Ansatz zur Auslagerung von Berechnungen, bei dem der Nutzer die spezifische Absicht der Berechnung glaubhaft leugnen kann, indem er eine verifizierbare, alternative Funktion präsentiert, die unter Koerzition ununterscheidbar von der echten ist, sofern die statistischen Bedingungen des Cover-Mediums erfüllt sind.