MPCitH-basierte Signaturen aus eingeschränkten Decodierungsproblemen

Grundlegende Informationen

• Paper-ID: 2510.11224
• Titel: MPCitH-based Signatures from Restricted Decoding Problems
• Autoren: Michele Battagliola (Polytechnische Universität Marche), Sebastian Bitzer, Antonia Wachter-Zeh, Violetta Weger (Technische Universität München)
• Klassifizierung: cs.CR (Kryptographie und Sicherheit), cs.IT (Informationstheorie), math.IT (Informationstheorie)
• Veröffentlichungsdatum: 13. Oktober 2025 (arXiv-Preprint)
• Paper-Link: https://arxiv.org/abs/2510.11224

Zusammenfassung

In diesem Artikel werden eingeschränkte Decodierungsprobleme (E-SDP) in die Frameworks Threshold-Computation-in-the-Head (TCitH) und VOLE-in-the-Head (VOLEitH) eingebettet, die neueste Entwicklungen des MPC-in-the-Head (MPCitH)-Paradigmas darstellen und die Leistung digitaler Signaturschemata erheblich verbessern. Die Autoren schlagen eine strukturell einfache Modellierungsmethode vor, die wettbewerbsfähige Signaturgrößen erreicht. Durch die Instanziierung des eingeschränkten Decodierungsproblems mit denselben Schwierigkeitsannahmen wie CROSS wird die Signaturgrößen um mehr als das Zweifache im Vergleich zur NIST-Einreichungsversion reduziert. Darüber hinaus stellen die Autoren fest, dass ternäres Vollgewichtsdecodieren eng mit den zugrunde liegenden Schwierigkeitsannahmen von WAVE zusammenhängt, und die mit dieser Methode erzielten Signaturgrößen sind mit den kleinsten MPCitH-Kandidaten im NIST-Wettbewerb vergleichbar.

Forschungshintergrund und Motivation

Problemhintergrund

1. Standardisierungsbedarf für Post-Quanten-Kryptographie: Nach der Standardisierung von CRYSTALS-Dilithium, FALCON und SPHINCS+ startete NIST im September 2022 eine Ausschreibung für zusätzliche digitale Signaturschemata, um die Vielfalt der Post-Quanten-Signaturstandardsammlung zu erhöhen.
2. Entwicklung des MPCitH-Paradigmas: Seit der Einführung durch Ishai et al. im Jahr 2007 hat die MPCitH-Technologie die Landschaft der Post-Quanten-Digitalsignaturen umgestaltet. TCitH und VOLEitH als neueste Spezialisierungen von MPCitH bieten erhebliche Leistungsverbesserungen gegenüber früheren Konstruktionen.
3. Anwendung der Kodierungstheorie in der Kryptographie: Schwierigkeitsprobleme basierend auf Kodierungstheorie (wie Hamming-Metrik- und Rang-Metrik-Decodierungsprobleme) bieten eine theoretische Grundlage für die Konstruktion effizienter Post-Quanten-Signaturen.

Forschungsmotivation

1. Optimierungsbedarf bei der Leistung: Das bestehende CROSS-Signaturschemata, obwohl basierend auf eingeschränkten Decodierungsproblemen, verwendet das relativ einfache CVE-Protokoll und hat Optimierungspotenzial bei der Signaturgrößen.
2. Framework-Vereinheitlichung: Vereinheitlichung eingeschränkter Decodierungsprobleme in fortgeschrittene TCitH/VOLEitH-Frameworks, um die Leistungsvorteile dieser Frameworks vollständig zu nutzen.
3. Verbesserung der Wettbewerbsfähigkeit: Signifikante Reduzierung der Signaturgrößen bei Beibehaltung der Sicherheit, um die Wettbewerbsfähigkeit im NIST-Wettbewerb zu erhöhen.

Kernbeiträge

1. Polynomiale Modellierungsmethode für E-SDP vorgeschlagen: Entwurf einer strukturell einfachen, aber effektiven polynomialen Beziehung, die das eingeschränkte Syndrom-Decodierungsproblem in TCitH- und VOLEitH-Frameworks einbettet.
2. Signifikante Reduzierung der Signaturgrößen von CROSS-Typ-Signaturen: Für dasselbe Decodierungsproblem wird die Signaturgrößen um mehr als 50% im Vergleich zum NIST-eingereichten CROSS-Schema reduziert (von 12,4 kB auf 5,5 kB).
3. Anwendungspotenzial des ternären Vollgewichtsdecodierens entdeckt: Nachweis, dass das mit WAVE verbundene ternäre Vollgewichtsdecodieren ein eingeschränktes Decodierungsproblem ist, und Realisierung von Signaturgrößen, die mit den kleinsten MPCitH-Kandidaten vergleichbar sind (3,1 kB).
4. Vollständiges parametrisiertes Schema bereitgestellt: Konkrete Parameterauswahl und Leistungsanalyse für NIST-Sicherheitskategorien 1, 3, 5.

Methodische Details

Aufgabendefinition

Das Forschungsziel besteht darin, das eingeschränkte Syndrom-Decodierungsproblem (E-SDP) als polynomiale Beziehung darzustellen, damit es digitale Signaturschemata in TCitH- und VOLEitH-Frameworks konstruieren kann.

E-SDP-Definition: Gegeben eine Beschränkungsmenge E ⊂ F, eine Paritätsprüfmatrix H ∈ F^(r×n) und ein Syndrom s ∈ F^r, finde e ∈ E^n so dass eH^T = s.

Kernmodellierungsmethode

1. Polynomiale Beschränkungskonstruktion

Für eine Paritätsprüfmatrix in Systemform H = (A, I_r), wobei A ∈ F^(r×k), I_r die Einheitsmatrix:

• Zeugvektor: w ∈ F^k (partieller Fehlervektor)
• Erweiterter Fehlervektor: e = (w, s - wA^T)
• Beschränkungspolynom: f_E(x) = ∏_{e∈E}(x - e)

Polynomiales Beziehungssystem:

F(x) = (f_1, ..., f_n) ∈ F[x_1, ..., x_k]^n

wobei:

• f_i(x) = f_E(x_i) für i ∈ k
• f_{k+i}(x) = f_E(s_i - ⟨a_i, x⟩) für i ∈ r

2. Gradanalyse

Proposition 1: Diese polynomiale Beziehung bietet eine Modellierung von E-SDP mit Grad z = |E|. Wenn w ∈ F^k F(w) = 0 erfüllt, dann löst der Fehlervektor e = (w, s - wA^T) die E-SDP-Instanz (H, s).

Konkrete Instanziierungen

CROSS-SDP

• Beschränkungsmenge: E = {2^i | i ∈ 7} ⊆ F_{127}
• Parameter: |E| = 7, p = 127
• Sicherheit: Basierend auf detaillierter Analyse 7,15

Ternary-SDP

• Beschränkungsmenge: E = {1, 2} ⊆ F_3
• Parameter: |E| = 2, p = 3
• Komplexität: O(2^{0.247·n}) Operationen (innerhalb polynomialer Faktoren)

Experimentelle Einrichtung

Parameterwahl-Strategie

Basierend auf Sicherheitsanforderungen und Leistungsoptimierungszielen werden folgende Schlüsselparameter ausgewählt:

1. TCitH-Framework-Parameter:
   • τ: Anzahl paralleler Wiederholungen
   • N: Evaluierungsbereichsgröße
   • μ: Erweiterungskörpergrad K : F
   • η: Batch-Parameter
2. VOLEitH-Framework-Parameter:
   • ρ: Erweiterungskörper-Parameter
   • B: Konsistenzprüfungsparameter
   • T_open: VC-Schema-Parameter

Sicherheitseinschränkungen

Erfüllung folgender Sicherheitsanforderungen:

• TCitH: N ≤ p^μ, p^{μ·η} ≥ 2^λ, (N/d)^τ ≥ 2^{λ-w}
• VOLEitH: N^τ/d ≥ 2^{λ-w}, p^ρ ≥ 2^λ

Bewertungsindikatoren

Hauptsächlich Bewertung der Signaturgrößen, bestehend aus drei Komponenten:

• |σ_sym|: VC-Schema-bezogen
• |σ_w|: Zeug-bezogen
• |σ_F|: OWF-bezogen

Experimentelle Ergebnisse

Hauptergebnisse

TCitH-Framework-Leistung

| Sicherheitsstufe | E-SDP-Typ | |F| | |E| | n | k | τ | N | μ | η | Signaturgrößen(B) | |---------|-----------|-----|-----|---|---|---|---|---|---|-----------| | NIST 1 | CROSS-SDP | 127 | 7 |127| 76| 15|2048| 2| 10| 5.533 | | NIST 1 | Ternary-SDP| 3 | 2 |579|213| 12|2048| 7| 12| 3.095 | | NIST 3 | CROSS-SDP | 127 | 7 |187|111| 23|2048| 2| 14| 12.354 | | NIST 3 | Ternary-SDP| 3 | 2 |839|309| 18|2048| 7| 18| 6.860 |

VOLEitH-Framework-Leistung

Vergleich mit NIST-Kandidatenschemata

Wichtige Erkenntnisse

1. Signifikante Größenreduktion: CROSS-SDP reduziert die Signaturgrößen um 64,5% im Vergleich zum ursprünglichen CROSS
2. Auswirkungen der Framework-Auswahl: Für hochgradige Probleme ist VOLEitH vorteilhafter als TCitH
3. Wettbewerbsfähigkeit: Ternary-SDP erreicht eine Leistung, die mit den besten MPCitH-Kandidaten vergleichbar ist

Verwandte Arbeiten

Entwicklung des MPCitH-Paradigmas

1. Ursprüngliches MPCitH 23: 2007 vorgeschlagen, kombiniert sichere Mehrparteienberechnung mit Fiat-Shamir-Transformation
2. TCitH-Framework 21: Instanziierung mit ℓ-aus-n-Schwellenwert-Geheimnisfreigabe
3. VOLEitH-Framework 13: Kompilierung von VOLE-basierten Nullwissensprotokollen zu öffentlich verifizierbaren Protokollen

Anwendungen der Kodierungstheorie

1. Hamming-Metrik-Decodieren: Grundlage von Schemata wie SDitH
2. Rang-Metrik-Decodieren: Schemata wie RYDE, Mirath
3. Permutationskern-Problem: Schwierigkeitsannahme des PERK-Schemas

Eingeschränkte Decodierungsprobleme

1. CROSS-Schema 6: Eingeschränktes Decodieren mit einfachem CVE-Protokoll
2. WAVE-Schema 10,19: Basierend auf ternärem hochgewichtigem Syndrom-Decodieren
3. Theoretische Analyse 8,9: NP-Vollständigkeit und konkrete Schwierigkeit von E-SDP

Schlussfolgerung und Diskussion

Hauptschlussfolgerungen

1. Erfolgreiche Framework-Integration: Nachweis, dass eingeschränkte Decodierungsprobleme effektiv in fortgeschrittene MPCitH-Frameworks integriert werden können
2. Signifikante Leistungsverbesserung: Durch Ersatz des einfachen CVE-Protokolls durch TCitH/VOLEitH wird die Signaturgrößen erheblich reduziert
3. Breite Anwendbarkeit: Die Methode ist auf verschiedene Arten von eingeschränkten Decodierungsproblemen anwendbar

Einschränkungen

1. Erhöhte Komplexität: Im Vergleich zum einfachen CVE-Protokoll des ursprünglichen CROSS ist die TCitH/VOLEitH-Konstruktion erheblich komplexer
2. Rechnerischer Overhead: Obwohl die Signaturgrößen reduziert werden, kann dies den Rechneraufwand für Signaturerstellung und -verifikation erhöhen
3. Parameterabhängigkeit: Die Leistung hängt stark von der konkreten Parameterauswahl und Optimierungsstrategie ab

Zukünftige Richtungen

1. Weitere Optimierung: Erforschung effizienterer polynomialer Modellierungsmethoden
2. Andere eingeschränkte Probleme: Erweiterung der Methode auf andere Arten von eingeschränkten Decodierungsproblemen
3. Implementierungsoptimierung: Entwicklung effizienter Implementierungen zur Reduzierung des Rechneraufwands

Tiefgreifende Bewertung

Stärken

1. Technische Innovation: Vorschlag einer prägnanten und effektiven polynomialen Modellierungsmethode für eingeschränkte Decodierungsprobleme
2. Signifikante Verbesserung: Erhebliche Reduzierung der Signaturgrößen bei Beibehaltung derselben Sicherheit
3. Theoretischer Beitrag: Aufbau einer Brücke zwischen eingeschränkten Decodierungsproblemen und fortgeschrittenen MPCitH-Frameworks
4. Praktischer Wert: Bereitstellung neuer Designideen für Post-Quanten-Signaturschemata

Mängel

1. Komplexitäts-Kompromiss: Austausch von Konstruktionskomplexität gegen Reduzierung der Signaturgrößen
2. Begrenzte Neuheit: Hauptsächlich geschickte Kombination bestehender Techniken mit relativ begrenzter theoretischer Innovation
3. Fehlende Implementierungsdetails: Mangel an detaillierter Leistungsanalyse und Vergleich tatsächlicher Implementierungen

Einfluss

1. Akademischer Wert: Bereitstellung neuer Fallstudien für die Anwendung des MPCitH-Frameworks
2. Praktische Bedeutung: Kann den Schemaauswahl-Prozess in zukünftigen NIST-Standardisierungsverfahren beeinflussen
3. Methodologischer Beitrag: Bereitstellung von Referenzen für ähnliche Modellierungen anderer Schwierigkeitsprobleme

Anwendungsszenarien

1. Ressourcenbegrenzte Umgebungen: Anwendungsszenarien, in denen Signaturgrößen kritisch sind
2. Post-Quanten-Kryptographie-Bereitstellung: Systeme, die vielfältige Sicherheitsannahmen benötigen
3. Forschungsprototypen: Als Grundlage für weitere Optimierung und Verbesserung

Referenzen

Das Paper zitiert 24 wichtige Referenzen, die die Entwicklung des MPCitH-Frameworks, Anwendungen der Kodierungstheorie und verwandte NIST-Kandidatenschemata abdecken und eine solide theoretische Grundlage für die Forschung bieten.