Tanda Tangan CRYSTALS-Dilithium & Falcon

Tanda tangan RSA dan ECDSA dipecahkan oleh algoritma Shor. Tanda tangan pascakuantum harus menggantikannya untuk: sertifikat TLS, penandatanganan kode, penandatanganan surel (S/MIME, PGP), dan autentikasi pembaruan perangkat lunak. NIST menstandardisasi dua skema berbasis kisi: ML-DSA dan FN-DSA.

Dilithium didasarkan pada kesulitan Module-LWE dan Module-SIS (Solusi Bilangan Bulat Pendek). Pembuktian keamanan dilakukan dalam QROM (Model Orakel Acak Kuantum). Tiga varian: Dilithium2 (sekitar 128 bit), Dilithium3 (sekitar 192 bit), Dilithium5 (sekitar 256 bit). Jalur penandatanganan sederhana dan bebas pengambilan sampel dengan penolakan.

Kunci privat: matriks rahasia s1, s2. Kunci publik: t = As1 + s2. Tanda tangani: ambil sampel y acak; hitung w = Ay; hitung tantangan c = H(mu || w1), dengan w1 = HighBits(w); hitung z = y + cs1; jika ||z|| atau ||r0|| terlalu besar, tolak dan ulangi. Keluarkan (z, c, hint).

Verifikasi (z, c, hint): periksa apakah ||z|| kecil; hitung w' = Az - ct; gunakan hint untuk memulihkan w1; verifikasi c == H(mu || w1). Hint adalah sejumlah kecil bit dari MakeHint(). Penolakan memastikan z tidak membocorkan s1 — argumen keamanannya adalah argumen "menggugurkan lalu seragam".

ML-DSA-65 (Dilithium3, keamanan 192 bit): kunci publik 1952 bita, kunci privat 4000 bita, tanda tangan 3293 bita. Sebagai perbandingan, ECDSA-P256: kunci publik 64 bita, tanda tangan 64 bita. Tanda tangan Dilithium sekitar 40–50 kali lebih besar, tetapi aman terhadap kuantum.

Falcon didasarkan pada kisi NTRU dan menggunakan pengambil sampel Gaussian pada kisi NTRU. Tanda tangannya jauh lebih kecil daripada Dilithium, tetapi penandatanganan memerlukan pengambil sampel Gaussian titik-mengambang — lebih sulit diimplementasikan dalam waktu-konstan dan lebih rumit untuk dikodekan secara aman.

Falcon-512 (keamanan 128 bit): kunci publik 897 bita, tanda tangan 666 bita — jauh lebih kecil daripada Dilithium. Konsekuensinya: Falcon lebih sulit diimplementasikan secara aman (pengambilan sampel Gaussian rentan terhadap serangan pewaktuan). Cocok untuk lingkungan dengan lebar pita terbatas, tetapi memerlukan implementasi yang cermat.

SPHINCS+ adalah skema tanda tangan berbasis hash — pilihan konservatif tanpa asumsi aljabar struktural. Keamanannya hanya bergantung pada keamanan fungsi hash. Ukuran tanda tangan: sekitar 8–50 KB (besar). Penandatanganan lambat. Digunakan ketika kepercayaan jangka panjang sangat penting dan kinerja menjadi prioritas sekunder.

ML-DSA (Dilithium): serbaguna, implementasi sederhana, cocok untuk sertifikat TLS dan penandatanganan kode. FN-DSA (Falcon): lingkungan dengan lebar pita terbatas (perangkat Internet untuk Segala Sesuatu, LPWAN). SLH-DSA (SPHINCS+): sangat konservatif, untuk akar berumur panjang (kunci CA luring, akar kepercayaan perangkat lunak).

Dilithium: pengambilan sampel dengan penolakan dapat membocorkan pewaktuan percabangan — gunakan perbandingan waktu-konstan. Falcon: pengambil sampel Gaussian menggunakan titik-mengambang — pastikan determinisme FP. Keduanya: hindari kanal samping dalam aritmetika polinomial. Gunakan implementasi rujukan dari paket pengajuan NIST.

NIST FIPS 204: ML-DSA (Dilithium). NIST FIPS 205: SLH-DSA (SPHINCS+). NIST FIPS 206: FN-DSA (Falcon). Semuanya diterbitkan pada Agustus 2024. Pustaka: OpenSSL 3.x, BoringSSL, dan liboqs (proyek Open Quantum Safe) menerapkan ketiganya.

Apa keunggulan utama Falcon dibandingkan Dilithium?

ML-DSA (Dilithium): berbasis kisi, sederhana, tanda tangan sekitar 3 KB. FN-DSA (Falcon): berbasis NTRU, tanda tangan sekitar 700 bita, implementasinya rumit. SLH-DSA (SPHINCS+): berbasis hash, konservatif, berukuran besar. Semuanya distandardisasi dalam FIPS 204/205/206. Berikutnya: bermigrasi ke PQC dengan pendekatan hibrida.