อัลกอริทึมควอนตัมของ Simon อ้างแก้ปัญหา DCP ได้ในเวลาพหุนาม แต่ยังไม่ใช่จุดจบของ ML-KEM และ ML-DSA

DCP เป็นปัญหาทางคณิตศาสตร์ที่ถูกศึกษามานาน และมีความเชื่อมโยงกับปัญหาในโครงสร้างตาข่าย ซึ่งเป็นส่วนหนึ่งของรากฐานทางทฤษฎีของการเข้ารหัสแบบหลังควอนตัม

ข้ออ้างหลักของงานมีดังนี้

• มีตัวแก้ DCP แบบเวลาพหุนาม Simon ระบุว่าอัลกอริทึมของเขาสามารถแก้ DCP ได้ในเวลาพหุนามบนคอมพิวเตอร์ควอนตัม โดยต่อยอดจากการลดรูปปัญหาที่ Oded Regev เสนอไว้ในปี 2002 ซึ่งเชื่อมปัญหา Dihedral Subgroup Problem เข้ากับ DCP
• อาจปิดช่องว่างทางทฤษฎีที่ยาวนานกว่า 20 ปี ก่อนหน้านี้มีเส้นทางการลดรูปจากปัญหาตาข่ายไปยัง DCP แต่ยังขาดอัลกอริทึมที่ทำให้เส้นทางดังกล่าวนำไปสู่การแก้ปัญหาได้อย่างมีประสิทธิภาพ ช่องว่างนี้มีมาตั้งแต่ราวปี 2004
• ใช้เทคนิคใหม่ในการดึงข้อมูลกลุ่มย่อยที่ซ่อนอยู่ งานวิจัยเสนอเทคนิคที่เรียกว่า “block-and-query” เพื่อทดแทนออราเคิลสำคัญบางส่วนในแนวทางก่อนหน้า
• อ้างผลต่อปัญหาตาข่ายหลายประเภท ในร่างงาน Simon ระบุว่าอัลกอริทึมสามารถนำไปรวมกับการลดรูปของ Regev และการปรับปรุงโดย Brakerski, Kirshanova, Stehlé และ Wen เพื่อสร้างอัลกอริทึมควอนตัมแบบเวลาพหุนามสำหรับปัญหาตาข่ายบางประเภท เช่น การหาเวกเตอร์สั้นที่สุดโดยประมาณ หรือ SVP และปัญหา Learning With Errors หรือ LWE

งานยังอ้างว่าอัลกอริทึมสามารถรับมือกับอัตราตัวอย่างที่ผิดพลาดได้สูงถึงระดับ 1/O(log n) ซึ่งเป็นคุณสมบัติที่ทำให้สามารถนำอัลกอริทึมไปประกอบกับเส้นทางการลดรูปดังกล่าวได้

ทำไมวงการจึงยังไม่รีบสรุป

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

• ยังไม่มีการประเมินโดยผู้ทรงคุณวุฒิ เอกสารถูกระบุว่าเป็น “Preliminary Draft” และเพิ่งเผยแพร่บน IACR ePrint เมื่อวันที่ 6 สิงหาคม 2026 ตามข้อมูลการเผยแพร่ที่มีอยู่
• หลักฐานสำคัญหลายส่วนยังเป็นเพียงโครงร่าง การวิเคราะห์เบื้องต้นจากผู้เชี่ยวชาญระบุว่า บทพิสูจน์ที่เป็นส่วนรับน้ำหนักของข้ออ้างยังไม่ได้แสดงรายละเอียดครบถ้วน และบทสรุปสุดท้ายเกี่ยวกับพารามิเตอร์ของ SVP และ LWE บางส่วนอ้างอิงการสื่อสารส่วนบุคคลที่ยังไม่มีการเผยแพร่เป็นอนุพันธ์ที่ตรวจสอบได้
• ยังไม่มีผลตรวจสอบจากทีมอิสระ นับตั้งแต่ร่างงานถูกเผยแพร่ ยังไม่มีการยืนยันหรือการหักล้างโดยอิสระที่ได้รับการเผยแพร่
• ปฏิกิริยาแรกเริ่มมีความกังขาสูง นักวิเคราะห์ในอุตสาหกรรมหลังควอนตัมบางรายอธิบายท่าทีแรกของวงการว่าเป็น “ความกังขาอย่างหนัก” พร้อมเรียกร้องให้ตรวจสอบข้อพิสูจน์อย่างละเอียดก่อนสรุปผล

ดังนั้นท่าทีที่เหมาะสมในตอนนี้คือ “ตรวจสอบข้อเท็จจริงก่อนตอบสนอง” ไม่ใช่การประกาศว่าการเข้ารหัสหลังควอนตัมล่มสลายแล้ว

ผลกระทบต่อ ML-KEM และ ML-DSA คืออะไร

สำหรับองค์กรที่กำลังใช้งานหรือประเมินมาตรฐานของ NIST คำตอบในระยะสั้นค่อนข้างชัดเจนว่า ยังไม่จำเป็นต้องเปลี่ยนแผนจากร่างงานวิจัยนี้เพียงฉบับเดียว

ยังไม่มีการโจมตีมาตรฐานโดยตรง

ร่างของ Simon ไม่ได้แสดงการโจมตี ML-KEM ซึ่งระบุในมาตรฐาน FIPS 203 หรือ ML-DSA ซึ่งระบุใน FIPS 204 และยังไม่มีชุดพารามิเตอร์ของ NIST ถูกโจมตีสำเร็จ

ML-KEM เป็นกลไกห่อหุ้มกุญแจสำหรับการจัดตั้งกุญแจ ส่วน ML-DSA เป็นอัลกอริทึมลายเซ็นดิจิทัล ทั้งสองมาตรฐานอาศัยสมมติฐานความยากของปัญหาตาข่ายแบบมีโครงสร้าง เช่น Module-LWE และ Module-SIS

จาก DCP ไปสู่การโจมตี ML-KEM หรือ ML-DSA ยังมีอีกหลายขั้น

แม้ DCP จะเชื่อมโยงกับปัญหาตาข่ายผ่านการลดรูปที่มีอยู่ แต่การพิสูจน์ว่าเส้นทางดังกล่าวนำไปสู่การโจมตีที่ใช้งานได้จริงกับ Module-LWE หรือ Module-SIS ซึ่งเป็นสมมติฐานเฉพาะของ ML-KEM และ ML-DSA ยังเป็นขั้นตอนทางทฤษฎีเพิ่มเติมที่ไม่ได้รับการยืนยัน

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

เป็นความเสี่ยงเชิงโครงสร้างมากกว่าภัยคุกคามทันที

หากข้ออ้างได้รับการพิสูจน์ ผลงานนี้จะทำให้เหตุผลทางทฤษฎีที่ว่า “คอมพิวเตอร์ควอนตัมอาจแก้ปัญหาตาข่ายบางประเภทได้อย่างมีประสิทธิภาพ” แข็งแรงขึ้นอย่างมาก แต่ผลกระทบต่อระบบมาตรฐานจะยังต้องผ่านการวิเคราะห์เรื่องการลดรูป โครงสร้างของปัญหา และพารามิเตอร์ที่ใช้งานจริงอีกหลายชั้น

นอกจากนี้ การมีอัลกอริทึมเชิงทฤษฎีไม่ได้แปลว่ามีเครื่องควอนตัมที่สามารถรันการโจมตีขนาดใหญ่ได้ในปัจจุบัน รายงานเกี่ยวกับข้ออ้างนี้ยังเน้นว่าไม่มีการโจมตีมาตรฐานใดถูกนำไปใช้งานจริง

บริบทจากงานก่อนหน้า

วงการไม่ได้เริ่มต้นจากศูนย์ ในปี 2025 Bai และคณะเสนออัลกอริทึมควอนตัมแบบเวลาควาซิพหุนามสำหรับ DCP รุ่นจำกัดที่เรียกว่า Extrapolated Dihedral Coset Problem บนโมดูลัสที่เป็นกำลังของสอง และงานดังกล่าวยังประยุกต์กับปัญหา SLWE ได้ด้วย

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

ท่าทีของผู้เชี่ยวชาญ: จับตาอย่างจริงจัง แต่อย่าเพิ่งตื่นตระหนก

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

ผลกระทบต่อการเข้ารหัสแบบหลังควอนตัมยังเป็น ผลกระทบแบบมีเงื่อนไข เพราะไม่ได้ขึ้นอยู่กับการแก้ DCP ได้เพียงอย่างเดียว แต่ขึ้นอยู่กับว่าเส้นทางการลดรูปจากปัญหาเหล่านั้นไปยังสมมติฐานเฉพาะของระบบมาตรฐานจะสมบูรณ์และมีประสิทธิภาพเพียงใด

ขณะเดียวกัน NIST ห้องปฏิบัติการวิชาการ และหน่วยงานกำหนดมาตรฐานยังไม่ได้ออกแถลงการณ์อย่างเป็นทางการ ซึ่งเป็นเรื่องที่คาดหมายได้ เนื่องจากร่างงานวิจัยเพิ่งเผยแพร่ได้เพียงไม่กี่วัน

สรุป

ร่างงานของ Daniel R. Simon เป็นข้ออ้างทางทฤษฎีที่สำคัญมาก หากถูกต้องจริง อาจเปลี่ยนความเข้าใจเกี่ยวกับความยากของปัญหาตาข่ายภายใต้การคำนวณควอนตัม และอาจกระทบต่อรากฐานบางส่วนของการเข้ารหัสหลังควอนตัม

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