💻 computer science

Quantum Leakage Resilience of Shamir Secret Sharing

Diese Arbeit stellt fest, dass unveränderte Shamir-Secret-Sharing-Verfahren über Primkörper sicher gegenüber lokalem Quanten-Leakage bleiben, wenn die Schwellenrate etwa 0,73339 überschreitet, vorausgesetzt, dass die Leakage-Geräte eine begrenzte oder keine Verschränkung aufweisen, während gleichzeitig aufgezeigt wird, dass beliebige Verschränkung zwischen Geräten die Sicherheit selbst bei klassischem Leakage vollständig brechen kann.

Ursprüngliche Autoren: Rishabh Batra, Fuyuki Kitagawa, Ryo Nishimaki, Takashi Yamakawa

Veröffentlicht 2026-09-30

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Rishabh Batra, Fuyuki Kitagawa, Ryo Nishimaki, Takashi Yamakawa

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

Im digitalen Zeitalter bedeutet der Schutz eines Geheimnisses oft, es in Stücke zu zerlegen und diese Stücke verschiedenen Personen zu übergeben. Diese Methode, bekannt als Secret Sharing (Geheimnisverarbeitung), stellt sicher, dass keine einzelne Person den gesamten Schlüssel zu einem Tresor, einem Passwort oder einem privaten Code besitzt. Stattdessen müssen eine bestimmte Anzahl von Personen zusammenkommen, um die ursprüngliche Information zu rekonstruieren. Dieser Ansatz ist ein Eckpfeiler der modernen Kryptographie, der zur Verwaltung von Verschlüsselungsschlüsseln und zur Sicherung der Kommunikation eingesetzt wird. Jahrzehntelang haben Forscher untersucht, wie man diese Systeme gegen eine spezifische Art von Bedrohung robust macht: einen Angreifer, der nicht die gesamten Stücke stehlen kann, aber in der Lage ist, einen Blick auf winzige Fragmente davon zu werfen. Dies wird als Leakage (Informationsabfluss) bezeichnet. Wenn ein Angreifer in der Lage ist, auch nur ein einziges Bit an Information aus jedem Stück einer Person zu lesen, könnte er in der Lage sein, das gesamte Geheimnis zusammenzusetzen. Die Frage war stets: Wie viel kann ein Angreifer lernen, bevor das System versagt?

Da sich die Technologie nun von klassischen Computern hin zu Quantenmaschinen bewegt, verändert sich die Natur dieser winzigen Fragmente. Anstatt nur Bits an Information zu extrahieren, könnte ein Angreifer ein Quantenbit, oder Qubit, extrahieren, das in einem komplexen Zustand multipler Möglichkeiten gleichzeitig existieren kann. Eine neue Studie von Forschern der EPFL und der NTT Social Informatics Laboratories untersucht, ob die standardmäßige, weit verbreitete Methode des Secret Sharing dieser neuen Art des „Quanten-Spähens“ standhalten kann. Sie fanden heraus, dass das System sicher bleibt, aber nur, wenn die Anzahl der Menschen, die erforderlich sind, um das Geheimnis zu entschlüsseln, hoch genug ist. Konkret gilt: Wenn die Gruppe mehr als etwa dreiundsiebzig Prozent der Gesamtzahl der Teilnehmer benötigt, um das Geheimnis zu rekonstruieren, hält das Schema stand, selbst wenn ein Angreifer versucht, ein Quantenbit aus jedem einzelnen Anteil der Teilnehmer zu extrahieren. Diese Sicherheit gilt auch dann, wenn der Angreifer alle geleakten Quantenbits gleichzeitig misst.

Die Forscher untersuchten auch ein komplexeres Szenario, in dem die Geräte, die die Geheimnisanteile halten, eine spezielle Quantenverbindung namens Verschränkung (Entanglement) untereinander oder sogar mit dem Angreifer teilen könnten. Verschränkung ist ein Phänomen, bei dem Teilchen so miteinander verknüpft sind, dass der Zustand des einen augenblicklich den anderen beeinflusst, unabhängig von der Entfernung. Die Studie zeigt, dass das System dieser Bedrohung standhalten kann, vorausgesetzt, die Anzahl der Geräte, die diese Verbindungen teilen, bleibt im Vergleich zur Gesamtgruppengröße relativ gering. Die Forscher entdeckten jedoch auch eine harte Grenze. Wenn die Anzahl der Geräte, die Verschränkung teilen, zu groß wird, wird das System verwundbar. Sie demonstrierten einen spezifischen Angriff, bei dem eine Gruppe von Geräten, die einen gemeinsamen Quantenzustand namens GHZ-Zustand nutzt, jeweils nur ein klassisches Bit leaken und dennoch das Geheimnis enthüllen konnte. Dieser Angriff funktioniert selbst dann, wenn die Geräte keine Verschränkung mit dem Angreifer haben, was beweist, dass die Größe der verschränkten Gruppe der entscheidende Faktor ist.

Die Arbeit stützt sich auf einen mathematischen Ansatz, der den Prozess des Secret Sharing wie ein Wellenmuster behandelt. Durch die Analyse der Wechselwirkungen dieser Wellen konnten die Forscher beweisen, dass das geleakte Geheimnis, solange die Schwelle für die Rekonstruktion hoch genug ist, zu stark gestreut ist, um nützlich zu sein. Sie zeigten, dass für eine Gruppe von Teilnehmern, wenn die zur Entschlüsselung erforderliche Anzahl etwa dreiundsiebzig Prozent der Gesamtzahl beträgt, die Wahrscheinlichkeit, dass ein Angreifer das Geheimnis korrekt errät, so gering ist, dass sie effektiv bei Null liegt. Dieses Ergebnis ist signifikant, da es auf die unveränderte Version des Secret-Sharing-Schemas anwendbar ist, das bereits heute im Einsatz ist, was bedeutet, dass keine Änderungen an bestehenden Protokollen vorgenommen werden müssen, um dieses Maß an Quantensicherheit zu erlangen.

Die Studie klärt auch die Grenze zwischen Sicherheit und Gefahr. Während eine kleine Anzahl von Geräten, die Verschränkung teilen, sicher ist, bewiesen die Forscher, dass die Sicherheit kollabiert, wenn eine ausreichend große Gruppe diese Verbindungen teilt. Sie fanden heraus, dass selbst mit klassischen Bits, wenn genügend Geräte verschränkt sind, sie ihre Leaks koordinieren können, um das Geheimnis zu enthüllen. Dies deutet darauf hin, dass in einer Welt mit Quantenfähigkeiten die Sicherheit des Secret Sharing nicht nur davon abhängt, wie viel Information geleakt wird, sondern wie die Geräte, die diese Informationen halten, miteinander verbunden sind. Die Ergebnisse liefern eine klare Karte darüber, wo diese Systeme sicher sind und wo sie es nicht sind, und bieten einen Leitfaden für den Aufbau sicherer Systeme in einer Zukunft, in der Quantencomputer Realität sind.

Die Forscher hörten nicht bei der Beweisführung der Sicherheit auf; sie identifizierten auch den präzisen Punkt, an dem sie versagt. Sie berechneten, dass für ein System, das gegen eine lineare Anzahl verschränkter Geräte sicher bleiben soll, die Schwellenrate ausreichend hoch sein muss. Wenn die Schwelle zu niedrig ist, ist das System unsicher. Dieses Gleichgewicht zwischen der Anzahl der Teilnehmer, die zur Entschlüsselung benötigt werden, und der Menge der erlaubten Verschränkung ist die zentrale Erkenntnis. Die Studie bestätigt, dass Quanten-Leakage zwar ein ernstes Problem darstellt, aber mit den richtigen Parametern handhabbar ist. Die Ergebnisse bieten einen beruhigenden Schluss für diejenigen, die auf diese kryptographischen Werkzeuge vertrauen: Die vertrauten Methoden des Secret Sharing sind widerstandsfähig, sofern die Regeln für die Rekonstruktion hoch genug angesetzt sind, um die Quantenbedrohungen abzuwehren.

Technisches Resümee: Quanten-Leckage-Resilienz von Shamir-Secret-Sharing

Problemstellung

Die vorliegende Arbeit untersucht die Quanten-Leckage-Resilienz des standardmäßigen, unveränderten Shamir-Secret-Sharing-Verfahrens über Primkörpern $\mathbb{F}_p$ . Während Shamirs Schema in der Schwellenwert-Kryptographie und der sicheren Mehrparteien-Berechnung weit verbreitet ist, setzen seine Sicherheitsgarantien traditionell voraus, dass unbefugte Mengen nichts über das Geheimnis erfahren. In der Praxis kann jedoch Teilinformationen (Leckage) durch Seitenkanäle exponiert werden.

Die Autoren erweitieren die Untersuchung der lokalen Leckage-Resilienz vom klassischen Setting (in dem ein Angreifer einen kurzen klassischen Output, z. B. ein Bit, von jedem Share erhält) auf das Quanten-Setting. In diesem Modell erhält das Gerät eines jeden Teilnehmers einen klassischen Share und gibt ein einzelnes Qubit (oder eine kleine Anzahl von Qubits) an einen Angreifer aus, der gemeinsame Messungen durchführen kann. Die Studie untersucht ferner, wie vorhandene Verschränkung (pre-shared entanglement) zwischen den Leckage-Geräten oder zwischen den Geräten und dem Angreifer die Sicherheit beeinflusst.

Methodik

Das Paper verwendet eine Kombination aus Fourier-Analyse über endlichen Körpern und den Eigenschaften von Maximum Distance Separable (MDS) Codes, um die Unterscheidungs-Vorteile (distinguishing advantage) zwischen zwei Geheimnis-Zuständen zu begrenzen.

Pauli-Fourier-Reduktion:
- Die Leckage aus jedem Share wird als Dichtematrix $\rho_i(y_i)$ modelliert. Die Autoren expandieren diese in der Pauli-Basis: $\rho_i(y) = \frac{1}{2}(I + r_{i,X}(y)X + r_{i,Y}(y)Y + r_{i,Z}(y)Z)$ .
- Sie definen ein „Fourier-Budget“ $W_i(a)$ basierend auf den quadrierten Beträgen der Fourier-Koeffizienten der Pauli-Koeffizientenfunktionen.
- Unter Verwendung der Parsevalschen Identität und der Orthogonalität der Pauli-Operatoren wird der Unterscheidungs-Vorteil durch eine Summe über den dualen Shamir-Code $C^\perp_0$ begrenzt:
  $\text{Adv} \leq \sum_{a \in C^\perp_0 \setminus \{0\}} \prod_{i=1}^n \sqrt{W_i(a_i)}$
- Dies reduziert das Quanten-Sicherheitsproblem auf die Kontrolle einer gewichteten Summe über den dualen Code, ähnlich wie bei klassischen Leckage-Beweisen, jedoch komplizierter durch die matrixwertige Natur der Koeffizienten.
Umgang mit Verschränkung und Blöcken:
- Disjunkte Blöcke: Für Geräte, die innerhalb disjunkter Blöcke Verschränkung teilen (aber nicht zwischen den Blöcken oder mit dem Angreifer), wenden die Autoren eine Block-MDS-Brascamp-Lieb-Ungleichung an. Dies ermöglicht es ihnen, die Summe der Produkte der Spur-Normen von Fourier-Koeffizienten für Block-Outputs zu begrenzen.
- Verschränkung mit dem Angreifer: Für eine Menge von Geräten $E$ , die eine beliebige Verschränkung mit dem Angreifer teilen, verwenden die Autoren ein Reduktionsargument. Sie zeigen, dass, falls der Angreifer die klassischen Shares von $E$ erfährt, die Sicherheit des verbleibenden Systems auf ein unverschränktes Shamir-Schema mit $n-r$ Parteien und einem Schwellenwert von $t-r$ reduziert wird.
Negative Ergebnisse (Angriffe):
- Das Paper konstruiert einen spezifischen Angriff unter Verwendung eines GHZ-Zustands, der unter $t$ Geräten geteilt wird. Durch Anwendung von Phasenverschiebungen, die von ihren Shares abhängen, und einer Messung in der Pauli-X-Basis können die Geräte zwischen Geheimnissen mit einem hohen Vorteil unterscheiden, selbst wenn sie nur jeweils ein klassisches Bit ausgeben.

Zentrale Beiträge und Ergebnisse

1. Unverschränkte Quanten-Leckage

Die Autoren beweisen, dass Shamir-Secret-Sharing gegen unverschränkte lokale Ein-Qubit-Leckage sicher ist, sofern die Schwellenwert-Rate $\tau = t/n$ einen spezifischen konstanten Wert $\tau^\star \approx 0,73339$ überschreitet.

Ergebnis: Wenn $\tau > \tau^\star + \eta$ (für ein festes $\eta > 0$ ), ist der Unterscheidungs-Vorteil exponentiell klein ( $2^{-\Omega(n)}$ ).
Technik: Dies wird mittels der Block-MDS-Brascamp-Lieb-Ungleichung mit der Blockgröße $b=1$ abgeleitet.

2. Disjunkte verschränkte Blöcke

Die Sicherheit wird auf Szenarien ausgeweitet, in denen Geräte in disjunkte Blöcke einer festen maximalen Größe $b$ unterteilt sind, wobei Geräte innerhalb eines Blocks Verschränkung teilen und gemeinsame Berechnungen durchführen können, die Blöcke jedoch unabhängig vone voneinander und vom Angreifer sind.

Ergebnis: Die Sicherheit gilt für ausreichend hohe Schwellenwert-Raten $\tau > \tau^\star(b)$ , wobei $\tau^\star(b) < 1$ . Mit steigender Blockgröße $b$ nähert sich die erforderliche Schwellenwert-Rate 1 an.
Details: Tabelle 1 im Paper listet hinreichende Schwellenwerte für gleiche Blockgrößen auf (z. B. für $b=2$ , $\tau \approx 0,933$ ; für $b=3$ , $\tau \approx 0,987$ ).

3. Leckage mit Verschränkung zum Angreifer

Das Paper analysiert den Fall, in dem eine lineare Anzahl von Geräten ( $r = \delta n$ ) eine beliebige Verschränkung untereinander und mit dem Angreifer teilen.

Ergebnis: Die Sicherheit bleibt erhalten, wenn die „restliche“ Rate die Bedingung erfüllt:
$\frac{\tau - \delta}{1 - \delta} > \tau^\star$
Dies impliziert, dass bei einer festen Schwellenwert-Rate $\tau > \tau^\star$ die Sicherheit auch dann gewahrt bleibt, wenn ein linearer Anteil der Geräte ( $\delta < \frac{\tau - \tau^\star}{1 - \tau^\star}$ ) eine Verschränkung mit dem Angreifer teilt.

4. Negatives Ergebnis: GHZ-Angriff

Die Autoren demonstrieren, dass das Schema unsicher wird, wenn $t$ Geräte einen GHZ-Zustand teilen, selbst unter klassischer Single-Bit-Leckage.

Mechanismus: $t$ Geräte teilen einen GHZ-Zustand. Jedes wendet eine Phase basierend auf seinem Share an und misst in der X-Basis. Das Produkt der Ergebnisse enthüllt das Geheimnis mit einem Vorteil von $\cos^2(\pi/(2p)) \approx 1 - O(p^{-2})$ .
Implikation: Dieser Angriff erfordert keine Verschränkung mit dem Angreifer, sondern lediglich eine Verschränkung unter den $t$ Leckage-Geräten. Er etabliert, dass die maximale Anzahl an Geräten, die eine beliebige Verschränkung teilen können, während die Sicherheit gewahrt bleibt, linear in $n$ ist (bis zu konstanten Faktoren), aber der optimale Anteil weiterhin eine offene Frage bleibt.

Bedeutung und Behauptungen

Das Paper beansprucht, die Untersuchung der Quanten-Leckage-Resilienz für das weit verbreitete, unveränderte Shamir-Secret-Sharing initiiert zu haben.

Robustheit Standardisierter Verfahren: Die Ergebnisse zeigen, dass das Standard-Shamir-Verfahren starke Sicherheitsgarantien gegen Quanten-Leckage beibehält, ohne dass neue Sharing-Algorithmen oder Protokolländerungen erforderlich sind, sofern die Schwellenwert-Rate ausreichend hoch (über $\approx 0,733$ ) ist.
Rolle der Verschränkung: Die Arbeit hebt eine kritische Unterscheidung hervor: Während unverschränkte Quanten-Leckage mit hohen Schwellenwerten handhabbar ist, kann das Vorhandensein von beliebiger Verschränkung unter den Leckage-Geräten (speziell ein GHZ-Zustand unter $t$ Geräten) die Sicherheit selbst bei klassischen Outputs brechen.
Optimalität: Die Autoren äußern sich bescheiden hinsichtlich der Optimalität ihrer Schranken. Sie merken an, dass der hinreichende Schwellenwert $\tau^\star \approx 0,733$ höher ist als der bekannte klassische Wert ( $\approx 0,668$ ), und werfen die Frage auf, ob diese Lücke geschlossen werden kann. Ähnlich bleibt die Frage, ob der exakte optimale Anteil verschränkter Geräte, der mit Sicherheit vereinbar ist, ein offenes Problem darstellt.

Das Paper schließt mit dem Schluss, dass die Quanten-Leckage-Resilienz fundamental sowohl von der Größe der geleakten Outputs als auch von der Verschränkungsstruktur der verfügbaren Leckage-Geräte abhängt.