Score:1

การเชื่อมโยงการตัดสินใจ Diffie-Hellman, ลอการิทึมแบบไม่ต่อเนื่องและความรู้เกี่ยวกับสมมติฐานที่เป็นเลขยกกำลัง

ธง yt

ฉันสงสัยเกี่ยวกับความสัมพันธ์ระหว่างลอการิทึมแบบไม่ต่อเนื่องกับดิฟฟี-เฮลแมนเชิงตัดสินใจ ปลอดภัยไหมที่จะมีข้อสันนิษฐานดังต่อไปนี้เพื่อเชื่อมโยงทั้งสอง

ให้ g^x และ g^y ที่เลือกอย่างสม่ำเสมอและเป็นอิสระต่อกัน หากมีอัลกอริธึมที่มีประสิทธิภาพที่สามารถแยกความแตกต่างของ g^(xy) และสุ่ม g^r ด้วยความน่าจะเป็นที่ไม่มีนัยสำคัญ จากนั้นจะมีตัวแยกที่สามารถแยก x หรือ y ด้วย ความน่าจะเป็นที่ไม่สำคัญ?

ดูเหมือนว่าจะเป็นความรู้เรื่องเลขชี้กำลัง แต่ฉันต้องการให้มันจัดการกับปัญหาการตัดสินใจ นอกจากนี้ เป็นที่ทราบกันดีว่ากลุ่มเส้นโค้งวงรีบางกลุ่มสามารถใช้การจับคู่เพื่อทำลาย DDH ในกรณีนี้ เราจะจำกัดการสนทนาไว้เฉพาะกลุ่ม เช่น กลุ่มของเศษซากกำลังสองเหนือจำนวนเต็ม Blum

Score:0
ธง cn

ฉันคิดว่าการทำลิงค์นี้ไม่ธรรมดาเลย

เหตุผลที่ดีคือ ตัวอย่างเช่น กลุ่ม bilinear ที่มีการจับคู่แบบสมมาตร (ประเภท 1) สามารถพิจารณาได้ว่าปลอดภัยสำหรับข้อสันนิษฐานแบบแยกส่วน แต่จะไม่เป็นเช่นนั้นสำหรับข้อสันนิษฐาน DDH

หากคุณได้รับ $(g,x,y,z)$คุณสามารถตรวจสอบได้อย่างง่ายดายว่า $e(g,z)=e(x,y)$และความเท่าเทียมกันนี้ก็เพียงพอแล้วที่จะตัดสินว่าเป็นทูเพิลของดิฟฟี-เฮลล์แมนหรือไม่

หากต้องการดูเหตุผลเชิงทฤษฎีเพิ่มเติม คุณสามารถดูข้อสันนิษฐาน Gap-DH (ในปัญหานี้ ฝ่ายตรงข้ามต้องแก้ไขอินสแตนซ์ CDH ด้วย DDH oracle) : ดังนั้นจึงแสดงให้เห็นว่าหากสำหรับฝ่ายตรงข้ามเกี่ยวกับพีชคณิต หาก DLog ถืออยู่ Gap-DH ก็เป็นปัญหาหนักเช่นกัน (ดังนั้น หากคุณแทนที่อินสแตนซ์ CDH ด้วยอินสแตนซ์ DLog ก็จะยิ่งยากขึ้น)

คุณสามารถดูหน้า phd 136 สำหรับรายละเอียดเพิ่มเติม

https://www.iacr.org/phds/index.php?p=detail&entry=1476

และเนื่องจากการพิจารณาศัตรูเชิงพีชคณิตสำหรับฉันแล้วดูเหมือนว่าจะเทียบเท่ากับสมมติฐานความรู้ของเลขยกกำลัง ดังนั้นการสร้างลิงก์ดังกล่าวจึงค่อนข้างแปลก (เท่าที่ฉันเข้าใจ มันจะบอกเป็นนัยว่า Dlog นั้นง่าย แต่ฉันไม่แน่ใจทั้งหมดเกี่ยวกับ นั่น).

Sean avatar
yt flag
ขอบคุณสำหรับข้อมูลเชิงลึก!
Sean avatar
yt flag
ทีนี้ จะเกิดอะไรขึ้นถ้าเราจำกัดการสนทนาไว้เฉพาะกลุ่มที่เชื่อว่าปัญหา DDH นั้นยาก (เช่น กลุ่มที่ไม่ใช่ Gap_DH)
Ievgeni avatar
cn flag
ฉันไม่เข้าใจคุณหมายถึงอะไร. แต่อย่าลังเลที่จะถามคำถามใหม่กับโพสต์อื่น มันจะชัดเจนกว่า
Sean avatar
yt flag
ฉันโพสต์คำถามอื่นตามด้านล่าง สิ่งนี้อธิบายว่าทำไมฉันจึงต้องเชื่อมโยงกับความรู้เรื่องสมมติฐานเลขชี้กำลัง
Sean avatar
yt flag
ลิงค์อยู่ด้านล่าง: https://crypto.stackexchange.com/questions/91834/decisional-diffie-hellman-assumption-over-group-of-quadratic-residue

โพสต์คำตอบ

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