ลายมือชื่อ CRYSTALS-Dilithium และ Falcon

ลายเซ็น RSA และ ECDSA ถูกทำลายได้ด้วยอัลกอริทึมของ Shor ลายเซ็นหลังควอนตัมต้องเข้ามาแทนที่ลายเซ็นเหล่านี้สำหรับใบรับรอง TLS, การเซ็นโค้ด, การเซ็นอีเมล (S/MIME, PGP) และการยืนยันความถูกต้องของการอัปเดตซอฟต์แวร์ NIST ได้กำหนดมาตรฐานรูปแบบที่อิงโครงข่ายไว้สองรูปแบบ ได้แก่ ML-DSA และ FN-DSA

Dilithium อิงความยากของ Module-LWE และ Module-SIS (คำตอบจำนวนเต็มสั้น) โดยมีการพิสูจน์ความปลอดภัยใน QROM (แบบจำลองออราเคิลสุ่มเชิงควอนตัม) มีสามรูปแบบ ได้แก่ Dilithium2 (ความปลอดภัยประมาณ 128 บิต), Dilithium3 (ประมาณ 192 บิต) และ Dilithium5 (ประมาณ 256 บิต) เส้นทางการเซ็นเรียบง่ายและไม่ต้องใช้การสุ่มตัวอย่างแบบปฏิเสธ

กุญแจส่วนตัว: เมทริกซ์ลับ s1, s2 กุญแจสาธารณะ: t = As1 + s2 การเซ็น: สุ่ม y คำนวณ w = Ay คำนวณค่าท้าทาย c = H(mu || w1) โดยที่ w1 = HighBits(w) คำนวณ z = y + cs1 หาก ||z|| หรือ ||r0|| มีขนาดใหญ่เกินไป ให้ปฏิเสธและลองใหม่ ผลลัพธ์คือ (z, c, hint)

ตรวจสอบ (z, c, hint): ตรวจสอบว่า ||z|| มีขนาดเล็ก คำนวณ w' = Az - ct ใช้คำใบ้เพื่อกู้คืน w1 แล้วตรวจสอบว่า c == H(mu || w1) คำใบ้คือบิตจำนวนเล็กน้อยจาก MakeHint() การปฏิเสธช่วยให้มั่นใจว่า z จะไม่เปิดเผย s1 โดยข้อโต้แย้งด้านความปลอดภัยคือข้อโต้แย้งแบบ "ยุติแล้วจึงเป็นแบบสม่ำเสมอ"

ML-DSA-65 (Dilithium3, ความปลอดภัย 192 บิต): กุญแจสาธารณะ 1952 ไบต์, กุญแจส่วนตัว 4000 ไบต์, ลายเซ็น 3293 ไบต์ เมื่อเปรียบเทียบกับ ECDSA-P256 ซึ่งมีกุญแจสาธารณะ 64 ไบต์และลายเซ็น 64 ไบต์ ลายเซ็นของ Dilithium มีขนาดใหญ่กว่าประมาณ 40-50 เท่า แต่ปลอดภัยต่อควอนตัม

Falcon อิงโครงข่าย NTRU และใช้ตัวสุ่มตัวอย่างแบบเกาส์เซียนเหนือโครงข่าย NTRU ลายเซ็นมีขนาดเล็กกว่า Dilithium อย่างมาก แต่การเซ็นต้องใช้ตัวสุ่มตัวอย่างแบบเกาส์เซียนที่ใช้เลขทศนิยม จึงนำไปใช้งานให้มีเวลาคงที่ได้ยากกว่า และต้องเขียนโค้ดอย่างปลอดภัยซับซ้อนกว่า

Falcon-512 (ความปลอดภัย 128 บิต): กุญแจสาธารณะ 897 ไบต์, ลายเซ็น 666 ไบต์ ซึ่งเล็กกว่า Dilithium มาก ข้อแลกเปลี่ยนคือ Falcon นำไปใช้งานให้ปลอดภัยได้ยากกว่า เนื่องจากการสุ่มตัวอย่างแบบเกาส์เซียนมีความเสี่ยงต่อการโจมตีจากเวลา เหมาะสำหรับสภาพแวดล้อมที่มีแบนด์วิดท์จำกัด แต่ต้องนำไปใช้งานอย่างระมัดระวัง

SPHINCS+ เป็นรูปแบบลายเซ็นอิงแฮช ซึ่งเป็นตัวเลือกแบบอนุรักษนิยมและไม่ตั้งอยู่บนสมมติฐานพีชคณิตเชิงโครงสร้าง ความปลอดภัยอาศัยเพียงความปลอดภัยของฟังก์ชันแฮช ขนาดลายเซ็นประมาณ 8-50 KB ซึ่งใหญ่ และการเซ็นทำได้ช้า เหมาะสำหรับกรณีที่ความน่าเชื่อถือระยะยาวมีความสำคัญมากกว่าประสิทธิภาพ

ML-DSA (Dilithium): ใช้งานทั่วไป นำไปใช้งานได้ง่าย เหมาะสำหรับใบรับรอง TLS และการเซ็นโค้ด FN-DSA (Falcon): เหมาะสำหรับสภาพแวดล้อมที่มีแบนด์วิดท์จำกัด (อินเทอร์เน็ตของสรรพสิ่ง, LPWAN) SLH-DSA (SPHINCS+): อนุรักษนิยมอย่างยิ่ง เหมาะสำหรับรากฐานที่ต้องใช้งานเป็นเวลานาน (กุญแจ CA แบบออฟไลน์, รากความน่าเชื่อถือของซอฟต์แวร์)

Dilithium: การสุ่มตัวอย่างแบบปฏิเสธอาจทำให้เวลาของแขนงการทำงานรั่วไหล ควรใช้การเปรียบเทียบที่ใช้เวลาคงที่ Falcon: ตัวสุ่มตัวอย่างแบบเกาส์เซียนใช้เลขทศนิยม ควรตรวจสอบให้ FP มีความแน่นอนเหมือนกันในการคำนวณ ทั้งสองรูปแบบ: หลีกเลี่ยงช่องทางข้างเคียงในเลขคณิตพหุนาม ควรใช้การนำไปใช้งานอ้างอิงจากแพ็กเกจเอกสารส่งของ NIST

NIST FIPS 204: ML-DSA (Dilithium) NIST FIPS 205: SLH-DSA (SPHINCS+) NIST FIPS 206: FN-DSA (Falcon) ทั้งหมดเผยแพร่ในเดือนสิงหาคม 2024 ไลบรารีต่าง ๆ ได้แก่ OpenSSL 3.x, BoringSSL และ liboqs (โครงการ Open Quantum Safe) รองรับทั้งสามรูปแบบ

ML-DSA (Dilithium): อิงโครงข่าย เรียบง่าย ลายเซ็นประมาณ 3 KB FN-DSA (Falcon): อิง NTRU ลายเซ็นประมาณ 700 ไบต์ นำไปใช้งานได้ซับซ้อน SLH-DSA (SPHINCS+): อิงแฮช อนุรักษนิยม และมีขนาดใหญ่ ทั้งหมดได้รับการกำหนดมาตรฐานใน FIPS 204/205/206 บทถัดไป: การย้ายไปใช้ PQC ด้วยแนวทางแบบผสม