การลดความปลอดภัยของอัลกอริธึมคีย์สมมาตรคืออะไร?

ฉันกำลังอ่านหน้า Wikipedia ของการเข้ารหัสหลังควอนตัม มันบอกว่ามันเป็นที่พึงปรารถนาสำหรับอัลกอริทึมการเข้ารหัสที่จะลดปัญหาทางคณิตศาสตร์บางอย่างโดยเฉพาะ นั่นคือความยากของระบบควรจะเกิดจากความแข็งของปัญหาทางคณิตศาสตร์บางอย่าง

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

ฉันไม่เห็นตัวอย่างใดๆ สำหรับอัลกอริทึมคีย์สมมาตร ทำไมถึงเป็นเช่นนั้น? ฉันคิดว่าพวกเขาไม่ต้องการคุณสมบัตินี้เนื่องจากธรรมชาติของการเข้ารหัสคีย์สมมาตร

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

ขอบคุณสำหรับคำตอบ มันมีประโยชน์

ฉันไม่เห็นตัวอย่างใด ๆ สำหรับอัลกอริทึมคีย์สมมาตร แต่ทำไม?

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

ยกตัวอย่างอัลกอริทึมแบบแอสสมมาตร:

ตัวอย่างเช่น ... diffie-hellman, rsa ... ลดเหลือ ... ปัญหาลอการิทึมไม่ต่อเนื่อง, การแยกตัวประกอบจำนวนเต็ม ... ตามลำดับ

นั่นไม่ถูกต้อง หากคุณได้รับ Oracle ที่สามารถทำลาย Diffie-Hellman ได้ คุณจะไม่มีทางรู้ว่าจะใช้สิ่งนั้นเพื่อแก้ปัญหาบันทึกแยก หากคุณได้รับ Oracle ที่สามารถทำลาย RSA ได้ จะไม่มีทางทราบได้ว่าจะใช้สิ่งนั้นเพื่อแยกตัวประกอบ

สิ่งที่ Diffie-Hellman ย่อให้เรียกว่า "ปัญหา Diffie-Hellman" (ในทางเทคนิคแล้ว cDH หรือ dDH ขึ้นอยู่กับว่า Oracle ของคุณทำอะไร); สิ่งที่ RSA ลดลงเรียกว่า "ปัญหา RSA"

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

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

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

ตราบเท่าที่มีความปลอดภัยลดลงในการเข้ารหัสแบบสมมาตร พวกเขามีแนวโน้มที่จะนำไปใช้กับโครงสร้างโดยใช้อุดมคติแบบดั้งเดิม เช่น ฟังก์ชันสุ่มหลอก หรือ ก การเปลี่ยนรูปแบบสุ่มหลอก. ตัวอย่างเช่น Luby และ Rackoff ได้พิสูจน์แล้วว่าเป็นไปได้ที่จะสร้างการเรียงสับเปลี่ยนแบบสุ่มหลอกจากฟังก์ชันสุ่มหลอกโดยใช้การสร้าง Feistel สามรอบ ในทำนองเดียวกัน cryptographers แบบสมมาตรอาจพยายามพิสูจน์ว่าโหมดการทำงานของ block cipher ขยายการเรียงสับเปลี่ยนแบบสุ่มหลอกในขนาดบล็อกไปสู่การเรียงสับเปลี่ยนแบบสุ่มหลอกในข้อมูลขนาดใหญ่ขึ้น

ความเชื่อมั่นจึงมาจากความเชื่อที่ว่าสิ่งดั้งเดิมแบบสมมาตรที่เราใช้นั้นสามารถแยกความแตกต่างจากคู่ที่สุ่มหลอกในอุดมคติได้ ไม่ว่าจะมีความมั่นใจมากขึ้นในข้อความ "การทำลายโครงสร้างนี้ยากพอๆ กับการแยก SHA256 ออกจากฟังก์ชันสุ่มหลอก" หรือ "การทำลายโครงสร้างนี้ยากพอๆ กับการตัดสินใจของปัญหา Diffie-Hellman ในกลุ่มนี้" ขึ้นอยู่กับผู้บริโภค