รากฐานของความปลอดภัย
รากฐานของความปลอดภัยเป็นรากฐานทางคณิตศาสตร์ที่เข้มงวดของวิทยาการเข้ารหัสลับ: คำจำกัดความที่แม่นยำของความหมายของความปลอดภัย สมมติฐานความยากที่ความปลอดภัยตั้งอยู่ และการลดทอนที่พิสูจน์ว่าแผนการเข้ารหัสมีความปลอดภัย
Definition
รากฐานของความปลอดภัยประกอบด้วยกรอบแนวคิดเชิงนิยาม สมมติฐานเชิงคำนวณ และเทคนิคการพิสูจน์ที่ใช้ในการระบุเป้าหมายความปลอดภัยอย่างแม่นยำ และเพื่อแสดงให้เห็นอย่างเข้มงวดว่าโครงสร้างการเข้ารหัสบรรลุเป้าหมายเหล่านั้น
Scope
ขอบเขตนี้ครอบคลุมทฤษฎีที่ทำให้วิทยาการเข้ารหัสลับเป็นวิทยาศาสตร์มากกว่าศิลปะ: คำจำกัดความความปลอดภัยอย่างเป็นทางการและแบบจำลองผู้โจมตี สมมติฐานความยากในการคำนวณ ระเบียบวิธีแบบลดทอนของความปลอดภัยที่พิสูจน์ได้ และบทบาทสำคัญของการสุ่มและการสุ่มเทียม ครอบคลุมถึงวิธีการกำหนดและแสดงให้เห็นว่า 'ปลอดภัย' หมายถึงอะไร ไม่รวมถึงหลักการพื้นฐานและโปรโตคอลที่เป็นรูปธรรมที่นำแนวคิดเหล่านี้ไปใช้ ซึ่งจะกล่าวถึงในสาขาที่เน้นวิทยาการเข้ารหัสลับ
Sub-topics
Core questions
- การที่แผนการเข้ารหัสลับ 'ปลอดภัย' หมายความว่าอย่างไรในทางรูปนัย?
- อำนาจและเป้าหมายของผู้โจมตีถูกจับในแบบจำลองที่แม่นยำได้อย่างไร?
- ความปลอดภัยตั้งอยู่บนสมมติฐานความยากที่ยังไม่ได้รับการพิสูจน์แต่มีความเป็นไปได้ใดบ้าง?
- การลดทอนพิสูจน์ได้อย่างไรว่าการทำลายแผนการเข้ารหัสจะแก้ปัญหาที่ยากได้?
- เหตุใดการสุ่มและการสุ่มเทียมจึงเป็นรากฐานของวิทยาการเข้ารหัสลับ?
Key concepts
- คำจำกัดความความปลอดภัย
- แบบจำลองผู้โจมตี
- ความปลอดภัยเชิงความหมายและการแยกแยะไม่ได้
- สมมติฐานความยากในการคำนวณ
- การลดทอน
- ฟังก์ชันทางเดียว
- การสุ่มเทียม
- ความน่าจะเป็นที่น้อยมาก
- ความปลอดภัยเชิงคำนวณเทียบกับความปลอดภัยเชิงทฤษฎีสารสนเทศ
Key theories
- ความปลอดภัยเชิงความหมายและการแยกแยะไม่ได้
- Goldwasser และ Micali ได้นิยามความปลอดภัยของการเข้ารหัสว่าเป็นความปลอดภัยเชิงความหมาย — ข้อความเข้ารหัสไม่เปิดเผยข้อมูลที่เป็นประโยชน์เชิงคำนวณเกี่ยวกับข้อความธรรมดา — ซึ่งแสดงให้เห็นว่าเทียบเท่ากับการแยกแยะไม่ได้ของข้อความเข้ารหัส โดยแทนที่สัญชาตญาณที่คลุมเครือด้วยเป้าหมายที่แม่นยำและสามารถทำได้
- ความปลอดภัยที่พิสูจน์ได้โดยการลดทอน
- แผนการเข้ารหัสได้รับการพิสูจน์ว่าปลอดภัยโดยการลดทอนที่แสดงให้เห็นว่าผู้โจมตีที่มีประสิทธิภาพคนใดก็ตามที่ทำลายแผนการเข้ารหัสสามารถเปลี่ยนเป็นอัลกอริทึมที่แก้ปัญหาที่ถือว่ายากได้ ดังนั้นความปลอดภัยจึงขึ้นอยู่กับสมมติฐานแต่มีความเข้มงวด
Clinical relevance
มุมมองเชิงรากฐานเป็นเหตุผลที่วิทยาการเข้ารหัสลับสมัยใหม่สามารถเชื่อถือได้: แทนที่จะหวังว่าแผนการเข้ารหัสจะต้านทานการโจมตีได้ นักออกแบบจะพิสูจน์ว่าการทำลายแผนการเข้ารหัสมีความยากพอๆ กับปัญหาที่ได้รับการศึกษามาอย่างดีภายใต้แบบจำลองผู้โจมตีที่ระบุไว้อย่างแม่นยำ ระเบียบวิธีนี้เป็นรากฐานของการอ้างสิทธิ์ความปลอดภัยของหลักการพื้นฐานและโปรโตคอลที่ได้มาตรฐานทุกชนิด เป็นแนวทางที่หน่วยงานกำกับดูแลและองค์กรกำหนดมาตรฐานอนุมัติแผนการเข้ารหัส และอธิบายว่าเหตุใดการออกแบบที่ทำขึ้นเองโดยไม่มีการพิสูจน์จึงไม่เป็นที่ยอมรับ
Evidence & guidelines
การวิเคราะห์ความปลอดภัยที่พิสูจน์ได้เป็นที่คาดหวังในการกำหนดมาตรฐานการเข้ารหัสลับในปัจจุบัน (การแข่งขัน NIST สำหรับ AES, SHA-3 และแผนการเข้ารหัสหลังควอนตัม ล้วนพิจารณาการพิสูจน์ความปลอดภัยและการลดทอน) การพิสูจน์ที่ตรวจสอบด้วยเครื่องจักร (EasyCrypt) และแบบจำลองที่ได้มาตรฐาน (random-oracle, standard model) ให้ความเข้มงวด แม้ว่าจะยังคงมีการถกเถียงเกี่ยวกับสมมติฐานในอุดมคติ การสร้างสรรค์ที่ความปลอดภัยขึ้นอยู่กับหลักการเชิงประสบการณ์เท่านั้นไม่เป็นที่สนับสนุน
History
วิทยาการเข้ารหัสลับกลายเป็นวิทยาศาสตร์ที่เข้มงวดในช่วงต้นทศวรรษ 1980 เมื่อ Goldwasser และ Micali ได้นำเสนอการเข้ารหัสแบบความน่าจะเป็นและความปลอดภัยเชิงความหมาย (1982-1984) ซึ่งให้คำจำกัดความและการพิสูจน์ที่แม่นยำเป็นครั้งแรก Yao และ Blum-Micali ได้กำหนดการสุ่มเทียมอย่างเป็นทางการ และระเบียบวิธีแบบลดทอนได้แพร่หลายไปตลอดทศวรรษ 1980 และ 1990 ซึ่งได้รับการรวบรวมใน 'Foundations of Cryptography' ของ Goldreich การปฏิวัติเชิงนิยามนี้ทำให้วิทยาการเข้ารหัสลับสมัยใหม่แตกต่างจากการสร้างรหัสในยุคก่อนหน้า
Key figures
- Shafi Goldwasser
- Silvio Micali
- Oded Goldreich
- Andrew Yao
- Manuel Blum
Related topics
Seminal works
- goldwasser1984
- goldreich2001
- katz2020
Frequently asked questions
- คำว่า 'ปลอดภัยที่พิสูจน์ได้' หมายความว่าอย่างไร?
- หมายความว่ามีการพิสูจน์ทางคณิตศาสตร์ว่าการทำลายแผนการเข้ารหัสมีความยากพอๆ กับการแก้ปัญหาบางอย่างที่เชื่อว่าแก้ไขไม่ได้ ภายใต้แบบจำลองผู้โจมตีที่ระบุไว้ ไม่ใช่การรับประกันที่สมบูรณ์: ความปลอดภัยขึ้นอยู่กับสมมติฐานความยากและแบบจำลองที่สอดคล้องกับความเป็นจริง
- เหตุใดจึงต้องพึ่งพาสมมติฐานความยากที่ยังไม่ได้รับการพิสูจน์?
- วิทยาการเข้ารหัสลับที่มีประโยชน์ส่วนใหญ่ไม่สามารถพิสูจน์ได้ว่าปลอดภัยโดยไม่มีเงื่อนไข — การทำเช่นนั้นจะแก้ปัญหาสำคัญที่ยังไม่ได้รับการแก้ไข เช่น P เทียบกับ NP แทนที่จะเป็นเช่นนั้น ความปลอดภัยจะถูกลดทอนลงเหลือชุดปัญหาเล็กๆ ที่ได้รับการศึกษามานาน (การแยกตัวประกอบ, ลอการิทึมไม่ต่อเนื่อง, แลตทิซ) ซึ่งความยากของปัญหาเหล่านี้ได้รับการสนับสนุนจากการโจมตีที่ล้มเหลวมานานหลายทศวรรษ