Signatures Basées sur MPCitH à partir de Problèmes de Décodage Restreint

Informations Fondamentales

• ID de l'article: 2510.11224
• Titre: Signatures Basées sur MPCitH à partir de Problèmes de Décodage Restreint
• Auteurs: Michele Battagliola (Université Polytechnique des Marches), Sebastian Bitzer, Antonia Wachter-Zeh, Violetta Weger (Université Technique de Munich)
• Classification: cs.CR (Cryptographie et Sécurité), cs.IT (Théorie de l'Information), math.IT (Théorie de l'Information)
• Date de publication: 13 octobre 2025 (prépublication arXiv)
• Lien de l'article: https://arxiv.org/abs/2510.11224

Résumé

Cet article intègre le problème de décodage restreint (E-SDP) dans les cadres Threshold-Computation-in-the-Head (TCitH) et VOLE-in-the-Head (VOLEitH), qui représentent les développements les plus récents du paradigme MPC-in-the-Head (MPCitH), améliorant significativement les performances des schémas de signature numérique. Les auteurs proposent une approche de modélisation structurellement simple, réalisant des tailles de signature compétitives. En instanciant le problème de décodage restreint avec les mêmes hypothèses de difficulté que CROSS, la taille de la signature est réduite de plus de deux fois par rapport à la version soumise au NIST. De plus, les auteurs découvrent que le décodage ternaire de poids plein est étroitement lié à l'hypothèse de difficulté sous-jacente de WAVE, et les signatures obtenues avec cette méthode peuvent rivaliser avec les plus petits candidats MPCitH de la compétition NIST.

Contexte et Motivation de la Recherche

Contexte du Problème

1. Besoin de normalisation de la cryptographie post-quantique: Après la normalisation de CRYSTALS-Dilithium, FALCON et SPHINCS+, le NIST a lancé en septembre 2022 un appel pour des schémas de signature numérique supplémentaires, visant à diversifier la combinaison de normes de signature post-quantiques.
2. Développement du paradigme MPCitH: Depuis sa proposition par Ishai et al. en 2007, la technologie MPCitH a transformé le paysage des signatures numériques post-quantiques. TCitH et VOLEitH, en tant que spécialisations les plus récentes de MPCitH, offrent des améliorations de performance significatives par rapport aux constructions antérieures.
3. Application de la théorie du codage en cryptographie: Les problèmes de difficulté basés sur la théorie du codage (tels que les problèmes de décodage en métrique de Hamming et en métrique de rang) fournissent une base théorique pour construire des signatures post-quantiques efficaces.

Motivation de la Recherche

1. Besoin d'optimisation des performances: Bien que le schéma de signature CROSS existant soit basé sur le problème de décodage restreint, il utilise un protocole CVE relativement simple, laissant de l'espace pour l'optimisation en termes de taille de signature.
2. Unification des cadres: Intégrer le problème de décodage restreint dans les cadres avancés TCitH/VOLEitH pour exploiter pleinement les avantages de performance de ces cadres.
3. Amélioration de la compétitivité: Réduire significativement la taille de la signature tout en maintenant la sécurité, augmentant ainsi la compétitivité dans la compétition NIST.

Contributions Principales

1. Proposition d'une méthode de modélisation polynomiale pour E-SDP: Conception d'une relation polynomiale structurellement simple mais efficace, intégrant le problème de décodage de syndrome restreint dans les cadres TCitH et VOLEitH.
2. Réduction significative de la taille des signatures de type CROSS: Pour le même problème de décodage, la taille de la signature est réduite de plus de 50% (de 12,4 kB à 5,5 kB) par rapport au schéma CROSS soumis au NIST.
3. Découverte du potentiel d'application du décodage ternaire de poids plein: Démonstration que le décodage ternaire de poids plein associé à WAVE est un problème de décodage restreint, réalisant une taille de signature comparable aux plus petits candidats MPCitH (3,1 kB).
4. Fourniture d'un schéma de paramétrisation complet: Présentation des choix de paramètres spécifiques et de l'analyse de performance pour les catégories de sécurité NIST 1, 3 et 5.

Détails de la Méthode

Définition de la Tâche

L'objectif de la recherche est de représenter le problème de décodage de syndrome restreint (E-SDP) comme une relation polynomiale, permettant sa construction dans les cadres TCitH et VOLEitH pour les schémas de signature numérique.

Définition d'E-SDP: Étant donné un ensemble de restriction E ⊂ F, une matrice de parité H ∈ F^(r×n) et un syndrome s ∈ F^r, trouver e ∈ E^n tel que eH^T = s.

Méthode de Modélisation Centrale

1. Construction de Contraintes Polynomiales

Pour une matrice de parité sous forme systématique H = (A, I_r), où A ∈ F^(r×k) et I_r est la matrice identité:

• Vecteur témoin: w ∈ F^k (vecteur d'erreur partiel)
• Vecteur d'erreur étendu: e = (w, s - wA^T)
• Polynôme de restriction: f_E(x) = ∏_{e∈E}(x - e)

Système de Relations Polynomiales:

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

où:

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

2. Analyse du Degré

Proposition 1: Cette relation polynomiale fournit une modélisation d'E-SDP de degré z = |E|. Si w ∈ F^k satisfait F(w) = 0, alors le vecteur d'erreur e = (w, s - wA^T) résout l'instance E-SDP (H, s).

Instanciations Concrètes

CROSS-SDP

• Ensemble de restriction: E = {2^i | i ∈ 7} ⊆ F_{127}
• Paramètres: |E| = 7, p = 127
• Sécurité: Basée sur l'analyse détaillée de 7,15

Ternary-SDP

• Ensemble de restriction: E = {1, 2} ⊆ F_3
• Paramètres: |E| = 2, p = 3
• Complexité: O(2^{0.247·n}) opérations (à facteur polynomial près)

Configuration Expérimentale

Stratégie de Choix des Paramètres

Selon les exigences de sécurité et les objectifs d'optimisation des performances, les paramètres clés suivants sont sélectionnés:

1. Paramètres du cadre TCitH:
   • τ: nombre de répétitions parallèles
   • N: taille du domaine d'évaluation
   • μ: degré d'extension de corps K : F
   • η: paramètre de traitement par lot
2. Paramètres du cadre VOLEitH:
   • ρ: paramètre d'extension de corps
   • B: paramètre de vérification de cohérence
   • T_open: paramètres du schéma VC

Contraintes de Sécurité

Satisfaction des exigences de sécurité suivantes:

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

Indicateurs d'Évaluation

Évaluation principale de la taille de la signature, comprenant trois composants:

• |σ_sym|: relatif au schéma VC
• |σ_w|: relatif au témoin
• |σ_F|: relatif à OWF

Résultats Expérimentaux

Résultats Principaux

Performance du Cadre TCitH

| Niveau de Sécurité | Type E-SDP | |F| | |E| | n | k | τ | N | μ | η | Taille de Signature (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 |

Performance du Cadre VOLEitH

Comparaison avec les Candidats NIST

Découvertes Clés

1. Réduction significative de taille: CROSS-SDP réduit la taille de la signature de 64,5% par rapport à CROSS original
2. Impact du choix du cadre: Pour les problèmes de haut degré, VOLEitH est plus avantageux que TCitH
3. Compétitivité: Ternary-SDP atteint des performances comparables aux meilleurs candidats MPCitH

Travaux Connexes

Développement du Paradigme MPCitH

1. MPCitH Original 23: Proposé en 2007, combinant le calcul sécurisé multipartite avec la transformation de Fiat-Shamir
2. Cadre TCitH 21: Instanciation utilisant le partage de secret à seuil ℓ-sur-n
3. Cadre VOLEitH 13: Compilation de protocoles de preuve zéro basés sur VOLE en protocoles publiquement vérifiables

Application de la Théorie du Codage

1. Décodage en Métrique de Hamming: Base des schémas tels que SDitH
2. Décodage en Métrique de Rang: Schémas RYDE, Mirath, etc.
3. Problème du Noyau de Permutation: Hypothèse de difficulté du schéma PERK

Problèmes de Décodage Restreint

1. Schéma CROSS 6: Décodage restreint utilisant un protocole CVE simple
2. Schéma WAVE 10,19: Basé sur le décodage de syndrome ternaire de poids plein
3. Analyse Théorique 8,9: Complétude NP et difficulté concrète d'E-SDP

Conclusion et Discussion

Conclusions Principales

1. Intégration de Cadre Réussie: Démonstration que le problème de décodage restreint peut être efficacement intégré dans les cadres MPCitH avancés
2. Amélioration Significative des Performances: Remplacement du protocole CVE simple par les constructions TCitH/VOLEitH, réduisant considérablement la taille de la signature
3. Applicabilité Générale: La méthode s'applique à différents types de problèmes de décodage restreint

Limitations

1. Augmentation de la Complexité: Par rapport au protocole CVE simple de CROSS original, les constructions TCitH/VOLEitH sont significativement plus complexes
2. Surcharge Computationnelle: Bien que la taille de la signature soit réduite, cela peut augmenter la complexité computationnelle de la génération et de la vérification de signature
3. Dépendance aux Paramètres: Les performances dépendent fortement du choix spécifique des paramètres et de la stratégie d'optimisation

Directions Futures

1. Optimisation Supplémentaire: Exploration de méthodes de modélisation polynomiale plus efficaces
2. Autres Problèmes Restreints: Extension de la méthode à d'autres types de problèmes de décodage restreint
3. Optimisation de l'Implémentation: Développement d'implémentations efficaces pour réduire la surcharge computationnelle

Évaluation Approfondie

Avantages

1. Innovation Technique: Proposition d'une méthode de modélisation polynomiale concise et efficace pour le problème de décodage restreint
2. Amélioration Significative: Réduction substantielle de la taille de la signature tout en maintenant la même sécurité
3. Contribution Théorique: Établissement d'un pont entre le problème de décodage restreint et les cadres MPCitH avancés
4. Valeur Pratique: Fourniture de nouvelles idées de conception pour les schémas de signature post-quantiques

Insuffisances

1. Compromis de Complexité: Échange de la complexité de construction pour la réduction de la taille de signature
2. Nouveauté Limitée: Principalement une combinaison ingénieuse de techniques existantes, avec une innovation théorique relativement limitée
3. Détails d'Implémentation Manquants: Absence d'analyse de performance détaillée et de comparaisons d'implémentation réelle

Impact

1. Valeur Académique: Fourniture d'une nouvelle étude de cas pour l'application du cadre MPCitH
2. Signification Pratique: Peut influencer les choix de schémas dans le processus de normalisation futur du NIST
3. Contribution Méthodologique: Fourniture de références pour la modélisation similaire d'autres problèmes de difficulté

Scénarios d'Application

1. Environnements aux Ressources Limitées: Scénarios d'application sensibles à la taille de la signature
2. Déploiement de Cryptographie Post-Quantique: Systèmes nécessitant une diversification des hypothèses de sécurité
3. Prototypes de Recherche: Base pour l'optimisation et l'amélioration ultérieures

Références Bibliographiques

L'article cite 24 références importantes, couvrant le développement du cadre MPCitH, l'application de la théorie du codage, ainsi que les schémas candidats NIST connexes, fournissant une base théorique solide pour la recherche.