CRYSTALS-Dilithium- og Falcon-signaturer

RSA- og ECDSA-signaturer brytes av Shors algoritme. Postkvantesignaturer må erstatte dem for TLS-sertifikater, kodesignering, e-postsignering (S/MIME, PGP) og autentisering av programvareoppdateringer. NIST har standardisert to gitterbaserte skjemaer: ML-DSA og FN-DSA.

Dilithium er basert på vanskeligheten av Module-LWE og Module-SIS (Short Integer Solution). Sikkerhetsbeviset er formulert i QROM (Quantum Random Oracle Model). Det finnes tre varianter: Dilithium2 (~128-bit), Dilithium3 (~192-bit) og Dilithium5 (~256-bit). Signeringsforløpet er enkelt og uten rejection sampling.

Privat nøkkel: hemmelige matriser s1 og s2. Offentlig nøkkel: t = As1 + s2. Signer: sample en tilfeldig y, beregn w = Ay, og beregn utfordringen c = H(mu || w1), der w1 = HighBits(w). Beregn z = y + cs1. Hvis ||z|| eller ||r0|| er for stor, avvis og prøv på nytt. Resultatet er (z, c, hint).

Verifiser (z, c, hint): kontroller at ||z|| er liten, beregn w' = Az - ct, bruk hint til å gjenopprette w1, og kontroller c == H(mu || w1). Hint er et lite antall biter fra MakeHint(). Avvisning sikrer at z ikke lekker s1 – sikkerhetsargumentet er et «aborts-then-uniform»-argument.

ML-DSA-65 (Dilithium3, 192-bit sikkerhet): offentlig nøkkel på 1952 byte, privat nøkkel på 4000 byte og signatur på 3293 byte. Til sammenligning har ECDSA-P256 en offentlig nøkkel på 64 byte og en signatur på 64 byte. Dilithium har ~40–50 ganger større signaturer, men er kvantesikkert.

Falcon er basert på NTRU-gittere og bruker en Gaussisk sampler over NTRU-gitteret. Signaturene er betydelig mindre enn Dilithium-signaturer, men signering krever en flyttallsbasert Gaussisk sampler – vanskeligere å implementere med konstant kjøretid og mer komplisert å implementere sikkert.

Falcon-512 (128-bit sikkerhet): offentlig nøkkel på 897 byte og signatur på 666 byte – mye mindre enn Dilithium. Avveiningen er at Falcon er vanskeligere å implementere sikkert (Gaussisk sampling er utsatt for tidsangrep). Det egner seg for miljøer med begrenset båndbredde, men krever en nøye implementasjon.

SPHINCS+ er et hashbasert signaturskjema – et konservativt valg uten strukturelle algebraiske antakelser. Sikkerheten avhenger bare av sikkerheten til hashfunksjonen. Signaturstørrelsen er ~8–50 KB (stor). Signering er langsom. Det brukes der langsiktig tillit er avgjørende og ytelse er mindre viktig.

ML-DSA (Dilithium): generell bruk, enkel implementasjon, egnet for TLS-sertifikater og kodesignering. FN-DSA (Falcon): miljøer med begrenset båndbredde (IoT, LPWAN). SLH-DSA (SPHINCS+): svært konservativt valg for røtter som skal vare lenge (frakoblede CA-nøkler, programvarerot for tillit).

Dilithium: rejection sampling kan lekke informasjon gjennom grenens kjøretid – bruk sammenligning i konstant tid. Falcon: den Gaussiske sampleren bruker flyttall – sørg for determinisme i flyttallsberegningene. Begge: unngå sidekanaler i polynomaritmetikken. Bruk referanseimplementasjoner fra NISTs innsendingspakker.

NIST FIPS 204: ML-DSA (Dilithium). NIST FIPS 205: SLH-DSA (SPHINCS+). NIST FIPS 206: FN-DSA (Falcon). Alle ble publisert i august 2024. Bibliotekene OpenSSL 3.x, BoringSSL og liboqs (Open Quantum Safe-prosjektet) implementerer alle tre.

ML-DSA (Dilithium): gitterbasert, enkelt, ~3 KB store signaturer. FN-DSA (Falcon): NTRU-basert, ~700 byte store signaturer, kompleks implementasjon. SLH-DSA (SPHINCS+): hashbasert, konservativt, stort. Alle er standardisert i FIPS 204/205/206. Neste emne: migrering til PQC med hybride tilnærminger.