เป็นไปได้ไหมที่คีย์อื่นจะถอดรหัสได้อย่างถูกต้อง?

ฉันกำลังคิดเกี่ยวกับความปลอดภัย CPA สำหรับการเข้ารหัสแบบสมมาตร

ดังนั้น $A$ เข้าถึงออราเคิลการเข้ารหัส และสามารถถามคำถามต่อไปได้ (ขั้นตอนการฝึกอบรม) ในขั้นตอนการฝึกอบรมนี้เขาถาม $m_i$ และรับกลับ $y_i$. นอกจากนี้ เขายังสามารถตรวจสอบได้ว่าสามารถหาคีย์ที่จะถอดรหัสเป็นข้อความเดียวกับที่เขาเข้ารหัสได้หรือไม่ เพียงแค่ตรวจสอบว่า $\Pi.\mathsf{ธ.ค.}(k, y_i) = m_i$ สำหรับบางคน $k$ นั่น $A$ คาดเดา เขายังสามารถทำสิ่งเดียวกันในระหว่างขั้นตอนการท้าทายและดูว่า $y^*$ เขาได้ถอดรหัสกลับไปทั้งสองอย่าง $m_0,m_1$.

ตอนนี้เดาได้เลยว่าหายาก $k$ (สุ่มเลือกอย่างสม่ำเสมอ) แต่เป็นไปได้ไหมที่จะหารหัสอื่น $k'$ ที่เกิดขึ้นกับแบบสอบถามการฝึกอบรมบางอย่าง? ฉันเดาว่าสิ่งนี้ไม่ควรเกิดขึ้นด้วยความน่าจะเป็นที่น้อยมากหาก $\ปี่$ CPA ปลอดภัยหรือไม่ แต่อาจเกิดขึ้นได้ใช่ไหม

คำถามของฉันอาจคล้ายกับ: เป็นไปได้ไหมที่จะถอดรหัสข้อความเข้ารหัสด้วยคีย์ส่วนตัวอื่น

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

มีคำถามว่าช่องว่างระหว่างข้อได้เปรียบของการค้นหาคีย์ที่สอดคล้องกันและความได้เปรียบของการค้นหาคีย์เป้าหมายนั้นห่างกันเพียงใด ฉันพบการบรรยายของ Bellare ที่พูดถึงประเด็นนี้ (แต่ไม่มีการเขียนเป็นลายลักษณ์อักษร) ในการบรรยายนั้น เบลแลร์กล่าวว่าช่องว่างนั้นแทบจะไม่มีเลย (เช่น ข้อดีเกือบเท่าๆ กัน) ถ้ารหัสบล็อกเป็นรหัสรหัสจริง (เช่น AES) เขากล่าวว่าข้อสรุปดังกล่าวขึ้นอยู่กับหลักฐานฮิวริสติกหรือเชิงประจักษ์ หากข้อดีเกือบจะเหมือนกัน หมายความว่าคีย์เป้าหมายเป็นคีย์เดียวที่สอดคล้องกับการค้นหาอินพุต-เอาต์พุต แต่ในทางทฤษฎี คีย์ที่สอดคล้องกัน (แตกต่างจากคีย์เป้าหมาย) เป็นไปได้และสามารถกู้คืนได้ก่อนที่จะกู้คืนคีย์เป้าหมาย คุณสามารถดูทั้งหมด การบรรยาย เพราะฉันแน่ใจว่าเบลลาเรสามารถอธิบายได้ดีกว่าฉันมาก