Skip to content
Retour aux résultats

Cryptographie basée sur les réseaux euclidiens

Introduite par
Miklós Ajtai
Année
1996
Type
public-key cryptosystem based on lattice hardness
Famille
Post-quantum cryptography

Ce texte est une traduction automatique et n’a pas encore été relu. Lire l’original en anglais

Taille de police

À quoi sert-elle ?

La cryptographie basée sur les réseaux euclidiens est une classe de cryptosystèmes dont la sécurité découle de la difficulté calculatoire des problèmes de réseaux euclidiens, en particulier le problème du plus court vecteur (SVP) et l'apprentissage avec erreurs (LWE).

Proposées pour la première fois par Miklós Ajtai en 1996, les approches basées sur les réseaux euclidiens sont devenues des candidates de premier plan pour la cryptographie post-quantique. Contrairement à RSA et ECC, qui sont vulnérables aux ordinateurs quantiques, on pense que les problèmes de réseaux euclidiens restent difficiles même face aux algorithmes quantiques.

L’intuition derrière la méthode

Un réseau euclidien est un sous-groupe discret de l'espace euclidien formé par des combinaisons linéaires entières de vecteurs de base. La cryptographie basée sur les réseaux euclidiens exploite l'écart entre deux problèmes : trouver un vecteur court dans un réseau euclidien est calculatoirement difficile, mais avec des informations supplémentaires (une base secrète), le vecteur court peut être trouvé rapidement. La cryptographie à clé publique est construite en publiant une base difficile et en gardant secrète une base facile. L'ajout d'un petit bruit aléatoire (le paradigme de l'apprentissage avec erreurs) renforce encore la sécurité en faisant ressembler le problème à un système linéaire bruité difficile à résoudre.

Histoire

Les travaux fondamentaux d'Ajtai en 1996 ont lié la difficulté des réseaux euclidiens à la cryptographie. Le cadre d'apprentissage avec erreurs (LWE) de Regev en 2005 a fourni une base pratique et polyvalente pour la cryptographie basée sur les réseaux euclidiens. Le domaine s'est accéléré après que les institutions universitaires et gouvernementales ont reconnu la menace des ordinateurs quantiques pour l'infrastructure cryptographique actuelle. En 2022, le NIST a standardisé des algorithmes cryptographiques post-quantiques, sélectionnant des schémas basés sur les réseaux euclidiens (CRYSTALS-Kyber pour le chiffrement, CRYSTALS-Dilithium pour les signatures) comme recommandations principales.

Quand l’utiliser

La cryptographie basée sur les réseaux euclidiens est essentielle pour les systèmes conçus pour rester sécurisés contre les futurs ordinateurs quantiques. Elle est recommandée pour la confidentialité à long terme des données sensibles, les communications gouvernementales et militaires, et les infrastructures qui doivent rester sécurisées pendant des décennies. À mesure que les algorithmes post-quantiques standardisés mûrissent (NIST a récemment standardisé ML-KEM et ML-DSA), les méthodes basées sur les réseaux euclidiens deviennent courantes dans les systèmes cryptographiques modernes.

Limites et points d’attention

  • Tailles de clés et de textes chiffrés plus importantes par rapport aux RSA ou ECC traditionnels, augmentant les frais généraux de stockage et de transmission
  • Plus récente et moins déployée que RSA ou ECC, l'expérience de déploiement dans le monde réel est donc limitée
  • Certains schémas basés sur les réseaux euclidiens ont des choix de paramètres subtils qui affectent considérablement la sécurité ; des paramètres incorrects peuvent être catastrophiques

Les conditions de la source ne remplacent ni une revue scientifique indépendante ni la validation par un moteur d’analyse.

Points forts

  • Réputée résistante aux attaques d'ordinateurs quantiques, y compris l'algorithme de Shor
  • Solides fondements mathématiques basés sur des problèmes de réseaux euclidiens bien étudiés
  • Prend en charge le chiffrement et les signatures numériques au sein du même cadre
  • Implémentations pratiques disponibles avec des coûts de calcul raisonnables pour le matériel moderne

Applications

  • Sécurité du transport post-quantique pour protéger les communications contre le déchiffrement quantique futur
  • Chiffrement d'archivage à long terme pour les documents et les données qui doivent rester secrets pendant des décennies
  • Systèmes de communication gouvernementaux et militaires résilients aux menaces quantiques
  • Systèmes de blockchain et de cryptomonnaies conçus pour une sécurité résistante aux quantiques
  • Systèmes IoT et embarqués où la résistance quantique est une exigence de conception
  • Systèmes cryptographiques hybrides combinant des algorithmes de réseau et traditionnels pendant la période de transition cryptographique

Comment ça marche

Comment ça marche

1

Choisir les dimensions du réseau euclidien n, le module q, et la distribution d'erreur. Générer une base courte secrète et en dériver une base publique à l'aide de transformations de réseau.

2

La clé publique est dérivée de la base de réseau difficile ; elle ne fournit aucune information sur la base secrète d'un point de vue calculatoire.

3

Pour chiffrer, ajouter le texte en clair à une combinaison linéaire bruitée des vecteurs de base publics, créant un point de réseau plus du bruit.

4

En utilisant la base courte secrète, réduire le point de réseau bruité et extraire le texte en clair.

Pièges courants

  • La sélection des paramètres de réseau (dimension, module, distribution d'erreur) n'est pas triviale ; il est fortement recommandé d'utiliser les paramètres standard approuvés par le NIST
  • Les attaques par canaux auxiliaires (temporisation, analyse de puissance) sur les opérations de réseau nécessitent une implémentation soignée ; les algorithmes à temps constant sont essentiels
  • Le mélange incorrect d'algorithmes basés sur les réseaux euclidiens et classiques peut créer des systèmes hybrides avec des faiblesses inattendues

Questions fréquentes

Quel est le problème de l'apprentissage avec erreurs (LWE)?

Le LWE est un problème calculatoire où l'on reçoit des équations linéaires bruitées sur un corps fini. Étant donné des équations de la forme a·x + e (mod q) où a est aléatoire, x est secret, et e est un petit bruit, récupérer x sans connaître e est calculatoirement difficile.

Pourquoi les clés basées sur les réseaux euclidiens sont-elles plus grandes que les clés RSA?

Les bases de réseau et les matrices qui les encodent contiennent plus d'informations qu'un seul nombre composé. L'encodage d'une base de réseau cryptographiquement nécessite plus de bits, bien que les schémas récents aient optimisé les représentations.

Les problèmes de réseau euclidien sont-ils résistants aux quantiques?

Il n'existe aucun algorithme quantique connu plus rapide que les algorithmes classiques pour les problèmes de réseau euclidien comme SVP ou LWE, bien que cela reste un domaine de recherche actif. La difficulté des réseaux euclidiens est conjecturée pour survivre aux ordinateurs quantiques.

Quelle est la recommandation du NIST sur la cryptographie basée sur les réseaux euclidiens?

Le NIST a standardisé ML-KEM (Module-Lattice-Based Key-Encapsulation Mechanism) pour le chiffrement et ML-DSA (Module-Lattice-Based Digital Signature Algorithm) pour les signatures comme algorithmes post-quantiques principaux dans les FIPS 203 et FIPS 204.

Puis-je utiliser la cryptographie basée sur les réseaux euclidiens aujourd'hui?

Oui. De nombreuses bibliothèques cryptographiques modernes prennent désormais en charge les algorithmes de réseau euclidien standardisés par le NIST. Les organisations qui traitent des données sensibles avec de longues périodes de rétention devraient commencer à planifier leur migration.

Méthodes associées

Sources

  1. Ajtai, M. (1996). Generating hard instances of the short basis problem. In Proceedings of the 28th Annual ACM Symposium on Theory of Computing, pp. 99-108.

    Ouvrir la référence de la publication
    Copié.
  2. Regev, O. (2005). On lattices, learning with errors, hard instances, and public key cryptography. In Proceedings of STOC 2005, pp. 84-93.

    Ouvrir la référence de la publication
    Copié.