Score:1

แสดงว่า $F'(k, x) := F(F(k, 0^{n}), x)$ เป็น PRF

ธง jp

ฉันต้องการฝึกฝนการพิสูจน์การลดความปลอดภัย และฉันก็งงกับสิ่งนี้จากหนังสือ Boneh-Shoup

ถ้า $F(k, x)$ เป็น PRF ที่ปลอดภัยแล้วแสดงว่า $F'(k, x) := F(F(k, 0^{n}), x)$ เป็น PRF ที่ปลอดภัย

สิ่งที่ฉันมีคือ:

สมมติ $F'$ ไม่ปลอดภัยด้วยความแตกต่าง $D'$. นี่หมายความว่า $F$ ยังไม่ปลอดภัยด้วยตัวแยก $D$. ตอนนี้ฉันจะแสดงโครงสร้าง $D$ โดยใช้ $D'$.

  1. $D$ รับกุญแจ, $k$.
  2. $D$ เริ่มทำงาน $D'$.
  3. เมื่อไหร่ก็ตาม $D'$ สอบถาม oracle ในข้อความ $x \leftarrow \lbrace0,1\rbrace^{n}$, ให้ $x$ ถึง $D$,คำนวณ $y:= O(x)$, ที่ไหน $O$ เป็น $D$ออราเคิลของ จากนั้นส่ง $F(F(k, y), x)$ ถึง $D'$.
  4. เอาท์พุทอะไรก็ตาม $D'$ เอาต์พุต

ซึ่งหมายความว่า:

ราคา[$D'^{F'}(1^{n}) = 1] =$ ราคา[$D^{F}(1^{n}) = 1]$ และ Pr[$D'^{r}(1^{n}) = 1] =$ ราคา[$D^{r}(1^{n}) = 1]$, ที่ไหน $r$ เป็นฟังก์ชันสุ่ม เช่นกัน,

$|$$[D^{F}(1^{n}) = 1] - Pr[D^{r}(1^{n}) = 1]| > $ ละเลย ($n$)

โดยสันนิษฐาน. อย่างไรก็ตามตั้งแต่ $F$ เป็น PRF นี่เป็นความขัดแย้งดังนั้น $F'$ เป็น PRF $\สแควร์$

หลักฐานนี้สมเหตุสมผลหรือไม่? ฉันรู้สึกว่าฉันสับสนในการกำหนด $D$, แต่ฉันไม่แน่ใจ. ขอบคุณสำหรับความช่วยเหลือ!

Fractalice avatar
in flag
เหตุใด $D$ จึงได้รับรหัส คุณมี $F(F(k,y),x)$ ส่งไปที่ $D'$ (โดย $y=F(k, x)$) ในขณะที่แยกความแตกต่างของรูปร่าง $F(F(k,0) x)$. คุณสามารถแก้ไขได้หรือไม่? คุณต้องโต้แย้งด้วยว่าเหตุใดสิ่งที่คุณส่งไปยัง $D'$ จึง "เหมือนสุ่ม" ในเมื่อ $F(k, .)$ เป็นแบบสุ่ม
ness64 avatar
jp flag
@Fractalice อืม แทนที่จะเป็น $y=O(x)$ มันจะเป็น $y=O(0^{n})$ แล้ว $D$ ส่ง $F(y,x)$ ถึง $D '$? ฉันเดาว่าแทนที่จะได้รับแท็ก $D$ สามารถคำนวณ $y = O(0^{n})$ ในขั้นตอนที่ 1

โพสต์คำตอบ

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