Cryptographie multivariée : sécurité basée sur les polynômes

La cryptographie multivariée fonde la sécurité sur la résolution de systèmes d'équations polynomiales. Alors que le Portefeuille résistant aux quantiques SynX utilise des schémas basés sur le hachage et le réseau, les approches multivariées représentent une autre famille post-quantique.

Le problème MQ

Problème quadratique multivarié (MQ) :

• Étant donné de nombreuses équations quadratiques sur des corps finis
• Trouver des valeurs de solution satisfaisant toutes les équations
• NP-complet dans le cas général
• Aucun algorithme quantique connu n'offre une accélération significative

Comment fonctionnent les signatures multivariées

Construction de base :

• Clé privée : deux transformations inversibles + carte centrale
• Clé publique : la composition semble aléatoire
• Signature : inverser en utilisant une structure privée
• Vérification : évaluer les polynômes publics

Candidats NIST

L'échec de Rainbow

Comme SIKE, Rainbow a été cassé en 2022 :

• Structure permettant une attaque classique
• Calcul du week-end sur PC standard
• Besoin renforcé de choix conservateurs

Avantages du multivarié

• Très petites tailles de signature (une fois sécurisées)
• Vérification rapide
• Base mathématique différente de celle des treillis
• Longue histoire de recherche

Défis

• Plusieurs candidats cassés récemment
• Clés de grande taille pour des paramètres sécurisés
• Complexe à mettre en œuvre correctement
• Une communauté de recherche plus petite que les treillis

Pourquoi SynX utilise plutôt SPHINCS+

Le Portefeuille résistant aux quantiques SynX choisi des signatures basées sur le hachage :

• Hypothèses minimales (juste la sécurité de la fonction de hachage)
• Aucune structure algébrique à exploiter
• Sélection primaire NIST
• Conservateur malgré une taille plus grande

Diversité dans le paysage PQC

Plusieurs familles assurent la résilience des écosystèmes :

• Treillis (Kyber, Dilithium)
• Basé sur le hachage (SPHINCS+)
• Basé sur le code (Classic McEliece)
• Multivarié (recherche en cours)

Foire aux questions

Le multivarié pourrait-il devenir courant ?

Possible avec de nouvelles constructions. Actuel Portefeuille résistant aux quantiques SynX les choix se sont révélés sûrs aujourd’hui.

Pourquoi les signatures continuent-elles à être cassées ?

PQC est plus récent que la cryptographie classique. Le processus NIST permet d'identifier les faiblesses avant le déploiement.