การเข้ารหัสลับฐานแลตทิซ
- ผู้เสนอ
- Miklós Ajtai
- ปี
- 1996
- ประเภท
- public-key cryptosystem based on lattice hardness
- กลุ่มวิธี
- Post-quantum cryptography
ข้อความนี้เป็นการแปลด้วยเครื่องและยังไม่ได้รับการตรวจทาน อ่านต้นฉบับภาษาอังกฤษ
ใช้ทำอะไร?
การเข้ารหัสลับฐานแลตทิซ (Lattice-based cryptography) เป็นกลุ่มของระบบการเข้ารหัสลับที่อาศัยความยากทางคำนวณของปัญหาแลตทิซ โดยเฉพาะปัญหาเวกเตอร์สั้นที่สุด (shortest vector problem - SVP) และปัญหาการเรียนรู้จากความผิดพลาด (learning with errors - LWE) แนวทางฐานแลตทิซซึ่งถูกเสนอครั้งแรกโดย Miklós Ajtai ในปี 1996 ได้รับความสำคัญในฐานะตัวเลือกหลักสำหรับการเข้ารหัสลับหลังยุคควอนตัม (post-quantum cryptography) ซึ่งแตกต่างจาก RSA และ ECC ที่มีความเสี่ยงต่อคอมพิวเตอร์ควอนตัม ปัญหาแลตทิซเชื่อกันว่าจะยังคงยากแม้กระทั่งกับอัลกอริทึมควอนตัม
แนวคิดเบื้องหลังวิธีการ
แลตทิซคือกลุ่มย่อยแบบไม่ต่อเนื่องของปริภูมิแบบยุคลิด (Euclidean space) ที่เกิดจากการรวมเชิงเส้นจำนวนเต็มของเวกเตอร์ฐาน (basis vectors) การเข้ารหัสลับฐานแลตทิซใช้ประโยชน์จากช่องว่างระหว่างสองปัญหา: การหาเวกเตอร์สั้นในแลตทิซนั้นยากทางคำนวณ แต่ด้วยข้อมูลเพิ่มเติม (ฐานลับ) เวกเตอร์สั้นสามารถหาได้เร็ว การเข้ารหัสลับแบบกุญแจสาธารณะ (public-key cryptography) ถูกสร้างขึ้นโดยการเผยแพร่ฐานที่ยากและเก็บฐานที่ง่ายไว้เป็นความลับ การเพิ่มสัญญาณรบกวนแบบสุ่มขนาดเล็ก (กระบวนทัศน์การเรียนรู้จากความผิดพลาด) ช่วยเสริมความปลอดภัยยิ่งขึ้นโดยทำให้ปัญหามีลักษณะคล้ายระบบเชิงเส้นที่มีสัญญาณรบกวนซึ่งแก้ได้ยาก
ประวัติศาสตร์
งานพื้นฐานของ Ajtai ในปี 1996 เชื่อมโยงความยากของแลตทิซกับการเข้ารหัสลับ กรอบการทำงาน learning with errors (LWE) ของ Regev ในปี 2005 เป็นพื้นฐานที่ใช้งานได้จริงและหลากหลายสำหรับการเข้ารหัสลับฐานแลตทิซ สาขานี้เร่งตัวขึ้นหลังจากสถาบันการศึกษาและหน่วยงานรัฐบาลตระหนักถึงภัยคุกคามจากคอมพิวเตอร์ควอนตัมต่อโครงสร้างพื้นฐานการเข้ารหัสลับในปัจจุบัน ในปี 2022 NIST ได้ให้สัตยาบันอัลกอริทึมการเข้ารหัสลับหลังยุคควอนตัม โดยเลือกแผนการเข้ารหัสลับฐานแลตทิซ (CRYSTALS-Kyber สำหรับการเข้ารหัสลับ, CRYSTALS-Dilithium สำหรับการลงนาม) เป็นคำแนะนำหลัก
ควรใช้เมื่อใด
การเข้ารหัสลับฐานแลตทิซมีความสำคัญอย่างยิ่งต่อระบบที่ออกแบบมาเพื่อคงความปลอดภัยต่อคอมพิวเตอร์ควอนตัมในอนาคต แนะนำสำหรับความลับข้อมูลที่ละเอียดอ่อนในระยะยาว การสื่อสารของรัฐบาลและกองทัพ และโครงสร้างพื้นฐานที่ต้องคงความปลอดภัยไปอีกหลายทศวรรษ เมื่ออัลกอริทึมหลังยุคควอนตัมที่ได้มาตรฐานมีความสมบูรณ์มากขึ้น (NIST ได้ให้สัตยาบัน ML-KEM และ ML-DSA เมื่อเร็วๆ นี้) วิธีการฐานแลตทิซกำลังกลายเป็นกระแสหลักในระบบการเข้ารหัสลับสมัยใหม่
ข้อจำกัดและข้อควรพิจารณา
- ขนาดกุญแจและข้อความเข้ารหัสมีขนาดใหญ่กว่า RSA หรือ ECC แบบดั้งเดิม เพิ่มภาระในการจัดเก็บและส่งข้อมูล
- ใหม่กว่าและมีการใช้งานจริงน้อยกว่า RSA หรือ ECC ประสบการณ์การใช้งานจริงจึงมีจำกัด
- แผนการเข้ารหัสลับฐานแลตทิซบางแผนมีการเลือกพารามิเตอร์ที่ละเอียดอ่อนซึ่งส่งผลต่อความปลอดภัยอย่างมาก พารามิเตอร์ที่ไม่ถูกต้องอาจนำไปสู่หายนะได้
เงื่อนไขจากแหล่งที่มาไม่สามารถใช้แทนการทบทวนทางวิทยาศาสตร์ที่เป็นอิสระหรือการตรวจสอบโดยเอนจินวิเคราะห์ได้
จุดแข็ง
- เชื่อว่าสามารถต้านทานการโจมตีด้วยคอมพิวเตอร์ควอนตัม รวมถึงอัลกอริทึมของ Shor
- มีรากฐานทางคณิตศาสตร์ที่แข็งแกร่งซึ่งอิงตามปัญหาแลตทิซที่ศึกษามาอย่างดี
- รองรับทั้งการเข้ารหัสลับและการลงนามดิจิทัลภายในกรอบการทำงานเดียวกัน
- มีการนำไปใช้งานจริงพร้อมต้นทุนการคำนวณที่สมเหตุสมผลสำหรับฮาร์ดแวร์สมัยใหม่
การประยุกต์ใช้
- การรักษาความปลอดภัยการขนส่งข้อมูลหลังยุคควอนตัม เพื่อปกป้องการสื่อสารจากการถอดรหัสด้วยควอนตัมในอนาคต
- การเข้ารหัสลับเอกสารและข้อมูลเพื่อการจัดเก็บระยะยาว ที่ต้องคงความลับไปอีกหลายทศวรรษ
- ระบบการสื่อสารของรัฐบาลและกองทัพ ที่ทนทานต่อภัยคุกคามจากควอนตัม
- ระบบบล็อกเชนและสกุลเงินดิจิทัล ที่ออกแบบมาเพื่อความปลอดภัยที่ทนทานต่อควอนตัม
- ระบบ IoT และระบบฝังตัว ที่ความทนทานต่อควอนตัมเป็นข้อกำหนดในการออกแบบ
- ระบบการเข้ารหัสลับแบบไฮบริด ที่ผสมผสานอัลกอริทึมฐานแลตทิซและอัลกอริทึมแบบดั้งเดิมในช่วงเปลี่ยนผ่านสู่ยุคควอนตัม
วิธีการทำงาน
วิธีการทำงาน
เลือกมิติของแลตทิซ n, ตัวหาร q, และการแจกแจงความผิดพลาด สร้างฐานลับที่สั้นและได้ฐานสาธารณะจากฐานลับนั้นโดยใช้การแปลงแลตทิซ
กุญแจสาธารณะได้มาจากการแปลงแลตทิซที่ยาก โดยไม่ให้ข้อมูลเกี่ยวกับฐานลับจากมุมมองของการคำนวณ
ในการเข้ารหัสลับ ให้บวกข้อความที่ต้องการเข้ารหัสเข้ากับการรวมเชิงเส้นแบบมีสัญญาณรบกวนของเวกเตอร์ฐานสาธารณะ เพื่อสร้างจุดแลตทิซบวกกับสัญญาณรบกวน
เมื่อใช้ฐานลับที่สั้น ให้ลดจุดแลตทิซที่มีสัญญาณรบกวนและดึงข้อความที่เข้ารหัสออกมา
ข้อผิดพลาดที่พบบ่อย
- การเลือกพารามิเตอร์แลตทิซ (มิติ ตัวหาร การแจกแจงความผิดพลาด) นั้นไม่ธรรมดา ขอแนะนำอย่างยิ่งให้ใช้พารามิเตอร์ที่ได้รับการรับรองจาก NIST
- การโจมตีช่องทางข้างเคียง (timing, power analysis) ต่อการดำเนินการแลตทิซต้องมีการนำไปใช้อย่างระมัดระวัง อัลกอริทึมแบบ constant-time เป็นสิ่งจำเป็น
- การผสมผสานอัลกอริทึมฐานแลตทิซและอัลกอริทึมแบบดั้งเดิมอย่างไม่ถูกต้อง อาจสร้างระบบไฮบริดที่มีจุดอ่อนที่ไม่คาดคิด
คำถามที่พบบ่อย
ปัญหา learning with errors (LWE) คืออะไร?
LWE เป็นปัญหาเชิงคำนวณที่ผู้ใช้ได้รับสมการเชิงเส้นที่มีสัญญาณรบกวนในฟีลด์จำกัด เมื่อได้รับสมการในรูปแบบ a·x + e (mod q) โดยที่ a เป็นค่าสุ่ม x เป็นค่าลับ และ e เป็นสัญญาณรบกวนขนาดเล็ก การกู้คืน x โดยไม่ทราบค่า e นั้นยากทางคำนวณ
เหตุใดกุญแจฐานแลตทิซจึงมีขนาดใหญ่กว่ากุญแจ RSA?
ฐานแลตทิซและเมทริกซ์ที่เข้ารหัสฐานเหล่านั้นมีข้อมูลมากกว่าจำนวนประกอบเพียงจำนวนเดียว การเข้ารหัสฐานแลตทิซต้องใช้บิตมากกว่า แม้ว่าแผนการเข้ารหัสลับล่าสุดได้ปรับปรุงการแสดงผลให้เหมาะสมแล้วก็ตาม
ปัญหาแลตทิซทนทานต่อควอนตัมหรือไม่?
ยังไม่มีอัลกอริทึมควอนตัมใดที่เป็นที่รู้จักซึ่งเร็วกว่าอัลกอริทึมแบบคลาสสิกสำหรับปัญหาแลตทิซ เช่น SVP หรือ LWE แม้ว่านี่จะยังคงเป็นพื้นที่การวิจัยที่กำลังดำเนินอยู่ก็ตาม ความยากของแลตทิซถูกคาดการณ์ว่าจะยังคงอยู่รอดได้แม้จะมีคอมพิวเตอร์ควอนตัม
NIST แนะนำการเข้ารหัสลับฐานแลตทิซอย่างไร?
NIST ได้ให้สัตยาบัน ML-KEM (Module-Lattice-Based Key-Encapsulation Mechanism) สำหรับการเข้ารหัสลับ และ ML-DSA (Module-Lattice-Based Digital Signature Algorithm) สำหรับการลงนาม เป็นอัลกอริทึมหลังยุคควอนตัมหลักใน FIPS 203 และ FIPS 204
ฉันสามารถใช้การเข้ารหัสลับฐานแลตทิซได้แล้วหรือยัง?
ได้แล้ว ไลบรารีการเข้ารหัสลับสมัยใหม่หลายแห่งรองรับอัลกอริทึมฐานแลตทิซที่ได้มาตรฐาน NIST แล้ว องค์กรที่จัดการข้อมูลที่ละเอียดอ่อนซึ่งมีระยะเวลาเก็บรักษาที่ยาวนาน ควรเริ่มวางแผนการย้ายระบบ
วิธีการที่เกี่ยวข้อง
แหล่งอ้างอิง
Ajtai, M. (1996). Generating hard instances of the short basis problem. In Proceedings of the 28th Annual ACM Symposium on Theory of Computing, pp. 99-108.
เปิดเอกสารอ้างอิงสิ่งพิมพ์คัดลอกแล้วRegev, O. (2005). On lattices, learning with errors, hard instances, and public key cryptography. In Proceedings of STOC 2005, pp. 84-93.
เปิดเอกสารอ้างอิงสิ่งพิมพ์คัดลอกแล้ว