Ring-LWE และโครงสร้างแลตทิซแบบโมดูลาร์

LWE มาตรฐานต้องใช้การคูณเมทริกซ์กับเวกเตอร์ขนาดใหญ่ ซึ่งทำให้ขนาดกุญแจใหญ่ตามไปด้วย Ring-LWE ซึ่งนำเสนอโดย Lyubashevsky, Peikert และ Regev ในปี 2010 แทนที่เวกเตอร์และเมทริกซ์ด้วยพหุนามในริง R_q = Z_q[X]/(f(X)) การจัดโครงสร้างนี้ทำให้ได้กุญแจที่กะทัดรัดกว่ามากและการคำนวณที่เร็วขึ้น จึงทำให้ Ring-LWE เป็นรากฐานที่ใช้งานได้จริงสำหรับการเข้ารหัสลับบนแลตทิซในโลกจริง

พหุนาม f(X) ที่ใช้ใน Ring-LWE โดยทั่วไปคือ f(X) = X^n + 1 โดย n เป็นกำลังของ 2 พหุนามนี้คือพหุนามไซโคลโทมิกอันดับ 2n โดยเลือกใช้พหุนามนี้เพราะไม่สามารถแยกตัวประกอบเหนือ Z ได้ ทำให้ริง R_q มีคุณสมบัติทางพีชคณิตที่ดี และช่วยให้ใช้การแปลงเชิงทฤษฎีจำนวน (NTT) เพื่อคูณได้อย่างมีประสิทธิภาพ ริงไซโคลโทมิกได้รับการศึกษาอย่างลึกซึ้งและเชื่อกันว่ามีความมั่นคงปลอดภัย

ใน Ring-LWE ค่าลับ s เป็นพหุนามใน R_q และตัวอย่างอยู่ในรูป (a, b = a*s + e) โดย a เป็นสมาชิกริงสุ่มแบบสม่ำเสมอ และ e เป็นพหุนามความผิดพลาดขนาดเล็ก ผู้โจมตีเห็นตัวอย่างลักษณะนี้จำนวนมาก และต้องกู้คืน s หรือแยกแยะตัวอย่างเหล่านี้ออกจากตัวอย่างสุ่มแบบสม่ำเสมอ ความยากอาศัยสมมติฐาน Ring-LWE ซึ่งมีการลดรูปจากปัญหาในกรณีเลวร้ายที่สุดบนแลตทิซอุดมคติ

Ring-LWE ทำให้ผู้โจมตีแก้ปัญหาได้ยากขึ้น แต่ก็มาพร้อมกับการลดรูปด้านความมั่นคงปลอดภัยที่แตกต่างจาก LWE แบบปกติเล็กน้อย การลดรูปนี้มาจากปัญหาในกรณีเลวร้ายที่สุดบนแลตทิซอุดมคติ (ideal-SVP) ไม่ใช่แลตทิซทั่วไป โดยหลักการแล้ว โครงสร้างเพิ่มเติมของแลตทิซอุดมคติอาจทำให้แก้ได้ง่ายกว่าแลตทิซทั่วไป และเรื่องนี้ยังเป็นหัวข้อวิจัยที่กำลังดำเนินอยู่ ยังไม่มีการโจมตีที่ใช้งานได้จริงซึ่งอาศัยโครงสร้างนี้

Module-LWE (M-LWE) ทำให้ทั้ง LWE และ Ring-LWE เป็นกรณีทั่วไป โดยทำงานกับเมทริกซ์ขนาด k x k ที่มีสมาชิกเป็นสมาชิกริง แทนที่จะใช้สมาชิกริงเพียงตัวเดียวหรือเมทริกซ์จำนวนเต็มขนาดใหญ่ เมื่อ k = 1 จะลดรูปเป็น Ring-LWE และเมื่อ k เพิ่มขึ้นก็จะเข้าใกล้ LWE มาตรฐาน พารามิเตอร์ k ที่ปรับค่าได้ช่วยให้สมดุลระหว่างความเชื่อมั่นด้านความมั่นคงปลอดภัยกับประสิทธิภาพได้

CRYSTALS-Kyber (ปัจจุบันคือ ML-KEM, FIPS 203) อาศัย Module-LWE ที่มีเมทริกซ์อันดับ k เหนือ R_q พารามิเตอร์ k ควบคุมระดับความปลอดภัยโดยตรง: k=2 มุ่งเป้าความปลอดภัยระดับ 128 บิต (ML-KEM-512), k=3 มุ่งเป้าระดับ 192 บิต (ML-KEM-768) และ k=4 มุ่งเป้าระดับ 256 บิต (ML-KEM-1024) โครงสร้างแบบโมดูลทำให้ใช้ฐานโค้ดเดียวกันได้ โดยปรับระดับความปลอดภัยด้วยการเปลี่ยนค่า k

การคูณพหุนามใน R_q = Z_q[X]/(X^n + 1) เป็นคอขวดด้านประสิทธิภาพ การแปลงเชิงทฤษฎีจำนวน (NTT) คือการแปลงฟูริเยร์แบบไม่ต่อเนื่องเหนือ Z_q ซึ่งแปลงพหุนามให้อยู่ในรูปแบบค่าประเมิน ทำให้การคูณกลายเป็นการคูณทีละจุด เมื่อเลือก q ให้เหมาะสมกับการใช้ NTT การคูณพหุนามจะใช้เวลา O(n log n) แทน O(n^2) ซึ่งเป็นการปรับปรุงที่สำคัญใน ML-KEM และ ML-DSA

NTT กำหนดให้ q เป็นจำนวนเฉพาะที่มี q = 1 mod 2n เพื่อให้ Z_q มีรากเอกภาพดั้งเดิมอันดับ 2n สำหรับ ML-KEM ที่มี n = 256 ค่า q = 3329 สอดคล้องกับเงื่อนไขนี้ NTT เหนือ Z_3329 ทำงานได้รวดเร็วมากบนฮาร์ดแวร์สมัยใหม่ที่มีคำสั่ง SIMD ทำให้ซีพียูทั่วไปสามารถดำเนินการ ML-KEM ได้หลายพันครั้งต่อวินาที

Ring-LWE และ Module-LWE ลดขนาดกุญแจลงอย่างมากเมื่อเทียบกับ LWE มาตรฐาน กุญแจสาธารณะของ LWE มาตรฐานสำหรับความปลอดภัยระดับ 128 บิตอาจมีขนาด 1 MB ส่วน Ring-LWE ลดขนาดลงเหลือประมาณ 800 ไบต์ และ Module-LWE (ML-KEM-768) มีกุญแจสาธารณะขนาด 1184 ไบต์ พร้อมความปลอดภัยหลังยุคควอนตัมระดับ 192 บิต ความกระชับนี้ทำให้โครงร่างแบบแลตทิซเหมาะสำหรับ TLS และระบบฝังตัว

นักวิทยาการเข้ารหัสลับบางส่วนกังวลว่าโครงสร้างพีชคณิตเพิ่มเติมของริงไซโคลโทมิกอาจเปิดทางให้เกิดการโจมตีที่ใช้ไม่ได้กับ LWE แบบพื้นฐาน ในปี 2024 Elias Rokicki และผู้ร่วมงานได้เผยแพร่การวิเคราะห์พหุนามไซโคลโทมิกอันดับ 2n โดยไม่พบการโจมตีที่ใช้ได้จริง แต่เน้นย้ำถึงความสำคัญของการตรวจสอบอย่างต่อเนื่อง กระบวนการ PQC ของ NIST พิจารณาความเสี่ยงนี้และเลือก Module-LWE ส่วนหนึ่งเพื่อลดการพึ่งพาโครงสร้างริงใดโครงสร้างริงหนึ่งมากเกินไป

นอกเหนือจาก Kyber แล้ว Ring-LWE ยังเป็นพื้นฐานของ CRYSTALS-Dilithium (ML-DSA) ซึ่งเป็นโครงร่างลายเซ็นที่ NIST ทำให้เป็นมาตรฐาน ไลบรารี SEAL จาก Microsoft รองรับการเข้ารหัสแบบโฮโมมอร์ฟิกผ่าน Ring-LWE ไลบรารีการเข้ารหัส Tink ของ Google มีการรองรับ ML-KEM Ring-LWE ได้เปลี่ยนจากโครงสร้างเชิงทฤษฎีไปสู่การนำไปใช้งานจริงในเวลาอันสั้นอย่างน่าทึ่ง โดยมีแรงผลักดันจากกระบวนการจัดทำมาตรฐานของ NIST

ข้อได้เปรียบหลักของ Ring-LWE เหนือ LWE มาตรฐานคืออะไร

Ring-LWE ย้าย LWE มาอยู่ในริงพหุนาม R_q = Z_q[X]/(X^n+1) ซึ่งลดขนาดกุญแจลงอย่างมากและทำให้สามารถคำนวณอย่างรวดเร็วด้วย NTT ได้ Module-LWE ขยายแนวคิดนี้ด้วยโครงสร้างอันดับ k และเป็นพื้นฐานของ ML-KEM (FIPS 203) และ ML-DSA (FIPS 204) จำนวนเฉพาะ q = 3329 ที่เหมาะกับ NTT ทำให้สามารถนำไปใช้งานได้อย่างมีประสิทธิภาพ ความปลอดภัยอาศัยความยากของปัญหาบนแลตทิซแบบไอดีลและแบบโมดูล