Skip to content
กลับไปยังผลการค้นหา

การเข้ารหัสลับฐานแลตทิซ

ผู้เสนอ
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 และระบบฝังตัว ที่ความทนทานต่อควอนตัมเป็นข้อกำหนดในการออกแบบ
  • ระบบการเข้ารหัสลับแบบไฮบริด ที่ผสมผสานอัลกอริทึมฐานแลตทิซและอัลกอริทึมแบบดั้งเดิมในช่วงเปลี่ยนผ่านสู่ยุคควอนตัม

วิธีการทำงาน

วิธีการทำงาน

1

เลือกมิติของแลตทิซ n, ตัวหาร q, และการแจกแจงความผิดพลาด สร้างฐานลับที่สั้นและได้ฐานสาธารณะจากฐานลับนั้นโดยใช้การแปลงแลตทิซ

2

กุญแจสาธารณะได้มาจากการแปลงแลตทิซที่ยาก โดยไม่ให้ข้อมูลเกี่ยวกับฐานลับจากมุมมองของการคำนวณ

3

ในการเข้ารหัสลับ ให้บวกข้อความที่ต้องการเข้ารหัสเข้ากับการรวมเชิงเส้นแบบมีสัญญาณรบกวนของเวกเตอร์ฐานสาธารณะ เพื่อสร้างจุดแลตทิซบวกกับสัญญาณรบกวน

4

เมื่อใช้ฐานลับที่สั้น ให้ลดจุดแลตทิซที่มีสัญญาณรบกวนและดึงข้อความที่เข้ารหัสออกมา

ข้อผิดพลาดที่พบบ่อย

  • การเลือกพารามิเตอร์แลตทิซ (มิติ ตัวหาร การแจกแจงความผิดพลาด) นั้นไม่ธรรมดา ขอแนะนำอย่างยิ่งให้ใช้พารามิเตอร์ที่ได้รับการรับรองจาก 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 แล้ว องค์กรที่จัดการข้อมูลที่ละเอียดอ่อนซึ่งมีระยะเวลาเก็บรักษาที่ยาวนาน ควรเริ่มวางแผนการย้ายระบบ

วิธีการที่เกี่ยวข้อง

แหล่งอ้างอิง

  1. 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.

    เปิดเอกสารอ้างอิงสิ่งพิมพ์
    คัดลอกแล้ว
  2. Regev, O. (2005). On lattices, learning with errors, hard instances, and public key cryptography. In Proceedings of STOC 2005, pp. 84-93.

    เปิดเอกสารอ้างอิงสิ่งพิมพ์
    คัดลอกแล้ว