⚛️ quantum physics

A Simple and Efficient One-Shot Signature Scheme

Diese Arbeit präsentiert ein neues, einfaches und effizientes One-Shot-Signaturverfahren, das die Shmueli-Zhandry-Konstruktion signifikant verbessert, indem es die Schlüssel- und Signaturgrößen von kubischer auf quadratische Komplexität reduziert, perfekte Korrektheit erreicht und eine starke Signatur-Inkompressibilität für Korrektur- und Wiederherstellungsanwendungen aus jüngster verwandter Arbeit ermöglicht.

Ursprüngliche Autoren: Andrew Huang, Vinod Vaikuntanathan

Veröffentlicht 2026-07-28

📖 6 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Andrew Huang, Vinod Vaikuntanathan

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 eine Welt vor, in der die Gesetze der Physik eine ganz besondere Art von digitalem Schloss erlauben. In unserer heutigen Welt können Sie, wenn Sie einen Schlüssel zu einem Tresor besitzen, diesen so oft wie Sie wollen benutzen. Aber in der seltsamen, quantentechnischen Welt der zukünftigen Kryptografie haben Wissenschaftler einen Weg gefunden, einen „One-Shot“-Schlüssel zu erschaffen. Stellen Sie sich das wie ein magisches, selbstzerstörendes Ticket vor. Sie können dieses Ticket verwenden, um eine Tür zu öffnen und zu beweisen, dass Sie da waren, aber in dem Moment, in dem Sie es benutzen, zerfällt das Ticket zu Staub. Sie können es nicht noch einmal verwenden und Sie können auch keine Kopie davon anfertigen, um es später zu benutzen. Dies ist nicht nur ein cooler Zaubertrick; es ist ein mächtiges Werkzeug, das zu unknackbarem digitalem Geld, unfälschbaren Zertifikaten von Quantenmacht und sogar zu einer Möglichkeit führen könnte, digitale Geheimnisse zu verbrennen, damit sie niemals wiederhergestellt werden können.

Lange Zeit war der Bau dieser „One-Shot-Signaturen“ so, als würde man versuchen, einen Wolkenkratzer aus Zahnstochern zu bauen. Es war theoretisch möglich, aber die Entwürfe waren unglaublich klobig, erforderten enorme Mengen an Quantenspeicher (wie eine Bibliothek voller Bücher, nur um einen einzigen Buchstaben zu signieren) und die Ausführung dauerte lange. Ein jüngster Durchbruch zeigte, dass es machbar war, aber die resultierenden „Schlüssel“ waren riesig und der Prozess war langsam. Nun ist ein neues Paper von Andrew Huang und Vinod Vaikuntanathan vom MIT mit einem eleganten, effizienten Redesign auf den Plan getreten. Sie haben herausgefunden, wie man diese selbstzerstörenden digitalen Tickets mit viel weniger Platz und Zeit bauen kann, was die gesamte Idee für den praktischen Einsatz in der realen Welt tauglich macht.

Das selbstzerstörende Ticket

Das Paper befasst sich mit einem Problem der Quantenkryptografie namens „One-Shot Signatures“ (OSS). Um diese Errungenschaft zu verstehen, stellen Sie sich vor, Sie seien ein Spion, der versucht, eine geheime Nachricht zu senden. In der alten, klobigen Version dieses Spionierspiels war die „Signatur“ (der Beweis, dass Sie die Nachricht gesendet haben) wie ein riesiger, schwerer Rucksack. Wenn Sie eine kurze Notiz signieren wollten, mussten Sie einen Rucksack mit $\Theta(\lambda^4)$ Qubits (dem quantentechnischen Äquivalent zu Bits) tragen. Wenn Sie eine längere Nachricht signieren wollten, wurde der Rucksack sogar noch größer, und der Prozess des Signierens war langsam und kompliziert, wobei der Spion oft eine komplexe Choreografie von Quantenmessungen durchführen musste, um die Aufgabe zu bewältigen.

Die Autoren dieses Papers sagen: „Wir können es besser machen.“ Sie haben ein neues, gestrafftes System entworfen, bei dem der „Rucksack“ viel kleiner ist. Anstatt einer massiven $\Theta(\lambda^4)$ Qubit-Last benötigt ihr neues Schema nur einen Rucksack von $\Theta(\lambda^2)$ Qubits. Das ist eine enorme Reduzierung der Größe. Darüber hinaus sind auch die von ihnen erzeugten Signaturen kleiner und schrumpfen von $\Theta(\lambda^3)$ Bits auf $\Theta(\lambda^2)$ Bits.

Wie sie es geschafft haben: Der „Bild“-Trick

Die vorherige Methode, die von Shmueli und Zhandry entwickelt wurde, war wie der Versuch, eine bestimmte Nadel im Heuhaufen zu finden, indem man nach dem Stroh (dem Präimage) sucht. Es war ein wenig so, als würde man versuchen, ein Passwort zu erraten, indem man vom verschlüsselten Ergebnis rückwärts arbeitet, was viel Ausprobieren und vieles „Quanten-Zurückspulen“ (immer wieder versuchen, bis man es richtig hat) erforderte. Dieser Prozess war ineffizient und führte manchmal dazu, dass keine gültige Signatur erzeugt wurde, was bedeutete, dass der Spion mit einem unbrauchbaren Ticket dastehen konnte.

Huang und Vaikuntanathan haben das Skript gedreht. Anstatt nach der Nadel im Stroh zu suchen, entschieden sie sich, nach dem Stroh in der Nadel zu suchen. In ihrer neuen Konstruktion wird die „Signatur“ direkt im „Bild“ (Image) der Funktion gefunden. Sie nutzen einen cleveren Quanten-Suchalgorithmus (Grover-Suche), um den richtigen Pfad durch die Daten zu finden. Dieser Ansatz ist wie eine Karte, die direkt zum Schatz führt, anstatt wahllos zu graben. Da sie am richtigen Ort suchen, ist der Prozess „perfekt korrekt“. Das bedeutet, dass das System jedes Mal, wenn Sie versuchen, eine Nachricht zu signieren, garantiert funktioniert. Es gibt keine Chance auf ein Scheitern, keine „Hoppla, das Ticket hat nicht funktioniert“-Momente.

Warum das wichtig ist: Das Quantenfeuer

Das Paper beschränkt sich nicht nur darauf, kleinere Rucksäcke zu bauen. Sie zeigen, dass ihre effizienten Signaturen verwendet werden können, um etwas zu bauen, das man „Quantenfeuer“ nennt. Stellen Sie sich vor, Sie haben ein digitales Dokument, das Sie mit einem Freund teilen möchten, aber Sie wollen sicherstellen, dass das Dokument, sobald er es gelesen hat, sofort und dauerhaft zerstört wird und niemand jemals eine Kopie davon anfertigen kann. Dies ist das Konzept des „Quantenfeuers“.

Frühere Versuche, dieses Feuer zu bauen, stützten sich auf die alten, klobigen Signaturen. Die Autoren weisen darauf hin, dass die alte Methode einen fatalen Fehler hatte: Sie war nicht „inkompressibel“. Einfach ausgedrückt: Ein Hacker konnte die alten, sperrigen Signaturen nehmen und sie in eine winzige, komprimierte Datei pressen, die immer noch genug Informationen enthielt, um später neue Signaturen zu fälschen. Es war wie ein Feuer, das man löschen und wieder entfachen konnte.

Das neue Schema behebt dies. Da ihre Signaturen anders strukturiert sind, sind sie „inkompressibel“. Man kann sie nicht verkleinern, ohne die Fähigkeit zu verlieren, sie zu verifizieren. Das bedeutet, dass das „Quantenfeuer“, das sie bauen, echt und zuverlässig ist. Sob wenn das digitale Geheimnis verbrannt ist, bleibt es verbrannt. Sie nutzen dies auch, um einen Fehler in einem aktuellen Paper von Çakan, Goyal und Shmueli zu beheben, und stellen so die Fähigkeit wieder her, diese sicheren, unkopierbaren digitalen Geheimnisse zu erschaffen.

Das Fazit

Die Autoren haben bewiesen, dass es möglich ist, ein One-Shot-Signatur-Schema zu erstellen, das:

Effizient ist: Es nutzt signifikant weniger Quantenspeicher ( $\Theta(\lambda^2)$ Qubits) und erzeugt kleinere Signaturen ( $\Theta(\lambda^2)$ Bits) im Vergleich zum bisherigen Bestwert ( $\Theta(\lambda^4)$ und $\Theta(\lambda^3)$ ).
Einfach ist: Es vermeidet die komplexen, mehrstufigen Quantenschaltkreise, die die alte Methode langsam und schwer verständlich machten.
Perfekt ist: Es funktioniert jedes Mal mit einer Erfolgsgarie von null Fehlerrisiko.
Sicher ist: Es verhindert, dass Hacker die Daten komprimieren können, um das System zu überlisten, was die Erstellung von „Quantenfeuer“ und anderen fortschrittlichen Sicherheitswerkzeugen ermöglicht.

Obwohl das Paper anmerkt, dass es noch Raum für Verbesserungen gibt (vielleicht um die Schlüssel in Zukunft noch kleiner zu machen), haben sie erfolgreich die Messlatte verschoben – von „theoretisch möglich, aber unpraktisch“ hin zu „effizient und bereit für die nächste Generation der Quantensicherheit“. Sie haben einen klobigen, selbstzerstörenden Backstein in eine elegante, selbstzerstörende Feder verwandelt.

Technisches Resümee: Ein einfaches und effizientes One-Shot-Signaturverfahren

Problemstellung

One-Shot-Signaturen (OSS) sind ein einzigartiges quantenkryptographisches Primitiv, das es einem Benutzer ermöglicht, einen öffentlichen Verifizierungsschlüssel ($pk$) und einen geheimen Quanten-Signaturzustand ( $|sk\rangle$ ) zu generieren. Der Signaturzustand ermöglicht die Erzeugung einer gültigen Signatur für genau eine Nachricht der Wahl des Benutzers; nach der Signatur „selbstzerstört“ sich der Zustand, was die Erzeugung einer zweiten Signatur verhindert. Während OSS leistungsfähige Primitive wie Quantum Money, Quantum Lightning und Quantum Fire impliziert, blieb die effiziente Konstruktion dieser Konzepte eine Herausforderung.

Der jüngste Durchbruch durch Shmueli und Zhandry (SZ) [SZ25] lieferte die erste Konstruktion von OSS. Jedoch leidet ihr Schema unter erheblichen Ineffizienzen:

Bitweise Signatur: Die SZ-Konstruktion signiert Nachrichten inhärent Bit für Bit. Um eine $\lambda$ -Bit-Nachricht zu signieren, erfordert das Schema eine parallele Repetition, was zu einem linearen Blowup in der Schlüssel- und Signaturgröße führt.
Komplexe Verstärkung: Um starke Sicherheit zu erreichen, greift SZ auf die Reduktion von Dall'Agnol und Spooner (DS) [DS22] zurück, die komplexe Quanten-Rewinding oder Quantum Singular Value Transform (QSVT)-Schaltkreise (speziell Alternating Projections oder Marriott-Watrous-artige Algorithmen) verwendet. Dies führt zu einem zusätzlichen Overhead von $\Theta(\lambda)$ in der Größe des Signatur-Schlüssels.
Unvollkommene Korrektheit: Das SZ-Schema weist einen vernachlässigbaren Korrektheitsfehler auf, was bedeutet, dass der Signaturalgorithmus fehlschlagen kann, eine gültige Signatur zu erzeugen.
Ressourcenkosten: Im Oracle-Modell führt das SZ-Schema zu Signatur-Schlüsseln der Größe $\Theta(\lambda^4)$ Qubits und Signaturen der Größe $\Theta(\lambda^3)$ Bits. Im Plain-Modell sind diese Parameter sogar noch größer.

Darüber hinaus versuchte eine nachfolgende Arbeit von Çakan, Goyal und Shmueli (CGS) [C¸GS25], OSS zu verwenden, um „Public-Key Quantum Fire“ zu konstruieren, stützte sich jedoch auf eine Inkompressibilitätseigenschaft, die das SZ-Schema nicht erfüllt.

Methodik

Diese Arbeit schlägt eine neue, direkte Konstruktion von One-Shot-Signaturen vor, die die komplexen Reduktionen und parallelen Repetitionen vermeidet, die in früheren Ansätzen erforderlich waren. Die Kernmethodik liegt in einem grundlegenden Wechsel in der Art und Weise, wie die Signatur generiert wird:

1. Direkte Konstruktion via Grover-Suche

Anstatt dem SZ-Ansatz zu folgen, der nach einem Präimage einer Hashfunktion sucht, die mit einem spezifischen Bit beginnt (was eine komplexe Verstärkung erfordert, um das „Sum-Binding“-Problem zu handhaben), sucht diese Arbeit nach einer Signatur im Image einer Funktion.

Das Setup: Das Schema nutzt eine Zufallspermutation $\Pi$ und eine Familie von Unterräumen, die durch Matrizen $\mathbf{A}_y$ und Vektoren $\mathbf{b}_y$ definiert sind. Der Signaturzustand $|sk\rangle$ ist eine Gleichverteilung über einen affinen Unterraum (Kosinus), der durch diese Parameter definiert ist.
Der Signaturprozess: Um ein Bit $b$ zu signieren, sucht der Algorithmus nicht nach einem Präimage, das mit $b$ beginnt. Stattdessen verwendet er einen Grover-Suchalgorithmus, um den initialen Superpositionszustand in einen Zustand zu transformieren, in dem die Kosinus-Vektoren ein spezifisches Präfix $b$ im Image unter einer Hilfsfunktion $\mathcal{P}$ besitzen.
Oracle-Nutzung: Der Signaturalgorithmus wendet iterativ zwei Reflexions-Oracles an:
1. Ein Phasen-Oracle, das Zustände markiert, in denen das Image-Präfix mit dem Nachrichtenbit übereinstimmt.
2. Ein duales Oracle $\mathcal{D}$ , das über das Dual des Unterraums reflektiert.
  Durch die Iteration dieses Prozesses $\ell$ -mal (wobei $\ell$ die Nachrichtenlänge ist), rotiert der Algorithmus den Zustand in eine Superposition gültiger Signaturen für die gesamte Nachricht. Das Messen dieses Zustands liefert eine gültige Signatur.

2. Gewährleistung perfekter Korrektheit

Die Autoren adressieren das Problem der unvollkommenen Korrektheit durch eine sorgfältige Gestaltung der Abtastung der Matrix $\mathbf{A}_y$ . Sie stellen sicher, dass die erste Spalte von $\mathbf{A}_y$ nicht Null ist, was garantiert, dass der Kosinus für jeden öffentlichen Schlüssel $y$ Vektoren enthält, die mit sowohl 0 als auch 1 beginnen. Diese strukturelle Garantie stellt sicher, dass die Grover-Suche immer erfolgreich ist, wodurch perfekte Korrektheit (Wahrscheinlichkeit 1) erreicht wird.

3. Handhabung von Nachrichten polynomieller Länge

Anstatt das Einzelbit-Schema $\lambda$ -mal zu wiederholen (was den $\lambda$ -Blowup verursacht), signiert das Schema die gesamte $\lambda$ -Bit-Nachricht in einem einzigen Schritt. Die Grover-Suche wird angepasst, um die gesamte Nachricht in einem einzigen Durchlauf bitweise zu signieren, wodurch die $\lambda$ Signaturen in eine einzige Signatur der Größe $\Theta(\lambda^2)$ komprimiert werden. Für beliebige polynomielle Längen wird eine Standard-Hash-and-Sign-Transformation angewendet.

4. Inkompressibilität und Quantum Fire

Das Paper identifiziert einen Fehler in der Behauptung von CGS [C¸GS25], dass das SZ-Schema eine „starke Signatur-Inkompressibilität“ besitzt. Das SZ-Schema erfüllt diese Eigenschaft nicht, da der Signaturalgorithmus Zugriff auf sowohl das Vorwärts- als auch das Inverse-Oracle ( $\mathcal{P}$ und $\mathcal{P}^{-1}$ ) benötigt, was es einem Angreifer ermöglicht, Signaturen für Schlüssel außerhalb einer komprimierten Liste zu generieren.
Die neue Konstruktion modifiziert das Schema so, dass die Signatur nur das duale Oracle $\mathcal{D}$ erfordert, während die Verifizierung ein separates Oracle $\mathcal{D}_0$ nutzt. Diese Trennung ermöglicht den Beweis der starken Signatur-Inkompressibilität und stellt somit die Gültigkeit der in CGS vorgeschlagenen Anwendungen für Quantum Fire wieder her.

Wichtigste Beiträge und Ergebnisse

Effizienzverbesserungen

Das Paper erzielt signifikante Reduktionen der Ressourcenkomplexität im Vergleich zur SZ-Konstruktion:

Größe des Signatur-Schlüssels: Reduziert von $\Theta(\lambda^4)$ Qubits auf $\Theta(\lambda^2)$ Qubits.
Signaturgröße: Reduziert von $\Theta(\lambda^3)$ Bits auf $\Theta(\lambda^2)$ Bits.
Öffentlicher Schlüssel: Reduziert von $\Theta(\lambda^3)$ Bits (Oracle-Modell) und $\Theta(\lambda^5)$ Bits (Plain-Modell) auf $\Theta(\lambda^2)$ Bits (Oracle-Modell) und $\Theta(\lambda^4)$ Bits (Plain-Modell).
Laufzeit: Der Signaturalgorithmus erfordert deutlich weniger Oracle-Abfragen und vermeidet den $\Theta(\lambda)$ -Overhead, der mit QSVT/Rewinding-Schaltkreisen verbunden ist.

Sicherheit und Korrektheit

Perfekte Korrektheit: Im Gegensatz zu SZ garantiert das neue Schema, dass eine gültige Signatur mit Wahrscheinlichkeit 1 erzeugt wird.
Starke Sicherheit: Das Schema erreicht starke Unforgeability, was bedeutet, dass es unmöglich ist, eine gültige Signatur für eine andere Nachricht oder eine andere Signatur für dieselbe Nachricht zu erzeugen.
Inkompressibilität: Das Schema erfüllt die starke Signatur-Inkompressibilität, eine Eigenschaft, die für fortgeschrittene Anwendungen wie Quantum Fire erforderlich ist.

Theoretische Ergebnisse

Das Paper formalisiert diese Verbesserungen in zwei Haupttheoremen:

Theorem 1.1: Belegt die Existenz effizienter OSS-Schemata für polynomielle Nachrichtenlängen mit perfekter Korrektheit sowohl im klassischen Oracle-Modell (unbedingt) als auch im Plain-Modell (unter Annahme von Post-Quantum Indistinguishability Obfuscation und LWE).
Theorem 1.2: Zeigt, dass das neue inkompressible OSS-Schema die Konstruktion von Public-Key Quantum Fire und Key-Fire Schemata mit perfekter Korrektheit ermöglicht und damit die Fehler in der Arbeit von CGS [C¸GS25] korrigiert.

Bedeutung

Das Paper beansprucht, eine „einfache, direkte und effiziente“ Alternative zu den aktuellen State-of-the-Art One-Shot-Signaturverfahren zu liefern. Durch die Umgehung der komplexen Reduktionen (DS [DS22]) und der parallelen Repetitionsstrategien der vorangegangenen Arbeiten erzielen die Autoren eine quadratische Verbesserung der Schlüssel- und Signaturgrößen.

Die Bedeutung dieser Arbeit ist zweifach:

Praktische Effizienz: Sie macht Quantensignatur-Schemata wesentlich praktikabler, indem sie die Qubit- und Bit-Anforderungen von quartischen/kubischen auf quadratische Skalen reduziert.
Fundamentale Korrektur: Sie behebt eine kritische Lücke in der Literatur bezüglich der Inkompressibilität von OSS. Durch die Behebung der Inkompressibilitätseigenschaft validiert und ermöglicht das Paper die Konstruktion von „Quantum Fire“ und verwandten Primitiven, die zuvor als möglich behauptet, aber auf einer fehlerhaften Annahme über das SZ-Schema basierend waren.

Die Autoren merken an, dass sie zwar die Parameter signifikant optimiert haben, weitere Verbesserungen auf $\Theta(\lambda)$ im Oracle-Modell jedoch völlig neue Techniken erfordern könnten, da der aktuelle Engpass in der Analyse des dual-freien Falls liegt. Ähnlich bleibt die Verbesserung der Parameter im Plain-Modell ein offenes Problem.