Score:2

การทำลาย CDH ยังทำลาย DHI

ธง mp

ฉันกำลังพยายามแสดงสิ่งนั้นโดยการทำลาย สมมติฐานการคำนวณ Diffie-Hellmann (CDH) หนึ่งยังทำลาย สมมติฐานผกผันของ Diffie-Hellmann. น่าเสียดายที่ฉันติดขัดเล็กน้อยและไม่รู้ว่าจะไปที่ไหน ฉันสงสัยว่าคุณสมบัติ bilinearity จากกลุ่มจับคู่ที่กำหนดโดย $พีจีเจน$ เป็นความผิด แต่ฉันไม่ทราบแน่ชัดว่าจะแก้ไขปัญหาต่อไปอย่างไร คำจำกัดความมีดังนี้

ด้วย Computational Diffie-Hellman (CDH) ที่กำหนดโดยที่ปรึกษา PPT A โดยที่: $Adv^{cdh}_{PGGen,A}(n)$ เล็กน้อยและ:

$Adv^{cdh}_{PGGen,A}(n) := Pr[Z = g^{xy} \กลาง PG \stackrel{$}{\gets} PGGen(1^n); x, y \stackrel{$}{\gets} \mathbb{Z}_p ; Z \stackrel{$}{\gets} A(PG, g^x, g^y)]$

และสมมติฐานผกผัน Diffie-Hellmann (DHI) ที่กำหนดโดย PPT ฝ่ายตรงข้าม A โดยที่: $Adv^{q-dhi}_{PGGen,A}(n)$ เล็กน้อยและ:

$Adv^{q-dhi}_{PGGen,A}(n) := Pr[Z = g^{1/x} \mid PG \stackrel{$}{\gets} PGGen(1^n); x, y \stackrel{$}{\gets} \mathbb{Z}_p ; Z \stackrel{$}{\gets} A(PG, g^x)]$

ความช่วยเหลือใด ๆ และทั้งหมดจะได้รับการชื่นชมอย่างมาก

Score:3
ธง cn

หากคุณสามารถทำลาย CDH ได้ แสดงว่าคุณสามารถสร้างทั้งหมดได้อย่างมีประสิทธิภาพ $g^{x^u}$ สำหรับทุกอย่าง $i$ เชิงบวกโดยการรวมการยกกำลังอย่างรวดเร็วเข้ากับ Oracle ของ CDH

$$g^{1/x} = \begin{กรณี} EXP(G',u) = g & \text{if } u=0 \ EXP(CDH(G'),u/2) & \text{if } u \text{ เป็นเลขคู่}\ CDH(G', EXP(G',u-1)) & \text{if } u \text{ เป็นเลขคี่}\ \end{กรณี}$$

จากนั้นเราสามารถคำนวณ $g^{x^{p-2}}= g^{x^{p-2} \mod p}= g^{x^{p-2}}= g^{\frac{1}{x } \mod p}$. จากนั้นคุณสามารถทำลาย DHI

kelalaka avatar
in flag
ฉันคิดว่าวิธีที่ง่ายที่สุดคือแสดงว่า DHI เทียบเท่ากับ Square DH...
poncho avatar
my flag
@kelalaka: อย่างไรก็ตาม สิ่งที่ดีของแนวทาง $g^{x^{q-2}}$ คือมันทำงานได้อย่างหมดจดแม้ว่า Oracle ของคุณจะได้รับการแก้ไขเป็น $g$ เฉพาะ

โพสต์คำตอบ

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