Firme Basate su MPCitH da Problemi di Decodifica Ristretti

Informazioni Fondamentali

• ID Articolo: 2510.11224
• Titolo: MPCitH-based Signatures from Restricted Decoding Problems
• Autori: Michele Battagliola (Università Politecnica delle Marche), Sebastian Bitzer, Antonia Wachter-Zeh, Violetta Weger (Università Tecnica di Monaco)
• Classificazione: cs.CR (Crittografia e Sicurezza), cs.IT (Teoria dell'Informazione), math.IT (Teoria dell'Informazione)
• Data di Pubblicazione: 13 ottobre 2025 (preprint arXiv)
• Link Articolo: https://arxiv.org/abs/2510.11224

Riassunto

Questo articolo integra il problema di decodifica ristretta (E-SDP) nei framework Threshold-Computation-in-the-Head (TCitH) e VOLE-in-the-Head (VOLEitH), rappresentando gli sviluppi più recenti del paradigma MPC-in-the-Head (MPCitH), migliorando significativamente le prestazioni degli schemi di firma digitale. Gli autori propongono un metodo di modellazione strutturalmente semplice, realizzando dimensioni di firma competitive. Istanziando il problema di decodifica ristretta con le stesse assunzioni di difficoltà di CROSS, la dimensione della firma si riduce di oltre il doppio rispetto alla versione sottomessa a NIST. Inoltre, gli autori scoprono che la decodifica ternaria a peso pieno è strettamente correlata all'assunzione di difficoltà sottostante di WAVE, ottenendo dimensioni di firma comparabili ai candidati MPCitH più piccoli della competizione NIST.

Contesto di Ricerca e Motivazione

Contesto del Problema

1. Necessità di Standardizzazione della Crittografia Post-Quantistica: Dopo la standardizzazione di CRYSTALS-Dilithium, FALCON e SPHINCS+, NIST ha lanciato nel settembre 2022 una raccolta di schemi di firma digitale aggiuntivi, mirando a diversificare il portafoglio di standard di firma post-quantistica.
2. Sviluppo del Paradigma MPCitH: Dalla sua introduzione nel 2007 da parte di Ishai e colleghi, la tecnologia MPCitH ha trasformato il panorama della firma digitale post-quantistica. TCitH e VOLEitH, come specializzazioni più recenti di MPCitH, offrono miglioramenti significativi delle prestazioni rispetto alle costruzioni precedenti.
3. Applicazione della Teoria dei Codici in Crittografia: I problemi difficili basati sulla teoria dei codici (come i problemi di decodifica nella metrica di Hamming e nella metrica di rango) forniscono fondamenti teorici per la costruzione di firme post-quantistiche efficienti.

Motivazione della Ricerca

1. Necessità di Ottimizzazione delle Prestazioni: Sebbene lo schema di firma CROSS esistente sia basato su problemi di decodifica ristretta, utilizza il protocollo CVE relativamente semplice, con spazio per l'ottimizzazione nella dimensione della firma.
2. Unificazione del Framework: Integrare il problema di decodifica ristretta nei framework avanzati TCitH/VOLEitH per sfruttare pienamente i vantaggi prestazionali di questi framework.
3. Miglioramento della Competitività: Ridurre significativamente la dimensione della firma mantenendo la sicurezza, aumentando la competitività nella competizione NIST.

Contributi Principali

1. Propone un Metodo di Modellazione Polinomiale per E-SDP: Progetta una relazione polinomiale strutturalmente semplice ma efficace, integrando il problema di decodifica sindrome ristretta nei framework TCitH e VOLEitH.
2. Riduce Significativamente la Dimensione delle Firme di Tipo CROSS: Per lo stesso problema di decodifica, la dimensione della firma si riduce di oltre il 50% rispetto allo schema CROSS sottomesso a NIST (da 12,4 kB a 5,5 kB).
3. Scopre il Potenziale Applicativo della Decodifica Ternaria a Peso Pieno: Dimostra che la decodifica ternaria a peso pieno correlata a WAVE è un problema di decodifica ristretta, realizzando dimensioni di firma comparabili ai candidati MPCitH più piccoli (3,1 kB).
4. Fornisce Schemi di Parametrizzazione Completi: Fornisce scelte di parametri specifiche e analisi delle prestazioni per le categorie di sicurezza NIST 1, 3, 5.

Spiegazione Dettagliata del Metodo

Definizione del Compito

L'obiettivo della ricerca è rappresentare il problema di decodifica sindrome ristretta (E-SDP) come una relazione polinomiale, consentendone l'utilizzo nella costruzione di schemi di firma digitale nei framework TCitH e VOLEitH.

Definizione di E-SDP: Dato un insieme di restrizione E ⊂ F, una matrice di controllo di parità H ∈ F^(r×n) e una sindrome s ∈ F^r, trovare e ∈ E^n tale che eH^T = s.

Metodo di Modellazione Principale

1. Costruzione di Vincoli Polinomiali

Per una matrice di controllo di parità in forma sistematica H = (A, I_r), dove A ∈ F^(r×k), I_r è la matrice identità:

• Vettore di testimone: w ∈ F^k (vettore di errore parziale)
• Vettore di errore esteso: e = (w, s - wA^T)
• Polinomio di restrizione: f_E(x) = ∏_{e∈E}(x - e)

Sistema di Relazioni Polinomiali:

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

dove:

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

2. Analisi del Grado

Proposizione 1: Questa relazione polinomiale fornisce una modellazione di E-SDP con grado z = |E|. Se w ∈ F^k soddisfa F(w) = 0, allora il vettore di errore e = (w, s - wA^T) risolve l'istanza E-SDP (H, s).

Istanziazioni Concrete

CROSS-SDP

• Insieme di restrizione: E = {2^i | i ∈ 7} ⊆ F_{127}
• Parametri: |E| = 7, p = 127
• Sicurezza: Basata su analisi dettagliata 7,15

Ternary-SDP

• Insieme di restrizione: E = {1, 2} ⊆ F_3
• Parametri: |E| = 2, p = 3
• Complessità: O(2^{0.247·n}) operazioni (entro fattori polinomiali)

Configurazione Sperimentale

Strategia di Scelta dei Parametri

In base ai requisiti di sicurezza e agli obiettivi di ottimizzazione delle prestazioni, vengono selezionati i seguenti parametri chiave:

1. Parametri del Framework TCitH:
   • τ: numero di ripetizioni parallele
   • N: dimensione del dominio di valutazione
   • μ: grado di estensione di campo K : F
   • η: parametro di batch processing
2. Parametri del Framework VOLEitH:
   • ρ: parametro di estensione di campo
   • B: parametro di verifica di coerenza
   • T_open: parametri dello schema VC

Vincoli di Sicurezza

Soddisfare i seguenti requisiti di sicurezza:

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

Metriche di Valutazione

La valutazione principale riguarda la dimensione della firma, composta da tre componenti:

• |σ_sym|: correlato allo schema VC
• |σ_w|: correlato al testimone
• |σ_F|: correlato a OWF

Risultati Sperimentali

Risultati Principali

Prestazioni del Framework TCitH

| Livello di Sicurezza | Tipo E-SDP | |F| | |E| | n | k | τ | N | μ | η | Dimensione Firma (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 |

Prestazioni del Framework VOLEitH

Confronto con Candidati NIST

Scoperte Chiave

1. Riduzione Significativa della Dimensione: CROSS-SDP riduce del 64,5% la dimensione della firma rispetto al CROSS originale
2. Impatto della Scelta del Framework: Per problemi ad alto grado, VOLEitH è più vantaggioso di TCitH
3. Competitività: Ternary-SDP raggiunge prestazioni comparabili ai migliori candidati MPCitH

Lavori Correlati

Sviluppo del Paradigma MPCitH

1. MPCitH Originale 23: Proposto nel 2007, combinando il calcolo sicuro multi-parte con la trasformazione di Fiat-Shamir
2. Framework TCitH 21: Istanziazione utilizzando la condivisione segreta di soglia ℓ-su-n
3. Framework VOLEitH 13: Compilazione di protocolli a conoscenza zero basati su VOLE in protocolli pubblicamente verificabili

Applicazione della Teoria dei Codici

1. Decodifica nella Metrica di Hamming: Fondamento di schemi come SDitH
2. Decodifica nella Metrica di Rango: Schemi come RYDE, Mirath
3. Problema del Nucleo di Permutazione: Assunzione di difficoltà dello schema PERK

Problemi di Decodifica Ristretta

1. Schema CROSS 6: Decodifica ristretta utilizzando il protocollo CVE semplice
2. Schema WAVE 10,19: Basato sulla decodifica sindrome ternaria ad alto peso
3. Analisi Teorica 8,9: Completezza NP e difficoltà concreta di E-SDP

Conclusioni e Discussione

Conclusioni Principali

1. Integrazione Riuscita del Framework: Dimostra che i problemi di decodifica ristretta possono essere efficacemente integrati nei framework MPCitH avanzati
2. Miglioramento Significativo delle Prestazioni: Sostituendo il semplice protocollo CVE con costruzioni TCitH/VOLEitH, si riduce significativamente la dimensione della firma
3. Ampia Applicabilità: Il metodo è applicabile a diversi tipi di problemi di decodifica ristretta

Limitazioni

1. Aumento della Complessità: Rispetto al semplice protocollo CVE del CROSS originale, le costruzioni TCitH/VOLEitH sono significativamente più complesse
2. Sovraccarico Computazionale: Sebbene la dimensione della firma si riduca, potrebbe aumentare la complessità computazionale della generazione e verifica della firma
3. Dipendenza dai Parametri: Le prestazioni dipendono fortemente dalla scelta e dall'ottimizzazione dei parametri specifici

Direzioni Future

1. Ulteriore Ottimizzazione: Esplorare metodi di modellazione polinomiale più efficienti
2. Altri Problemi Ristretti: Estendere il metodo ad altri tipi di problemi di decodifica ristretta
3. Ottimizzazione dell'Implementazione: Sviluppare implementazioni efficienti per ridurre il sovraccarico computazionale

Valutazione Approfondita

Punti di Forza

1. Innovazione Tecnica: Propone un metodo di modellazione polinomiale semplice ed efficace per i problemi di decodifica ristretta
2. Miglioramento Significativo: Riduce sostanzialmente la dimensione della firma mantenendo la stessa sicurezza
3. Contributo Teorico: Stabilisce un ponte tra i problemi di decodifica ristretta e i framework MPCitH avanzati
4. Valore Pratico: Fornisce nuove idee di progettazione per gli schemi di firma post-quantistica

Insufficienze

1. Compromesso di Complessità: Scambia la complessità costruttiva per la riduzione della dimensione della firma
2. Novità Limitata: Principalmente una combinazione intelligente di tecniche esistenti, con innovazione teorica relativamente limitata
3. Dettagli di Implementazione Mancanti: Manca un'analisi dettagliata delle prestazioni e un confronto delle implementazioni pratiche

Impatto

1. Valore Accademico: Fornisce un nuovo caso di studio per l'applicazione del framework MPCitH
2. Significato Pratico: Potrebbe influenzare la scelta degli schemi nel processo di standardizzazione NIST futuro
3. Contributo Metodologico: Fornisce un riferimento per la modellazione simile di altri problemi difficili

Scenari Applicabili

1. Ambienti Limitati in Risorse: Scenari applicativi sensibili alla dimensione della firma
2. Distribuzione della Crittografia Post-Quantistica: Sistemi che richiedono diverse assunzioni di sicurezza
3. Prototipi di Ricerca: Base per ulteriore ottimizzazione e miglioramento

Bibliografia

L'articolo cita 24 importanti riferimenti bibliografici, coprendo lo sviluppo del framework MPCitH, l'applicazione della teoria dei codici e gli schemi candidati NIST correlati, fornendo una base teorica solida per la ricerca.