CRYSTALS-Dilithium- en Falcon-handtekeningen

RSA- en ECDSA-handtekeningen worden door het algoritme van Shor gebroken. Postkwantumhandtekeningen moeten ze vervangen voor: TLS-certificaten, codeondertekening, e-mailondertekening (S/MIME, PGP) en authenticatie van software-updates. NIST heeft twee roostergebaseerde schema's gestandaardiseerd: ML-DSA en FN-DSA.

Dilithium is gebaseerd op de moeilijkheid van Module-LWE en Module-SIS (opgave van de korte gehele oplossing). Beveiligingsbewijs in het QROM (model van het kwantumwillekeurige orakel). Drie varianten: Dilithium2 (ongeveer 128 bits), Dilithium3 (ongeveer 192 bits), Dilithium5 (ongeveer 256 bits). Eenvoudig ondertekeningspad zonder afwijzingssteekproeven.

Privésleutel: geheime matrices s1, s2. Openbare sleutel: t = As1 + s2. Onderteken: genereer een willekeurige y; bereken w = Ay; bereken uitdaging c = H(mu || w1), waarbij w1 = HighBits(w); bereken z = y + cs1; als ||z|| of ||r0|| te groot is, wijs het resultaat af en probeer opnieuw. Geef (z, c, hint) als resultaat.

Verifieer (z, c, hint): controleer of ||z|| klein is; bereken w' = Az - ct; gebruik de aanwijzing om w1 terug te krijgen; controleer c == H(mu || w1). De aanwijzing bestaat uit een klein aantal bits uit MakeHint(). De afwijzing zorgt ervoor dat z niets lekt over s1 — het beveiligingsargument is een argument van "afbreken-dan-uniform".

ML-DSA-65 (Dilithium3, beveiliging van 192 bits): openbare sleutel 1952 bytes, privésleutel 4000 bytes, handtekening 3293 bytes. Ter vergelijking: ECDSA-P256: openbare sleutel van 64 bytes, handtekening van 64 bytes. Dilithium-handtekeningen zijn ongeveer 40 tot 50 keer groter, maar wel kwantumbestendig.

Falcon is gebaseerd op NTRU-roosters en gebruikt een Gaussische steekproeftrekker over het NTRU-rooster. Handtekeningen zijn aanzienlijk kleiner dan die van Dilithium, maar voor ondertekening is een Gaussische steekproeftrekker met drijvende komma nodig — moeilijker constant in tijd te implementeren en complexer om veilig te programmeren.

Falcon-512 (beveiliging van 128 bits): openbare sleutel 897 bytes, handtekening 666 bytes — veel kleiner dan Dilithium. Afweging: Falcon is moeilijker veilig te implementeren (Gaussische steekproeven zijn gevoelig voor timingaanvallen). Geschikt voor omgevingen met beperkte bandbreedte, maar vereist een zorgvuldige implementatie.

SPHINCS+ is een hashgebaseerd handtekeningsschema — een behoudende keuze zonder structurele algebraïsche aannames. De beveiliging berust alleen op de beveiliging van de hashfunctie. Grootte van de handtekening: ongeveer 8–50 KB (groot). Langzame ondertekening. Wordt gebruikt wanneer vertrouwen op lange termijn cruciaal is en prestaties minder belangrijk zijn.

ML-DSA (Dilithium): algemeen toepasbaar, eenvoudige implementatie, geschikt voor TLS-certificaten en codeondertekening. FN-DSA (Falcon): omgevingen met beperkte bandbreedte (IoT, LPWAN). SLH-DSA (SPHINCS+): uiterst behoudend, voor vertrouwensbasissen met een lange levensduur (offline CA-sleutels, softwarematige vertrouwensbasis).

Dilithium: afwijzingssteekproeven kunnen vertakkingsinformatie over de uitvoeringstijd lekken — gebruik een vergelijking met constante uitvoeringstijd. Falcon: de Gaussische steekproeftrekker gebruikt drijvende-kommagetallen — zorg voor determinisme van berekeningen met drijvende komma. Beide: vermijd zijkanalen in de rekenkunde voor polynomen. Gebruik referentie-implementaties uit de NIST-inzendingpakketten.

NIST FIPS 204: ML-DSA (Dilithium). NIST FIPS 205: SLH-DSA (SPHINCS+). NIST FIPS 206: FN-DSA (Falcon). Alle drie zijn in augustus 2024 gepubliceerd. Bibliotheken: OpenSSL 3.x, BoringSSL en liboqs (het Open Quantum Safe-project) ondersteunen alle drie.

ML-DSA (Dilithium): roostergebaseerd, eenvoudig, handtekeningen van ongeveer 3 KB. FN-DSA (Falcon): gebaseerd op NTRU, handtekeningen van ongeveer 700 bytes, complexe implementatie. SLH-DSA (SPHINCS+): hashgebaseerd, behoudend, groot. Alle drie zijn gestandaardiseerd in FIPS 204/205/206. Volgende onderwerp: migratie naar PQC met hybride benaderingen.