การเข้ารหัสลับยุคหลังควอนตัม

การเข้ารหัสลับยุคหลังควอนตัมพัฒนาแผนการเข้ารหัสลับแบบกุญแจสาธารณะที่ความปลอดภัยขึ้นอยู่กับปัญหาที่เชื่อว่ายากแม้สำหรับคอมพิวเตอร์ควอนตัม โดยเข้ามาแทนที่ RSA และการเข้ารหัสลับแบบเส้นโค้งเชิงวงรีที่อัลกอริทึมของ Shor จะสามารถถอดรหัสได้

Definition

การเข้ารหัสลับยุคหลังควอนตัมประกอบด้วยอัลกอริทึมการเข้ารหัสลับแบบคลาสสิก (ไม่ใช่ควอนตัม) ที่ออกแบบมาเพื่อให้ยังคงปลอดภัยจากการโจมตีของศัตรูที่มีคอมพิวเตอร์ควอนตัมขนาดใหญ่ โดยอาศัยปัญหาที่ยังไม่พบอัลกอริทึมควอนตัมที่มีประสิทธิภาพในการแก้ไข

Scope

หัวข้อนี้ครอบคลุมภัยคุกคามจากควอนตัม (อัลกอริทึมของ Shor และ Grover) ตระกูลหลักของแผนการเข้ารหัสลับที่ทนทานต่อควอนตัม ได้แก่ แบบแลตทิซ แบบรหัส แบบแฮช และแบบหลายตัวแปร ความพยายามในการสร้างมาตรฐานของ NIST และอัลกอริทึมที่เลือก (ML-KEM, ML-DSA, SLH-DSA) และข้อกังวลเกี่ยวกับการย้ายระบบ เช่น 'เก็บเกี่ยวตอนนี้-ถอดรหัสทีหลัง' และการปรับใช้แบบไฮบริด ไม่รวมถึงการเข้ารหัสลับควอนตัมโดยตรง (การกระจายกุญแจควอนตัม) ซึ่งใช้อุปกรณ์ควอนตัมแทนที่จะเป็นอัลกอริทึมแบบคลาสสิก

Core questions

• เหตุใดคอมพิวเตอร์ควอนตัมจึงสามารถถอดรหัส RSA และการเข้ารหัสลับแบบเส้นโค้งเชิงวงรีได้ แต่ไม่สามารถทำลายการเข้ารหัสลับแบบสมมาตรได้อย่างรุนแรง?
• ปัญหาที่ยาก (แลตทิซ, รหัส, แฮช) ใดบ้างที่เชื่อว่าสามารถต้านทานการโจมตีของควอนตัมได้?
• NIST เลือกแผนการเข้ารหัสลับใดบ้างสำหรับการสร้างมาตรฐาน และข้อดีข้อเสียของแต่ละแผนการคืออะไร?
• ภัยคุกคาม 'เก็บเกี่ยวตอนนี้-ถอดรหัสทีหลัง' คืออะไร และเหตุใดจึงสร้างความเร่งด่วน?
• แผนการเข้ารหัสลับยุคหลังควอนตัมและคลาสสิกถูกรวมเข้าด้วยกันในการปรับใช้แบบไฮบริดระหว่างการย้ายระบบได้อย่างไร?

Key concepts

• อัลกอริทึมของ Shor
• อัลกอริทึมของ Grover
• การเข้ารหัสลับแบบแลตทิซ (การเรียนรู้ด้วยข้อผิดพลาด)
• การเข้ารหัสลับแบบรหัส
• ลายเซ็นแบบแฮช
• ML-KEM (Kyber) และ ML-DSA (Dilithium)
• เก็บเกี่ยวตอนนี้-ถอดรหัสทีหลัง
• ความคล่องตัวในการเข้ารหัสลับ
• การแลกเปลี่ยนกุญแจแบบไฮบริด

Key theories

ภัยคุกคามควอนตัมจากอัลกอริทึมของ Shor

อัลกอริทึมควอนตัมของ Shor สามารถแยกตัวประกอบจำนวนเต็มและคำนวณลอการิทึมแบบไม่ต่อเนื่องได้ในเวลาพหุนาม ซึ่งทำลาย RSA, Diffie-Hellman และการเข้ารหัสลับแบบเส้นโค้งเชิงวงรี; อัลกอริทึมของ Grover เพียงแค่เร่งความเร็วการโจมตีแบบ Brute Force เป็นกำลังสอง ดังนั้นกุญแจสมมาตรจึงเพียงแค่ต้องเพิ่มขนาดเป็นสองเท่า

ตระกูลปัญหาที่ยากต่อควอนตัม

ความปลอดภัยยุคหลังควอนตัมถูกแสวงหาในปัญหาต่างๆ เช่น การเรียนรู้ด้วยข้อผิดพลาดและปัญหาเวกเตอร์ที่สั้นที่สุดในแลตทิซ การถอดรหัสรหัสเชิงเส้นแบบสุ่ม และความปลอดภัยของฟังก์ชันแฮช ซึ่งทั้งหมดนี้ยังไม่มีอัลกอริทึมควอนตัมที่มีประสิทธิภาพเป็นที่รู้จัก

Mechanisms

แผนการเข้ารหัสลับแบบแลตทิซ เช่น ML-KEM (พัฒนาจาก CRYSTALS-Kyber) ใช้การห่อหุ้มกุญแจโดยอาศัยความยากของปัญหาการเรียนรู้ด้วยข้อผิดพลาดแบบโมดูลาร์ โดยเพิ่ม 'ข้อผิดพลาด' แบบสุ่มเล็กน้อยที่เฉพาะกุญแจส่วนตัวเท่านั้นที่สามารถลบออกได้ ลายเซ็นแบบแฮช (SLH-DSA/SPHINCS+) สร้างลายเซ็นจากความปลอดภัยของฟังก์ชันแฮชเพียงอย่างเดียว แผนการเข้ารหัสลับแบบรหัสซ่อนโครงสร้างที่ถอดรหัสได้ไว้ในรหัสเชิงเส้นที่ดูเหมือนสุ่ม การย้ายระบบโดยทั่วไปใช้โครงสร้างแบบไฮบริดที่รวมแผนการเข้ารหัสลับแบบคลาสสิกและแบบยุคหลังควอนตัมเข้าด้วยกัน เพื่อให้ความปลอดภัยยังคงอยู่หากแผนการใดแผนการหนึ่งรอด

Clinical relevance

การย้ายระบบกำลังดำเนินอยู่แล้วในระบบที่ใช้งานจริง: เบราว์เซอร์หลักและไลบรารี TLS ได้เปิดใช้งานการแลกเปลี่ยนกุญแจ ML-KEM แบบไฮบริด แอปส่งข้อความ (PQXDH ของ Signal) และ SSH ได้เพิ่มการจับมือแบบยุคหลังควอนตัม และหน่วยงานมาตรฐานกำลังกระตุ้นให้องค์กรต่างๆ ตรวจสอบการเข้ารหัสลับและวางแผนการเปลี่ยนผ่าน ความเสี่ยง 'เก็บเกี่ยวตอนนี้-ถอดรหัสทีหลัง' หมายความว่าข้อมูลที่ต้องการความลับในระยะยาวควรได้รับการปกป้องจากการโจมตีของควอนตัมตั้งแต่วันนี้

Evidence & guidelines

NIST ได้สรุปมาตรฐานยุคหลังควอนตัมชุดแรกในปี 2024: FIPS 203 (ML-KEM) สำหรับการห่อหุ้มกุญแจ, FIPS 204 (ML-DSA) และ FIPS 205 (SLH-DSA) สำหรับลายเซ็น คำแนะนำจาก NIST, NSA (CNSA 2.0) และหน่วยงานระดับชาติกำหนดไทม์ไลน์การย้ายระบบ แนวปฏิบัติที่ดีที่สุดในช่วงการเปลี่ยนผ่านคือการใช้แผนการแบบไฮบริดที่รวมอัลกอริทึมยุคหลังควอนตัมและคลาสสิกเข้าด้วยกัน

History

อัลกอริทึมของ Peter Shor ในปี 1994 แสดงให้เห็นว่าคอมพิวเตอร์ควอนตัมสามารถถอดรหัสระบบกุญแจสาธารณะที่โดดเด่นได้ ซึ่งกระตุ้นให้เกิดการค้นหาทางเลือกอื่น การเข้ารหัสลับแบบแลตทิซมีความก้าวหน้าผ่านผลลัพธ์ความยากในกรณีที่เลวร้ายที่สุดของ Ajtai และปัญหาการเรียนรู้ด้วยข้อผิดพลาดของ Regev (2005) NIST ได้เปิดตัวกระบวนการสร้างมาตรฐานสาธารณะในปี 2016; หลังจากหลายรอบได้เลือก CRYSTALS-Kyber และอื่นๆ โดยเผยแพร่มาตรฐานชุดแรก (FIPS 203-205) ในปี 2024

Key figures

• Peter Shor
• Daniel J. Bernstein
• Tanja Lange
• Oded Regev
• Chris Peikert

Seminal works

• shor1997
• nist2024mlkem
• bernstein2017

Frequently asked questions

มีคอมพิวเตอร์ควอนตัมที่สามารถถอดรหัส RSA ได้แล้วหรือไม่?

ยังไม่มี คอมพิวเตอร์ควอนตัมในปัจจุบันมีขนาดเล็กเกินไปและมีสัญญาณรบกวนมากเกินไปที่จะรันอัลกอริทึมของ Shor กับขนาดกุญแจที่ใช้งานจริง ข้อกังวลคือเครื่องจักรในอนาคต เมื่อรวมกับข้อเท็จจริงที่ว่าข้อมูลที่เข้ารหัสในวันนี้สามารถจัดเก็บและถอดรหัสได้เมื่อมีเครื่องจักรดังกล่าวอยู่

การเข้ารหัสลับยุคหลังควอนตัมต้องใช้อุปกรณ์ควอนตัมหรือไม่?

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