ImplementierungImplementierung

Zusammenfassung

Kyber ist darauf ausgelegt, sowohl in Software als auch in Hardware effizient implementiert zu werden. Seine Hauptoperationen sind Polynommultiplikationen in R_q = Z_q[x]/(x^n + 1) mit n = 256, q = 3329.

NTT — Number Theoretic Transform

Die Multiplikation in R_q ist die dominierende Operation. Kyber beschleunigt sie mit NTT, dem Analogon der FFT in endlichen Körpern.

Naive Multiplikation: O(n²) = 65.536 Operationen
Multiplikation via NTT: O(n log n) ≈ 2.048 Operationen

NTT in Kyber verwendet primitive Einheitswurzeln in Z_q. Da q = 3329 eine Primzahl ist und 3329 ≡ 1 (mod 512), existiert eine primitive Wurzel der Ordnung 512, die für NTT mit n = 256 benötigt wird.

Die Transformierte

Kyber NTT-transformiert nicht alle Polynome. Eine wichtige Optimierung besteht darin, einige Polynome im NTT-Bereich (bereits transformiert) zu halten, um unnötige Transformationen zu vermeiden:

• Â (die transformierte öffentliche Matrix) wird im NTT-Bereich gespeichert
• ŝ (der transformierte geheime Schlüssel) wird ebenfalls im NTT-Bereich gespeichert
• Die Einkapselung erfordert die Transformation von s' in den NTT-Bereich und die Rücktransformation von u

Dies reduziert die Anzahl der benötigten inversen NTTs.

Compress und Decompress

Kyber komprimiert die Ciphertexts, indem es Bits niedriger Größenordnung verwirft. Dies reduziert die Größe von ct, führt aber einen Kompressionsfehler ein — einen Fehler, der sich zum kryptographischen Fehler addiert und von den Parametern verwaltet werden muss.

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

Wobei d die Genauigkeit steuert: mehr Bits → weniger Kompressionsfehler → größerer Ciphertext.

Die Kompression ist nicht symmetrisch: Decompress(Compress(x)) ≈ x aber nicht gleich. Die Differenz muss von der Fehlermarge des Schemas absorbiert werden.

FO-Transform — Fujisaki-Okamoto

Der FO-Transform macht aus einem gegen adaptive Angriffe unsicheren PKE (asymmetrische Verschlüsselung) einen CCA-sicheren KEM.

Das zugrundeliegende PKE von Kyber (ohne FO) ist CPA-sicher, aber nicht CCA-sicher. Ohne FO könnte ein Angreifer:

1. Einen Ciphertext ct abfangen
2. Ihn leicht modifizieren → ct'
3. Beobachten, ob der Empfänger ct' akzeptiert oder nicht (Gültigkeitsorakel)
4. Diese Information nutzen, um den Schlüssel wiederherzustellen

FO eliminiert dies, indem die Entschlüsselung den empfangenen Ciphertext neu verarbeitet und überprüft, ob er mit dem übereinstimmt, der von Grund auf mit derselben zufälligen Münze erzeugt worden wäre. Stimmt er nicht überein, wird ein pseudozufälliger Schlüssel zurückgegeben (nicht der echte).

Impliziter vs. expliziter FO

Kyber verwendet impliziten FO: Es gibt kein unterscheidbares Zurückweisungssymbol zurück, sondern einen falschen Schlüssel. Dies vermeidet Orakelangriffe, die auf der Unterscheidung zwischen "Fehler" und "Erfolg" beruhen.

Decaps(sk, ct):
    m' = Decrypt(sk, ct)          # entschlüsseln
    (K', r') = G(m' || H(pk))     # neu verarbeiten
    ct' = Encrypt(pk, m', r')     # neu verschlüsseln
    if ct' == ct:
        return K'                 # echt
    else:
        return H(sk || ct)        # pseudozufällig (nicht unterscheidbar)

Deterministisches Sampling von A

Die Matrix A wird aus einem Seed d mit SHAKE-128 als erweiterbarer Zufallszahlengenerator (XOF) erzeugt. Das bedeutet:

1. A muss nicht im öffentlichen Schlüssel gespeichert werden (nur der Seed wird gespeichert, 32 Bytes).
2. Jeder kann A rekonstruieren, wenn er den Seed kennt.
3. Die Erzeugung ist deterministisch: gleicher Seed → gleiche Matrix.

Der Seed ist in pk als Teil der 800/1184/1568 Bytes enthalten.

Optimierungen

Software

Hardware

Referenzimplementierungen

Referenzen

• 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.