ImplémentationImplémentation

Résumé

Kyber est conçu pour être implémenté efficacement tant en logiciel qu'en matériel. Ses opérations principales sont des multiplications polynomiales dans R_q = Z_q[x]/(x^n + 1) avec n = 256, q = 3329.

NTT — Number Theoretic Transform

La multiplication dans R_q est l'opération dominante. Kyber l'accélère en utilisant NTT, l'analogue de la FFT dans les corps finis.

Multiplication naïve : O(n²) = 65 536 opérations
Multiplication via NTT : O(n log n) ≈ 2 048 opérations

Le NTT dans Kyber utilise des racines primitives de l'unité dans Z_q. Comme q = 3329 est premier et 3329 ≡ 1 (mod 512), il existe une racine primitive d'ordre 512, nécessaire pour NTT avec n = 256.

La Transformée

Kyber ne NTT-transforme pas tous les polynômes. Une optimisation clé est de maintenir certains polynômes en domaine NTT (déjà transformés) pour éviter des transformations inutiles :

• Â (la matrice publique transformée) est stockée dans le domaine NTT
• ŝ (la clé secrète transformée) est également stockée dans le domaine NTT
• L'encapsulation nécessite de transformer s' dans le domaine NTT et de retransformer u

Cela réduit le nombre de NTT inverses nécessaires.

Compress et Decompress

Kyber comprime les ciphertexts en supprimant les bits de faible magnitude. Cela réduit la taille de ct mais introduit une erreur de compression — une erreur qui s'ajoute à l'erreur cryptographique et doit être gérée par les paramètres.

Compress_q(x, d) = ⌈(2^d / q) · x⌋ mod 2^d
Decompress_q(y, d) = ⌈(q / 2^d) · y⌋

Où d contrôle la précision : plus de bits → moins d'erreur de compression → ciphertext plus grand.

La compression n'est pas symétrique : Decompress(Compress(x)) ≈ x mais pas égal. La différence doit être absorbée par la marge d'erreur du schéma.

FO Transform — Fujisaki-Okamoto

La transformation FO est ce qui convertit un PKE (chiffrement asymétrique) non sécurisé contre les attaques adaptatives en un KEM CCA-sécurisé.

Le PKE sous-jacent de Kyber (sans FO) est CPA-sécurisé mais pas CCA-sécurisé. Sans FO, un attaquant pourrait :

1. Intercepter un ciphertext ct
2. Le modifier légèrement → ct'
3. Observer si le récepteur accepte ct' ou non (oracle de validité)
4. Utiliser cette information pour récupérer la clé

FO élimine cela en faisant en sorte que le déchiffrement retraite le ciphertext reçu et vérifie qu'il correspond à celui qui serait généré à partir de zéro avec la même monnaie aléatoire. Si ça ne correspond pas, une clé pseudo-aléatoire est retournée (pas la vraie).

FO implicite vs explicite

Kyber utilise FO implicite : il ne retourne pas un symbole de rejet distinguable, mais une fausse clé. Cela évite les attaques d'oracle qui dépendent de la distinction entre "échec" et "succès".

Decaps(sk, ct) :
    m' = Decrypt(sk, ct)          # déchiffrer
    (K', r') = G(m' || H(pk))     # retraiter
    ct' = Encrypt(pk, m', r')     # re-chiffrer
    if ct' == ct :
        return K'                 # réelle
    else :
        return H(sk || ct)        # pseudo-aléatoire (indistinguable)

Échantillonnage Déterministe de A

La matrice A est générée à partir d'une graine d en utilisant SHAKE-128 comme générateur de nombres aléatoires extensible (XOF). Cela signifie que :

1. A n'a pas besoin d'être stockée dans la clé publique (seule la graine est stockée, 32 bytes).
2. N'importe qui peut reconstruire A en connaissant la graine.
3. La génération est déterministe : même graine → même matrice.

La graine est incluse dans pk comme faisant partie des 800/1184/1568 bytes.

Optimisations

Logiciel

Matériel

Implémentations de Référence

Références

• Bos, J. et al. (2018). "CRYSTALS-Kyber: A CCA-Secure Module-Lattice-Based KEM."
• Alkim, E. et al. (2020). "The Number Theoretic Transform and Its Applications in Lattice-Based Cryptography."
• Montgomery, P. (1985). "Modular Multiplication Without Trial Division." Mathematics of Computation.