อธิบายอัลกอริทึมของ Shor และ Grover

คอมพิวเตอร์ควอนตัมไม่ได้เพียงเรียกใช้อัลกอริทึมแบบดั้งเดิมได้เร็วขึ้นเท่านั้น แต่ยังใช้ประโยชน์จากการซ้อนทับและการแทรกสอดเชิงควอนตัม เพื่อแก้ปัญหาบางประเภทได้เร็วขึ้นแบบทวีคูณ อัลกอริทึมสองรายการคุกคามการเข้ารหัสลับที่ใช้งานอยู่ส่วนใหญ่ ได้แก่ ของ Shor (ทำลาย RSA/ECC) และของ Grover (ลดความแข็งแกร่งของการเข้ารหัสแบบสมมาตร/แฮช)

อัลกอริทึมของ Shor (ค.ศ. 1994) แก้ปัญหาการแยกตัวประกอบจำนวนเต็มและลอการิทึมไม่ต่อเนื่องได้ในเวลาพหุนามบนคอมพิวเตอร์ควอนตัม ซึ่งทำลาย RSA (อิงการแยกตัวประกอบ), Diffie-Hellman (ลอการิทึมไม่ต่อเนื่องมอดุโล p) และ ECDH/ECDSA (ลอการิทึมไม่ต่อเนื่องบนเส้นโค้งวงรี) ได้โดยตรง

องค์ประกอบสำคัญของอัลกอริทึมของ Shor คือการแปลงฟูเรียร์เชิงควอนตัม (QFT) ซึ่งเป็นรูปแบบเชิงควอนตัมของ DFT ที่เร็วขึ้นแบบทวีคูณ สำหรับการค้นหาคาบ QFT จะระบุคาบของ f(x) = a^x mod N จากนั้นจึงใช้ GCD เพื่อหาตัวประกอบของ N

การแยกตัวประกอบ N: (1) เลือก a แบบสุ่มโดยที่ a < N แล้วตรวจสอบว่า gcd(a,N)=1 (2) ค้นหาคาบ r ของ f(x)=a^x mod N โดยใช้ QFT (3) ด้วยความน่าจะเป็นสูง gcd(a^{r/2}±1, N) จะให้ตัวประกอบที่ไม่ใช่ตัวประกอบเล็กน้อย ขั้นตอนแบบดั้งเดิมใช้เวลา O(log N); การค้นหาคาบแบบควอนตัมใช้เวลา O((log N)^3) ซึ่งเป็นเวลาพหุนาม

วิธีแยกตัวประกอบแบบดั้งเดิมที่ดีที่สุดคือ GNFS ซึ่งใช้เวลาแบบกึ่งเลขชี้กำลัง O(exp((64/9 log N)^{1/3} log log N)^{2/3})) ส่วนอัลกอริทึมของ Shor บนคอมพิวเตอร์ควอนตัมที่ทนต่อข้อผิดพลาดใช้เวลาพหุนาม O((log N)^3) RSA-2048 ต้องใช้คิวบิตเชิงตรรกะประมาณ 4000 คิวบิต และการดำเนินการเกตประมาณ 10^9 ครั้ง คอมพิวเตอร์ NISQ ในปัจจุบันมีคิวบิตที่มีสัญญาณรบกวนประมาณ 1000 คิวบิต จึงยังไม่เป็นภัยคุกคาม

อัลกอริทึมของ Grover (ค.ศ. 1996) ให้ความเร็วเพิ่มขึ้นแบบกำลังสองสำหรับการค้นหาแบบไม่มีโครงสร้าง หากพื้นที่ค้นหามี N รายการ อัลกอริทึมแบบดั้งเดิมต้องสอบถาม O(N) ครั้ง แต่อัลกอริทึมของ Grover ต้องสอบถาม O(√N) ครั้ง เมื่อนำมาใช้กับการเข้ารหัสลับ จะทำลายกุญแจสมมาตรขนาด n บิตได้ในเวลา O(2^{n/2}) แทนที่จะเป็น O(2^n)

AES-128: ความปลอดภัยแบบดั้งเดิมอยู่ที่ 2^128 แต่อัลกอริทึมของ Grover ลดลงเหลือ 2^64 ซึ่งไม่ปลอดภัยเมื่อเผชิญกับคอมพิวเตอร์ควอนตัมขนาดใหญ่ AES-256: 2^256 → 2^128 ซึ่งยังคงปลอดภัย วิธีแก้ไขคือเพิ่มขนาดกุญแจสมมาตรเป็นสองเท่า ความต้านทานการชนกันของ SHA-256: 2^128 → 2^85 (การโจมตีแบบวันเกิด+Grover) การค้นหาค่าก่อนภาพของ SHA-256: 2^256 → 2^128 ซึ่งยัง OK

คอมพิวเตอร์ควอนตัม NISQ ในปัจจุบัน (IBM Heron: 133 คิวบิต, Google Sycamore: 70 คิวบิต) มีขนาดเล็กเกินไปและมีสัญญาณรบกวนมากเกินไปสำหรับการคำนวณที่เกี่ยวข้องกับการเข้ารหัสลับ คาดการณ์ว่าการทำลาย RSA-2048 จะเกิดขึ้นในช่วงปี 2035-2050 ด้วยคอมพิวเตอร์ควอนตัมที่ทนต่อข้อผิดพลาด การโจมตีแบบเก็บข้อมูลตอนนี้เพื่อถอดรหัสภายหลังเป็นภัยคุกคามในปัจจุบัน

ฝ่ายตรงข้ามรวบรวมข้อมูลการสื่อสารที่เข้ารหัสไว้ในปัจจุบันและจัดเก็บเอาไว้ เมื่อมีคอมพิวเตอร์ควอนตัมพร้อมใช้งาน ก็จะถอดรหัสข้อมูลเหล่านั้นย้อนหลังได้ ทำให้ความลับที่ต้องเก็บรักษาเป็นเวลานาน เช่น ข้อมูลลับของรัฐบาลและเวชระเบียน มีความเสี่ยงตั้งแต่วันนี้ การย้ายไปใช้ PQC สำหรับข้อมูลประเภทนี้ต้องเริ่มต้นทันที

ปัญหาโครงข่าย (LWE, SIS), ปัญหาอิงรหัส (McEliece), ลายเซ็นอิงแฮช (SPHINCS+), และปัญหาหลายตัวแปร ยังไม่มีอัลกอริทึมควอนตัมในเวลาพหุนามที่เป็นที่รู้จัก ปัญหาเหล่านี้เป็นรากฐานของมาตรฐานหลังควอนตัมของ NIST

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

อัลกอริทึมของ Grover ส่งผลกระทบต่อ AES-128 อย่างไร

อัลกอริทึมของ Shor ซึ่งทำงานในเวลาพหุนาม ทำลาย RSA, DH และ ECC ได้ อัลกอริทึมของ Grover ซึ่งเพิ่มความเร็วแบบกำลังสอง ลดความแข็งแกร่งของกุญแจสมมาตรลงครึ่งหนึ่ง วิธีแก้ไขคือย้ายไปใช้มาตรฐาน PQC ของ NIST ซึ่งอิงโครงข่าย บทถัดไป: CRYSTALS-Kyber KEM