ใน นี้ กระดาษ ("โครงร่างลายเซ็นที่หุ้มฉนวนกุญแจที่แข็งแกร่ง" โดย Dodis, Katz, Xu, Yung (2002)) ฉันเข้าใจหลักฐานส่วนใหญ่สำหรับบทแทรก 1 (หน้า 9); ฉันต่อสู้กับวิธีการคำนวณความน่าจะเป็นบางอย่าง
ฉันคิดว่าไม่จำเป็นต้องอ่านกระดาษสิ่งที่คุณต้องมีดังต่อไปนี้:
บริบท
- ปฏิปักษ์ $A$ แบ่ง ("ใหม่") โครงการ $\ปี่$
- ชาเลนเจอร์ $A'$ ต้องการทำลายโครงร่างพื้นฐาน $\เธต้า$ โดยใช้ $A$
- การลงนาม oracle ใช้เป็นอินพุตข้อความและ ระยะเวลา $i$
- เดอะ จำนวนข้อความค้นหาสูงสุด สำหรับการลงนาม oracle คือ $q(k)$
ส่วนที่สับสน:
เมื่อถึงจุดหนึ่งผู้ท้าชิง $A'$ วาดแบบสุ่ม $r \in \{1,..,q(k)\}$ แล้วดูที่ $r^{th}$ ลงชื่อแบบสอบถามว่า $A$ ทำให้.
- หากข้อความค้นหานี้มีระยะเวลาที่ใช้ในข้อความค้นหาการเซ็นชื่อก่อนหน้านี้เป็นอินพุต ให้ยกเลิกการทดสอบ
- หากเป็นครั้งแรกที่ช่วงเวลานี้ (แสดงแทน $i^*$) ถูกสอบถาม ดำเนินการต่อ
- ถ้า $A$ สอบถามหรือสอบถามออราเคิล "การเปิดเผยคีย์" ได้ตลอดเวลา $i^*$ยกเลิกด้วย (การเปิดเผยคีย์ = การเปิดเผยคีย์ลับสำหรับช่วงเวลาที่สอบถาม)
ในที่สุด, $A$ ปลอมลายเซ็นในช่วงเวลาหนึ่ง $i$. (ปรับตัว ฉันคิดว่า, ดังนั้น $i$ ไม่ถูกกำหนดไว้ในตอนต้น แต่ A เลือกไว้ตอนท้าย)
จากนั้นกระดาษเขียนว่า:
ด้วยความน่าจะเป็นเป็นอย่างน้อย $1/q(k)$, การทดสอบจะไม่ถูกยกเลิกและ $i^â = ฉัน$ [..].
ฉันเดา
$P(\text{การทดสอบไม่ถูกยกเลิก } \wedge\, i^â = i) =\
P(\text{period }i^* \text{ไม่ได้สอบถามก่อน } r^{th} \text{เซ็นชื่อแบบสอบถาม } \wedge\, \text{ไม่มีการค้นหาคีย์สำหรับ }i^* \wedge\, i^ â = ฉัน )$
อะไรตอนนี้? ฉันไม่เห็นว่าการคำนวณนี้จะชัดเจนได้อย่างไร ฉันนึกถึงคำถามมากมาย:
- เหตุการณ์เหล่านั้นเป็นอิสระทั้งหมดหรือไม่ $P(\text{period }i^* \text{ไม่ได้สอบถามก่อน } r^{th} \text{เซ็นชื่อแบบสอบถาม } \wedge\, \text{ไม่มีการค้นหาคีย์สำหรับ }i^* \wedge\, i ^â = i ) = P(\text{period }i^* \text{not query before } r^{th} \text{signing query })*P(\text{no key exposurequery for }i ^*)*P( i^â = i )?$
- เป็น $P( i^â = i )=1/q(k)$ หรือมีความเป็นไปได้สูงกว่าที่ฝ่ายตรงข้ามเลือก $i$ สำหรับการปลอมแปลงที่พวกเขารู้บางอย่างเกี่ยวกับ (= ที่พวกเขาเคยสอบถามมาก่อน)? หรือเราคิดไปเองว่า $A$แบบสอบถามเป็นแบบสุ่ม? ทำไมเราถึงคิดอย่างนั้น?
- เป็น $P(\text{period }i^* \text{ไม่ได้สอบถามก่อน } r^{th} \text{ลงชื่อแบบสอบถาม })$ เหมือนกันสำหรับทุกคน $r$ หรือสูงกว่าสำหรับขนาดเล็ก $r$ (แบบสอบถาม = "ต้น")? ขึ้นอยู่กับว่า $P( ฉัน^â = ฉัน )$?
ฉันงุนงงจริง ๆ ที่ความน่าจะเป็นนี้ได้รับโดยไม่มีคำอธิบายเพิ่มเติม ฉันต้องขาดอะไรพื้นฐานไป คุณสามารถช่วย?