Tandatangan CRYSTALS-Dilithium & Falcon

Tandatangan RSA dan ECDSA dapat dipecahkan oleh algoritma Shor. Tandatangan pascakuantum mesti menggantikannya untuk: sijil TLS, penandatanganan kod, penandatanganan e-mel (S/MIME, PGP), dan pengesahan kemas kini perisian. NIST menyeragamkan dua skim berasaskan kekisi: ML-DSA dan FN-DSA.

Dilithium berasaskan kesukaran Module-LWE dan Module-SIS (Penyelesaian Integer Pendek). Bukti keselamatan diberikan dalam QROM (Model Peramal Rawak Kuantum). Tiga variasi: Dilithium2 (kira-kira 128 bit), Dilithium3 (kira-kira 192 bit), Dilithium5 (kira-kira 256 bit). Laluan tandatangan yang ringkas dan bebas daripada pensampelan penolakan.

Kunci peribadi: matriks rahsia s1, s2. Kunci awam: t = As1 + s2. Untuk menandatangani: ambil sampel y rawak; kira w = Ay; kira cabaran c = H(mu || w1) dengan w1 = HighBits(w); kira z = y + cs1; jika ||z|| atau ||r0|| terlalu besar, tolak dan cuba lagi. Hasilkan (z, c, hint).

Sahkan (z, c, hint): semak bahawa ||z|| kecil; kira w' = Az - ct; gunakan hint untuk mendapatkan semula w1; sahkan c == H(mu || w1). Hint ialah sebilangan kecil bit daripada MakeHint(). Penolakan memastikan z tidak membocorkan s1 — hujah keselamatannya ialah hujah “gagal kemudian seragam”.

ML-DSA-65 (Dilithium3, keselamatan 192 bit): kunci awam 1952 bait, kunci peribadi 4000 bait, tandatangan 3293 bait. Bandingkan: ECDSA-P256: kunci awam 64 bait, tandatangan 64 bait. Tandatangan Dilithium kira-kira 40-50 kali lebih besar tetapi tahan kuantum.

Falcon berasaskan kekisi NTRU dan menggunakan pensampel Gaussian pada kekisi NTRU. Tandatangannya jauh lebih kecil berbanding Dilithium, tetapi penandatanganan memerlukan pensampel Gaussian titik apungan — lebih sukar dilaksanakan dalam masa malar dan lebih rumit untuk dikodkan dengan selamat.

Falcon-512 (keselamatan 128 bit): kunci awam 897 bait, tandatangan 666 bait — jauh lebih kecil berbanding Dilithium. Pertukarannya: Falcon lebih sukar dilaksanakan dengan selamat (pensampelan Gaussian terdedah kepada serangan pemasaan). Sesuai untuk persekitaran dengan lebar jalur terhad tetapi memerlukan pelaksanaan yang teliti.

SPHINCS+ ialah skim tandatangan berasaskan cincangan — pilihan konservatif tanpa andaian algebra berstruktur. Keselamatannya hanya bergantung pada keselamatan fungsi cincang. Saiz tandatangan: kira-kira 8-50 KB (besar). Penandatanganan perlahan. Digunakan apabila kepercayaan jangka panjang amat penting dan prestasi menjadi keutamaan kedua.

ML-DSA (Dilithium): tujuan umum, pelaksanaan mudah, sesuai untuk sijil TLS dan penandatanganan kod. FN-DSA (Falcon): persekitaran dengan lebar jalur terhad (Internet Benda, LPWAN). SLH-DSA (SPHINCS+): sangat konservatif, akar yang berumur panjang (kunci luar talian CA, akar kepercayaan perisian).

Dilithium: pensampelan penolakan mungkin membocorkan pemasaan cabang — gunakan perbandingan masa malar. Falcon: pensampel Gaussian menggunakan titik apungan — pastikan ketentuan FP. Kedua-duanya: elakkan saluran sampingan dalam aritmetik polinomial. Gunakan pelaksanaan rujukan daripada pakej penyerahan NIST.

NIST FIPS 204: ML-DSA (Dilithium). NIST FIPS 205: SLH-DSA (SPHINCS+). NIST FIPS 206: FN-DSA (Falcon). Semua diterbitkan pada Ogos 2024. Pustaka: OpenSSL 3.x, BoringSSL dan liboqs (projek Open Quantum Safe) melaksanakan ketiga-tiganya.

ML-DSA (Dilithium): berasaskan kekisi, ringkas, tandatangan kira-kira 3 KB. FN-DSA (Falcon): berasaskan NTRU, tandatangan kira-kira 700 bait, pelaksanaan rumit. SLH-DSA (SPHINCS+): berasaskan cincangan, konservatif, besar. Semua diseragamkan dalam FIPS 204/205/206. Seterusnya: berhijrah kepada PQC dengan pendekatan hibrid.