ML-DSA (FIPS 204) dan SLH-DSA (FIPS 205)

ML-DSA (Algoritma Tanda Tangan Digital berbasis Kisi-Modul), yang distandardisasi sebagai FIPS 204, diturunkan dari CRYSTALS-Dilithium. Dilithium dirancang oleh Ducas, Kiltz, Lepoint, Lyubashevsky, Schwabe, Seiler, dan Stehle, lalu diajukan kepada NIST pada 2017. Algoritma ini menggunakan kerangka Fiat-Shamir dengan pembatalan yang diterapkan pada Module-LWE, sehingga menghasilkan skema tanda tangan praktis dengan bukti keamanan yang kuat.

Transformasi Fiat-Shamir klasik mengubah protokol identifikasi interaktif menjadi tanda tangan. Untuk skema kisi, penerapan langsung membocorkan informasi tentang kunci rahasia melalui vektor respons. Teknik "dengan pembatalan" oleh Lyubashevsky menambahkan pengambilan sampel penolakan: penanda tangan memeriksa apakah respons akan membocorkan informasi, lalu membatalkan dan mencoba lagi jika demikian. Hal ini menambah sedikit beban penandatanganan, tetapi penting untuk keamanan.

Untuk menandatangani, ML-DSA mengambil sampel vektor penyamaran y dari distribusi seragam, menghitung komitmen w = Ay, menghitung nilai pencincangan dari (message, w) untuk memperoleh polinomial tantangan c, lalu menghitung respons z = y + cs. Pengambilan sampel penolakan memeriksa apakah z membocorkan informasi tentang s. Jika pemeriksaan berhasil, tanda tangan tersebut adalah (c, z) beserta petunjuk untuk verifikasi yang efisien. Jika tidak, proses diulang.

ML-DSA menetapkan tiga set parameter: ML-DSA-44 (tingkat keamanan NIST 2, sekitar 128 bit), ML-DSA-65 (tingkat 3, sekitar 192 bit), dan ML-DSA-87 (tingkat 5, sekitar 256 bit). Angka-angka tersebut merujuk pada peringkat modul dalam skema ini. Ukuran kunci publik masing-masing adalah 1312, 1952, dan 2592 bita. Ukuran tanda tangan ML-DSA-65 adalah 3293 bita, dibandingkan dengan 64 bita untuk Ed25519 pada keamanan 128 bit.

Kekurangan ML-DSA yang paling signifikan dibandingkan ECDSA atau EdDSA adalah ukuran tanda tangannya. Tanda tangan ML-DSA-65 berukuran 3293 bita, dibandingkan dengan 64 bita untuk Ed25519. Untuk protokol yang mengirimkan banyak tanda tangan (rantai sertifikat TLS, penandatanganan kode), hal ini meningkatkan penggunaan lebar pita. Namun, penandatanganan dan verifikasi ML-DSA sangat cepat (sebanding dengan atau lebih cepat daripada ECDSA), sehingga komprominya terutama terletak pada biaya komunikasi.

SLH-DSA (Algoritma Tanda Tangan Digital Tanpa Status berbasis Pencincangan), yang distandardisasi sebagai FIPS 205, diturunkan dari SPHINCS+. Berbeda dari skema kisi, keamanan SLH-DSA hanya bergantung pada ketahanan terhadap kolisi dan ketahanan terhadap prapencitraan kedua dari fungsi pencincangan yang mendasarinya (SHA-256 atau SHAKE-256). Hal ini membuat SLH-DSA sangat konservatif: algoritma ini tetap aman sekalipun asumsi kisi dipatahkan.

SLH-DSA dibangun di atas WOTS+ (Tanda Tangan Sekali Pakai Winternitz), yaitu skema berbasis pencincangan yang kunci privatnya berupa sekumpulan untaian acak dan kunci publiknya diperoleh dengan melakukan pencincangan berulang kali pada setiap untaian. Penandatanganan mencakup pencincangan sebagian berdasarkan bit pesan. WOTS+ hanya boleh digunakan sekali untuk setiap pasangan kunci agar tetap aman; penggunaan dua kali membocorkan informasi. SLH-DSA membangun penandatanganan berkali-kali di atas WOTS+ melalui pohon.

SLH-DSA menggunakan hiperpohon: pohon yang terdiri atas pohon-pohon Merkle. Setiap daun adalah kunci publik dari suatu instans WOTS+. Akarnya adalah kunci publik SLH-DSA. Tanda tangan terdiri atas tanda tangan WOTS+ untuk pesan dan jalur autentikasi dari daun ke akar. Struktur hiperpohon memungkinkan banyak tanda tangan dari satu pasangan kunci dengan menggunakan daun WOTS+ yang berbeda.

SLH-DSA memiliki 12 set parameter yang menggabungkan fungsi pencincangan (SHA-256 atau SHAKE-256), tingkat keamanan (128s/128f, 192s/192f, 256s/256f), dan pengoptimalan (s = tanda tangan kecil, f = penandatanganan cepat). Varian 128f memiliki tanda tangan berukuran 7856 bita dengan penandatanganan cepat; 128s juga berukuran 7856 bita, tetapi lebih lambat. Semuanya jauh lebih besar daripada ML-DSA, tetapi memiliki asumsi keamanan yang paling kuat.

ML-DSA lebih disukai ketika kinerja dan lebar pita penting serta asumsi kisi dipercaya. SLH-DSA lebih disukai untuk penerapan yang sangat konservatif, ketika hanya keamanan fungsi pencincangan yang dipercaya, atau untuk mempersiapkan sistem menghadapi kemungkinan kerusakan asumsi kisi di masa depan. Otoritas sertifikat dan sistem pemerintahan yang jarang melakukan penandatanganan tetapi memerlukan jaminan maksimal mungkin memilih SLH-DSA, sedangkan server TLS yang sering melakukan penandatanganan akan lebih memilih ML-DSA.

FN-DSA (FIPS 206, berbasis FALCON) menawarkan tanda tangan yang lebih kecil daripada ML-DSA (897 bita untuk FALCON-512 pada keamanan 128 bit) dengan menggunakan kisi NTRU dan pengambilan sampel Gaussian. Namun, FALCON memerlukan implementasi waktu-konstan yang cermat untuk mencegah serangan kanal-samping dari pengambil sampel Gaussian. FIPS 206 diperkirakan distandardisasi setelah FIPS 203-205 dan akan menyediakan opsi berkinerja tinggi untuk lingkungan dengan sumber daya terbatas.

Apa keunggulan keamanan utama SLH-DSA dibandingkan ML-DSA?

ML-DSA (FIPS 204) menggunakan Fiat-Shamir dengan pembatalan berdasarkan Module-LWE, sehingga menawarkan penandatanganan cepat dengan tanda tangan berukuran 3 KB (pada keamanan 192 bit). SLH-DSA (FIPS 205) menggunakan pohon Merkle berbasis pencincangan (WOTS+), yang hanya mengandalkan keamanan fungsi pencincangan dengan tanda tangan berukuran 7-50 KB. ML-DSA lebih disukai untuk aplikasi yang sensitif terhadap kinerja; SLH-DSA untuk konservatisme maksimal. FN-DSA (FALCON, FIPS 206) akan menambahkan opsi tanda tangan kisi dengan ukuran lebih kecil.