ความปลอดภัยที่พิสูจน์ได้: การลดลงที่เป็นไปไม่ได้เมื่อข้อความถูกเข้ารหัส/การรักษาความปลอดภัยเชิงความหมายพร้อมฟังก์ชันที่ขึ้นอยู่กับผลลัพธ์ของฝ่ายตรงข้าม

ฉันมีปัญหากับโปรโตคอลที่ฉันสามารถพิสูจน์ความปลอดภัยได้หากข้อความที่ส่งโดยฝ่ายตรงข้ามนั้นชัดเจน แต่ฉันไม่สามารถพิสูจน์ความปลอดภัยได้อีกต่อไปหากข้อความที่ส่งโดยฝ่ายตรงข้ามนั้นถูกเข้ารหัส... และสิ่งนี้ ค่อนข้างแปลกเพราะฉันคาดว่าโปรโตคอลจะปลอดภัยในกรณีที่สองนั้นด้วย

แม่นยำยิ่งขึ้น ฉันกำลังพิจารณาโปรโตคอลที่ Bob เซิร์ฟเวอร์ได้รับข้อความ $k$ จากอลิซ (สามารถมองได้ว่าเป็นการเข้ารหัสของสตริงบิต $d_0$ ภายใต้รหัสลับสาธารณะ $t_k$) และส่งข้อความกลับ $y$ (ซึ่งสามารถมองได้ว่าเป็นการเข้ารหัสของบางข้อความ $x$ ภายใต้ รหัสสาธารณะเดียวกัน $k$ ของอลิซ: ไม่ใช่ว่าเนื่องจากรูปร่างของโปรโตคอลฉันจำเป็นต้องใช้คีย์เดียวกันนี้จริงๆ) ในหลักฐานการรักษาความปลอดภัย ฉันต้องการแสดงว่าไม่มี Bob ที่เป็นอันตรายคนใดสามารถค้นหาค่าลับได้ $\theta_\pi=f(x,d_0)$ ที่ควรดูสุ่มเป็นอย่างอื่น

ข่าวดีก็คือถ้าฉันรู้ $x$ฉันสามารถกลับด้านได้ $f$ และค้นหา $d_0$. ดังนั้นหาก Bob ที่เป็นอันตรายรู้ $x$ฉันสามารถทำการลดลงเพื่อพิสูจน์ว่าถ้า Bob สามารถหาได้ $\theta_\pi$ พวกเขาบ็อบก็รู้เช่นกัน $d_0 = f^{-1}(x,\theta_\pi)$: นี่เป็นข้อขัดแย้งเนื่องจากการเข้ารหัสนั้นปลอดภัย IND-CPA

น่าเสียดายที่การลดลงนี้ใช้ไม่ได้เพราะ Bob ที่เป็นอันตรายอาจ "ไม่รู้" $x$: พวกเขาส่งเฉพาะเวอร์ชันที่เข้ารหัสเท่านั้น $y$ ของมัน: และในระหว่างการลดขนาด ฉันไม่สามารถถอดรหัสสิ่งนี้ได้ $y$ เนื่องจากอลิซเท่านั้นที่รู้จักกุญแจนี้ (กรณีของฉันหลีกเลี่ยงไม่ได้)...

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

แก้ไข

เพื่อตอบ Mikero ฉันคิดว่าในข้อโต้แย้งของคุณ เราต้องพูดทำนองนี้:

หากเราจัดการได้ช่องที่ถูกต้อง ฉันยอมรับว่าการพิสูจน์จะตามมาอย่างง่ายดาย แต่ฉันไม่แน่ใจว่าจะพิสูจน์ความเท่าเทียมกันระหว่างสองสถานการณ์นี้ได้อย่างไร ฉันไม่คิดว่านี่เป็นการลดการรักษาความปลอดภัย IND-CPA โดยตรง เนื่องจากตัวแยกสัญญาณยังสามารถเข้าถึงได้ $\theta_\pi$ ซึ่งเชื่อมโยงกับข้อมูลบางอย่างเกี่ยวกับการถอดรหัสของ $y$. ฉันเดาว่าจะเป็นการดีที่จะแสดงว่าไดอะแกรมแรกเทียบเท่ากับ

แต่ไม่แน่ใจว่าจะพิสูจน์ได้อย่างไร (แน่นอน $Ideal Func_1$ แตกต่างจาก $Ideal Func_3$คำถามคือเมื่อเราเพิ่มตัวจำลองไว้ด้านบน)