Lattice-based extended withdrawability

Technische Zusammenfassung: Lattice-basierte erweiterte Rückziehbarkeit (Extended Withdrawability)

Problemstellung
Digitale Signaturen bieten traditionell Permanenz: Einmal signiert, bleibt eine Nachricht unter dem öffentlichen Schlüssel des Signers unbegrenzt verifizierbar. Viele dezentrale Anwendungen (z. B. zeitlich begrenzte Zugriffe, widerrufbare Vereinbarungen, dezentrales Escrow) erfordern jedoch die Möglichkeit, eine Signatur zurückzuziehen, ohne den geheimen Schlüssel zu enthüllen oder andere Signaturen zu invalidieren. Liu, Susilo und Baek führten erweiterte rückziehbare Signaturen (Extended Withdrawable Signatures, EWS) ein, um dies zu adressieren. Diese ermöglichen es, dass eine Signatur unter einer Menge potenzieller Signierer bis zur „Bestätigung“ durch den wahren Signierer mehrdeutig bleibt. Ihre Konstruktion basiert auf Diskret-Logarithmus-Primitiven (Schnorr-Signaturen und 1-aus-N-Signaturen).

Diese Arbeit adressiert die „Post-Quanten-Lücke“: Shors Algorithmus bricht die auf dem Diskreten-Logarithmus basierende Grundlage bestehender EWS-Schemata. Obwohl lattice-basierte Signaturen (z. B. Dilithium) existieren, scheitert eine direkte „wortgetreue Transkription“ der Liu-Susilo-Baek-Konstruktion (LSB) auf Gittern (Lattices) aufgrund struktureller Hindernisse. Speziell beruht das LSB-Schema darauf, multiplikative Verschiebungen der öffentlichen Schlüssel zu veröffentlichen, um den Beitrag des Signierers zu re-randomisieren. Im Gitter-Kontext (Fiat-Shamir mit Abbrüchen) nehmen solche Verschiebungen die Form $As_1 s_j$ an, die einen gemeinsamen Faktor $As_1$ mit dem öffentlichen Schlüssel des Signierers $t_i = As_1 + s_2$ teilen. Das Veröffentlichen dieser Verschiebungen führt zum Leak der Identität des Signierers, was die erforderliche Mehrdeutigkeit verletzt.

Methodik
Die Autoren schlagen eine neue Konstruktion für lattice-basierte EWS vor, die vom LSB-Ansatz abweicht, indem sie das Schema als beanspruchbare Ringsignatur (Claimable Ring Signature, nach Park und Sealfon) behandelt. Anstatt zu versuchen, öffentliche Schlüssel im Klartext zu re-randomisieren, trennt die Konstruktion die zwei Kernfunktionen von EWS:

1. Mehrdeutigkeit (Ambiguity): Wird durch eine anonyme 1-aus-N-Signatur (Ring-Signatur) bereitgestellt, die als Blackbox verwendet wird.
2. Bestätigung (Confirmation): Wird durch den Anspruch (Claim) des Signers bereitgestellt, welcher aus einer bindenden Signatur auf das rückziehbare Objekt und der Eröffnung einer verborgenen Bindung (Hiding Commitment) an den Index des Signers besteht.

Die Konstruktion operiert über das Fiat-Shamir-mit-Abbrüchen-Paradigma und stützt sich auf drei modulare Bestandteile:

• Ein Basissignatur-Schema (z. B. ein No-Hint, Full-$t$ Dilithium-artiges Schema).
• Eine anonyme 1-aus-N-Signatur (instanziiert via eines Lattice One-out-of-Many-Beweises).
• Ein Verborgheits- und Bindungs-Commitment-Schema (Ajtai-Stil).

Die rückziehbare Signatur $\sigma$ besteht aus einer Ringsignatur $\sigma_r$ auf die Nachricht und einem Commitment $C$ auf den Index des Signers sowie der Menge der öffentlichen Schlüssel. Zur Bestätigung offenbart der Signierer die Eröffnung $(i, \rho)$ von $C$ und signiert das gesamte rückziehbare Objekt $\langle \mu, \pi, \sigma \rangle$ mit seinem Basisschlüssel.

Wesentliche Beiträge

1. Verfeinerung des Sicherheitsmodells: Die Autoren verfeinern das Sicherheitsmodell von LSB.

   • Sie ersetzen die LSB-Definition der „Vollständigkeit“ (Completeness) der erweiterten Rückziehbarkeit durch ein Ununterscheidbarkeitsspiel der „Anonymität bis zum Anspruch“ (Definition 14), welches die Verborgeneit explizit erfasst.
   • Sie führen die „Beanspruchungs-Soundness“ (Claimability Soundness, Definition 16) ein, die sicherstellt, dass eine bestätigte Signatur an einen eindeutigen Signierer-Index bindet, um zu verhindern, dass ein Angreifer dieselbe Signatur verschiedenen Ringmitgliedern zuordnet.
   • Sie formalisieren die „Unfälschbarkeit unter Insider-Korruption“ mit einem festen Zielindex, wodurch der Verlust durch die multiplikative $q_H$ (Hash-Query)-Reduktion in der LSB-Bewertung vermieden wird.

2. Generische Konstruktion: Es wird eine generische Konstruktion von EWS über das Fiat-Shamir-mit-Abbrüchen-Paradigma präsentiert. Entscheidend ist, dass kein vom Signierer abgeleiteter Wert im Klartext veröffentlicht wird. Die Mehrdeutigkeit ergibt sich ausschließlich aus den Zero-Knowledge-Eigenschaften der Ringsignatur, und die Rückverfolgbarkeit aus der Bindungseigenschaft des Commitments.

3. Unmöglichkeitsresultat: Das Paper beweist (Proposition 2), dass eine wörtliche Gitter-Transkription der LSB 1-aus-N-Signatur (unter Verwendung von additiver Challenge-Aufteilung) unsicher ist. Im Gitter-Kontext mit spärlichen Challenges (Sparse Challenges) ist die Wahrscheinlichkeit, dass ein ehrlicher Signierer eine gültige Challenge-Aufteilung produziert, vernachlässigbar klein ($2^{-\Omega(n)}$), und selbst wenn die Vollständigkeit behoben würde, würde die Anonymität scheitern, da der simulierte Transkript nicht ununterscheidbar von einem realen wäre.

4. Vollständige Sicherheitsbeweise: Die Autoren liefern explizite spielbasierte Reduktionen im (Quanten-)Random-Oracle-Modell (QROM) für:

   • Korrektheit: Reduktion auf die Korrektheit der zugrunde liegenden Primitiven.
   • Erweiterte Rückziehbarkeit: Reduktion auf die Verborgeneit des Commitments (Decisional MLWE) und die Anonymität des 1-aus-N-Schemas.
   • Unfälschbarkeit: Reduktion auf die EUF-CMA-Sicherheit der Basissignatur (ohne Rewinding und ohne $q_H$-Verlust).
   • Beanspruchungs-Soundness: Reduktion auf die Bindung des Commitments (MSIS).

5. Instanziierung: Das Schema wird unter Verwendung einer No-Hint, Full-$t$ Dilithium-artigen Basissignatur und eines etablierten Lattice One-out-of-Many-Beweises instanziiert. Das Paper diskutiert Parameterwahlmöglichkeiten und merkt an, dass HAETAE als alternative Basis dienen könnte.

Ergebnisse
Das Paper stellt fest, dass die vorgeschlagene Konstruktion:

• Korrekt ist: Ehrliche Signaturen verifizieren mit überwältigender Wahrscheinlichkeit.
• Erweitert rückziehbar ist: Ein Angreifer, der alle geheimen Schlüssel besitzt, kann nicht unterscheiden, welches Mitglied eines Rings eine rückziehbare Signatur erstellt hat, bis der Signierer sie bestätigt.
• Unfälschbar ist: Selbst mit Zugriff auf Signier-Oracles und den geheimen Schlüsseln aller Ringmitglieder außer dem Zielmitglied kann ein Angreifer keine bestätigte Signatur für eine neue Nachricht fälschen.
• Sound ist: Eine bestätigte Signatur kann nicht zwei verschiedenen Signierern zugeordnet werden.

Die Sicherheit beruht auf Standard-Modul-Gitter-Annahmen: Decisional MLWE, MSIS und SelfTargetMSIS sowie der Zero-Knowledge-Eigenschaft des 1-aus-N-Beweises.

Bedeutung
Das Paper beansprucht seine Bedeutung durch die Bereitstellung der ersten sicheren, Post-Quanten-Realisierung erweiterter rückziehbarer Signaturen. Es zeigt auf, dass die auf dem Diskreten-Logarithmus basierende Konstruktion von LSB aufgrund des Fehlens einer „freien Re-Randomisierung“ gemeinsamer Werte nicht direkt auf Gitter übertragen werden kann. Durch die Umformulierung des Problems als beanspruchbare Ringsignatur und die Nutzung eines Commitment-basierten Bestätigungsmechanismus erreichen die Autoren ein Schema, das:

• Post-Quanten-Sicher ist: Resistent gegen Quantenangreifer durch Gitter-Annahmen.
• Öffentlich verifizierbar ist: Im Gegensatz zu Designated-Verifier-Varianten kann jede Partei die rückziehbare Signatur verifizieren.
• Modular ist: Die Sicherheitsbeweise beruhen nur auf den Schnittstellen der zugrunde liegenden Primitiven, was den Austausch verschiedener lattice-basierter Komponenten (z. B. unterschiedliche Basissignaturen oder Ring-Beweise) ermöglicht, ohne das gesamte System neu beweisen zu müssen.
• Den ursprünglichen Zielen treu bleibt: Das Design bewahrt die funktionalen Ziele und die Intuition des ursprünglichen LSB-Schemas, korrigiert jedoch dessen strukturelle Mängel im Gitter-Kontext.