ในการพิสูจน์ความปลอดภัยการเข้ารหัสส่วนใหญ่จะใช้เทคนิคการพิสูจน์การลด ตอนนี้ฉันได้อ่านบทพิสูจน์การลดหย่อนมากมายและได้ลองทำด้วยตัวเองแล้ว และฉันคิดว่าฉันเข้าใจดีทีเดียว ในขณะที่อ่านบทพิสูจน์เหล่านั้น ฉันสังเกตเห็นสองรูปแบบหลักของการลดลงดังกล่าว
สมมติว่าเรามีแบบแผน $B$ ขึ้นอยู่กับ $A$. พวกเรารู้ $A$ ปลอดภัย หากใครต้องการพิสูจน์ความปลอดภัยของ $B$ โดยลดการรักษาความปลอดภัยของ $A$ เขาสามารถดำเนินการได้ดังนี้:
- สไตล์: สมมติว่าเป็นศัตรูที่สามารถทำลายได้ $B$ $\ลูกศรขวา$ สำหรับการลดลงสามารถสร้างศัตรูใหม่ขึ้นมาได้ $A$ ใช้ทำลายศัตรู $B$ $\ลูกศรขวา$ ผลที่ได้คือความขัดแย้งที่แสดงให้เห็นว่าไม่มีศัตรูที่ไม่มีความสำคัญเลย $B$
- สไตล์: สมมติว่าเป็นฝ่ายตรงข้าม ppt ตามอำเภอใจ $B$ $\ลูกศรขวา$ แสดง (เช่น ด้วยการวิเคราะห์แบบสุ่มของการทดลอง) ที่ทำลาย $B$ ยากพอ ๆ กับการทำลาย $A$จึงลดความซับซ้อนของการทำลายลง $B$ ถึงความซับซ้อนของการแตกหัก $A$ $\ลูกศรขวา$ เนื่องจากมีศัตรูเพียงเล็กน้อยเท่านั้นที่ต่อต้าน $A$ ไม่มีศัตรูที่ไม่สำคัญเลย $B$
แน่นอนว่าสิ่งนี้ทำให้ง่ายขึ้น แต่ฉันอยากให้คุณเข้าใจสิ่งที่ฉันสังเกตเห็น
คำถามของฉัน: สไตล์เหล่านี้มีอยู่จริงไหม? พวกเขาทั้งสอง (เขียนอย่างถูกต้องอย่างเป็นทางการ) สามารถพิสูจน์เหมือนกันได้หรือไม่? พวกเขาทั้งสอง (โดยเฉพาะรูปแบบที่ 1.) สมบูรณ์หรือไม่? ควรใช้รูปแบบใดในการพิสูจน์
แก้ไข: คำจำกัดความที่ชัดเจนยิ่งขึ้นของรูปแบบที่ 2: ในความรู้เบื้องต้นเกี่ยวกับการเข้ารหัสสมัยใหม่ พิสูจน์ระบบเข้ารหัสลับบน PRG: ในการวิเคราะห์สุ่ม พวกเขาระบุว่า การทำลายระบบเข้ารหัสลับนั้นมีความเป็นไปได้พอๆ กับการทำลาย PRGพวกเขาใช้สิ่งนี้เพื่อบอกเป็นนัยว่าฝ่ายตรงข้ามตามอำเภอใจจะต้องไม่คำนึงถึงรูปแบบนี้: เนื่องจากสิ่งนี้เล็กน้อยและพวกเขาก็มีโอกาสเหมือนกัน อีกฝ่ายหนึ่งจึงต้องไม่มีความสำคัญ
(หมายเหตุ: โดยย่อ ฉันจะอธิบาย 1. เป็น: $B \rightarrow A \rightarrow \unicode{x21af} \rightarrow B$ และ 2. เป็น: $B \rightarrow A \rightarrow (B = A) \rightarrow B$)