ฮาร์ดอินสแตนซ์หมายถึงอะไรในการเข้ารหัส

"ฮาร์ดอินสแตนซ์" หมายถึงปัญหาที่ยากต่อการแก้ไข เช่น ข้อสันนิษฐานของ DDH (Decisional Diffie Hellman) หรือไม่

โดยทั่วไปใช่ มันหมายถึงเฉพาะ ตัวอย่าง ของปัญหาที่ยาก ตัวอย่างเช่น ในกรณี DDH หมายถึงความท้าทายเฉพาะอย่างหนึ่ง $(g^a, g^b, g^c)$.

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

การลดมักเริ่มต้นด้วยการได้รับอินสแตนซ์ของปัญหาหนัก เช่น ปัญหา DDH จากนั้นคุณจะพูดว่า "สมมุติว่า $\mathcal{A}$ เป็นปฏิปักษ์/อัลกอริทึมที่สามารถทำลายโปรโตคอล XXX ได้อย่างได้เปรียบ $\epsilon$" ต่อไป คุณจะแสดงวิธีเปลี่ยนอินสแตนซ์ของปัญหา DDH $g^a, g^b, g^c$ เป็นคุณค่าที่คุณมอบให้ได้ $\mathcal{A}$ดังนั้นไม่ว่าอะไรก็ตาม $\mathcal{A}$ คุณจะได้เรียนรู้คำตอบของอินสแตนซ์ DDH (อาจมีความเป็นไปได้ต่ำกว่า $\epsilon$ซึ่งเรียกว่า "สูญเสียความรัดกุม") นี่เป็นวิธีการเปลี่ยนอินสแตนซ์ DDH ให้เป็นสิ่งที่คุณสามารถมอบให้ได้ $\mathcal{A}$ ที่เรียกว่า "การฝัง" ตัวอย่างของปัญหา DDH ลงในโปรโตคอลของคุณ

แต่คุณจะต้องหาความน่าจะเป็น และถ้าคุณสามารถแสดงให้เห็นว่าคุณได้เปรียบในการแก้ปัญหา DDH โดยใช้ $\mathcal{A}$ เป็นสิ่งที่ไม่สำคัญหาก $\epsilon$ คือ แสดงว่าคุณได้แสดงการลดความปลอดภัยของโปรโตคอลจาก DDH เรียบร้อยแล้ว