ข้อสมมติฐานความยากเชิงคำนวณ

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

Definition

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

Scope

หัวข้อนี้ครอบคลุมข้อสมมติฐานที่วิทยาการเข้ารหัสลับอาศัย: การมีอยู่ของฟังก์ชันทางเดียว ปัญหาทางทฤษฎีจำนวน (การแยกตัวประกอบ, RSA, ลอการิทึมไม่ต่อเนื่อง) และปัญหาแลตทิซและรหัสที่ใช้ในการเข้ารหัสลับหลังยุคควอนตัม นอกจากนี้ยังกล่าวถึงลำดับชั้นระหว่างข้อสมมติฐาน ความแตกต่างระหว่างความยากในกรณีที่เลวร้ายที่สุดกับกรณีเฉลี่ย และวิธีการตรวจสอบข้อสมมติฐาน หัวข้อนี้ไม่รวมถึงกลไกการลดทอนที่เชื่อมโยงข้อสมมติฐานกับระบบ และคำจำกัดความด้านความปลอดภัยเอง ซึ่งจะกล่าวถึงในหัวข้อที่เกี่ยวข้อง

Core questions

• เหตุใดความปลอดภัยของการเข้ารหัสลับจึงต้องอาศัยข้อสมมติฐานความยากที่ยังไม่ได้รับการพิสูจน์?
• ข้อสมมติฐานหลักๆ มีอะไรบ้าง (ฟังก์ชันทางเดียว, การแยกตัวประกอบ, ลอการิทึมไม่ต่อเนื่อง, แลตทิซ)?
• ข้อสมมติฐานมีความสัมพันธ์กันอย่างไรในด้านความแข็งแกร่ง?
• ความแตกต่างระหว่างความยากในกรณีที่เลวร้ายที่สุดกับกรณีเฉลี่ยคืออะไร?
• ปัญหาที่ยากที่เป็นไปได้ได้รับการตรวจสอบอย่างไร และจะเกิดอะไรขึ้นหากปัญหาใดปัญหาหนึ่งล้มเหลว?

Key concepts

• ฟังก์ชันทางเดียว
• ฟังก์ชันประตูซ่อน
• ข้อสมมติฐานการแยกตัวประกอบจำนวนเต็ม
• ข้อสมมติฐานลอการิทึมไม่ต่อเนื่อง
• ข้อสมมติฐาน RSA และ Diffie-Hellman
• การเรียนรู้พร้อมข้อผิดพลาด (LWE)
• ความยากในกรณีที่เลวร้ายที่สุดเทียบกับกรณีเฉลี่ย
• P เทียบกับ NP
• ลำดับชั้นของข้อสมมติฐาน

Key theories

ฟังก์ชันทางเดียวเป็นข้อสมมติฐานขั้นต่ำ

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

ข้อสมมติฐานทางทฤษฎีจำนวนและแลตทิซ

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

Mechanisms

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

Clinical relevance

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

Evidence & guidelines

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

History

การพึ่งพาความยากเกิดขึ้นพร้อมกับการเข้ารหัสลับแบบกุญแจสาธารณะในปี 1976 เมื่อ Diffie และ Hellman เชื่อมโยงความปลอดภัยเข้ากับลอการิทึมไม่ต่อเนื่อง และ RSA เข้ากับการแยกตัวประกอบ ในทศวรรษ 1980 ได้มีการกำหนดฟังก์ชันทางเดียวและความแตกต่างระหว่างกรณีที่เลวร้ายที่สุด/กรณีเฉลี่ย การลดทอนจากกรณีที่เลวร้ายที่สุดไปสู่กรณีเฉลี่ยของ Ajtai (1996) และปัญหาการเรียนรู้พร้อมข้อผิดพลาดของ Regev (2005) ได้สร้างข้อสมมติฐานแลตทิซ ซึ่งได้รับความโดดเด่นในฐานะรากฐานที่ทนทานต่อควอนตัมและเป็นรากฐานของมาตรฐานหลังควอนตัมใหม่

Key figures

• Whitfield Diffie
• Martin Hellman
• Oded Goldreich
• Oded Regev
• Andrew Yao

Seminal works

• diffie1976
• goldreich2001
• katz2020

Frequently asked questions

ทำไมเราถึงไม่สามารถพิสูจน์ได้ว่าปัญหาเหล่านี้ยาก?

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

จะเกิดอะไรขึ้นหากข้อสมมติฐานความยากถูกทำลาย?

ทุกระบบที่ความปลอดภัยลดลงไปสู่ข้อสมมติฐานนั้นอาจไม่ปลอดภัยและต้องถูกแทนที่ นี่คือเหตุผลที่ภัยคุกคามควอนตัมต่อการแยกตัวประกอบและลอการิทึมไม่ต่อเนื่องกระตุ้นให้เกิดการย้ายทั่วโลกไปยังระบบที่อิงตามข้อสมมติฐานที่แตกต่างกันซึ่งทนทานต่อควอนตัม