เราจะบอกได้อย่างไรว่าวิทยาการเข้ารหัสลับแบบหนึ่งแข็งแกร่งกว่าอีกแบบหนึ่ง

ใครสามารถช่วยฉันเข้าใจสิ่งนี้: เราจะพูดได้อย่างไรว่าการเข้ารหัสแบบดั้งเดิมนั้นแข็งแกร่งกว่าอีกอันหนึ่ง

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

วิธีดั้งเดิมในการแสดงนั้น $คิว$ หมายถึง $พี$ เป็นทางก การลดกล่องดำ ของ $พี$ ถึง $คิว$: เช่น.,

• แสดงประสิทธิภาพก่อน การก่อสร้าง $C^{(\cdot)}$ ที่ให้การเข้าถึงกล่องดำกับทุกอินสแตนซ์ (ไม่จำเป็นต้องมีประสิทธิภาพ) $\mathsf{Q}$ ของ $คิว$ให้ผลตอบแทนเช่น $\mathsf{P}=C^{\mathsf{Q}}$ ของ $พี$; และ
• แล้วแสดงประสิทธิภาพ การลดความปลอดภัย $\mathsf{R}^{(\cdot)}$ ที่ให้การเข้าถึงกล่องดำกับศัตรูทุกคน (ไม่จำเป็นต้องมีประสิทธิภาพ) $\mathsf{A}_P$ ที่แบ่ง $\mathsf{P}$, ยอมเป็นปฏิปักษ์ $\mathsf{A}_Q$ ที่แบ่ง $\mathsf{Q}$.

เพื่อดูว่ามีการเข้ารหัสคีย์สาธารณะ $(\mathsf{G},\mathsf{E},\mathsf{D})$ หมายถึงฟังก์ชันทางเดียว (เช่น) ตั้งอัลกอริทึมการสร้างคีย์เป็นฟังก์ชันทางเดียว เช่น $\mathsf{F}(1^n,r):=pk$, ที่ไหน $(pk,sk):=\mathsf{G}(1^n;r)$.

ในทางกลับกัน เพื่อแสดงให้เห็นว่า $พี$ ไม่ หมายความว่า $คิว$ หนึ่งต้องออกกฎ ทั้งหมด การลดลงของ $คิว$ ถึง $พี$เช่น แสดง ก การแยก. เช่นเพื่อแสดงว่า $พี$ ไม่ได้หมายความว่า $คิว$ ด้วยการลดขนาดกล่องดำ ก็เพียงพอแล้วที่จะอธิบายถึงคำทำนาย $\mathcal{O}$ เช่นนั้นดั้งเดิม $พี$ มีอยู่สัมพันธ์กับ $\mathcal{O}$, แต่ ทั้งหมด ตัวอย่างของ $คิว$ แตกหัก ตั้งแต่การลดกล่องดำ สัมพัทธ์การลดดังกล่าวไม่สามารถเกิดขึ้นได้ มีการแสดงไว้ใน [IR] ว่าฟังก์ชันแบบทางเดียวไม่ได้หมายความถึงการเข้ารหัสคีย์สาธารณะผ่านการลดขนาดกล่องดำ (ซึ่งถือว่าไม่สำคัญอย่างยิ่ง)

คุณสามารถอ่านเพิ่มเติมเกี่ยวกับรสชาติต่างๆ ของการลดและการแยกได้ใน [RTV]

[IR]: อิมพาเกลียซโซ และ รูดิช ข้อจำกัดเกี่ยวกับผลลัพธ์ที่พิสูจน์ได้ของการเรียงสับเปลี่ยนทางเดียว,สตอค'89.

[RTV]: เรนโกลด์ เทรวิซาน และวาดฮัน แนวคิดของการลดลงระหว่าง Cryptographic Primitives,TCC'04.