Score:3

ข้อสันนิษฐานของ Diffie-Hellman ที่ตัดสินใจเกี่ยวกับกลุ่มของสารตกค้างกำลังสอง

ธง yt

พิจารณาการตัดสินใจ Diffie-Hellman (DDH) มากกว่า $QR_n$ (กลุ่มกากกำลังสองทับ $n=pq$ ที่ไหน $p$ และ $คิว$ เป็นจำนวนเฉพาะที่ปลอดภัย) ตามเอกสารของ Boneh DDH ควรจะหนักกว่า $QR_n$ (https://link.springer.com/chapter/10.1007/BFb0054851):

[DDH] ได้รับสามตัวอย่างสุ่ม $g^x, g^y, g^z$ เป็นการยากที่จะบอกว่า $z = x*y$.

ฉันสงสัย: ถ้าได้รับพิเศษ $x^2$ $mod$ $n$ปัญหานี้ยังคงยากอยู่ $QR_n$? (สัญชาตญาณคือการคำนวณรากของ $x^2$ เป็นเรื่องยาก สี่เหลี่ยมจัตุรัสนี้จึงไม่ควรให้ข้อมูลเพิ่มเติมสำหรับการแก้ DDH ข้อยกเว้นอาจเป็นการรั่วไหลของสัญลักษณ์ Jacobi/Legendre แต่เป็นการสุ่มเลือก $z$ แก้ไขให้สอดคล้องกันได้หรือไม่).

Ievgeni avatar
cn flag
ให้ $x^2$ หรือ $g^{x^2}$?
poncho avatar
my flag
"โดยสัญชาตญาณแล้วสี่เหลี่ยมนี้ไม่ควรรั่วไหลของข้อมูลเพิ่มเติม"; จริง ๆ แล้ว จากมุมมองความสามารถในการพิสูจน์ได้ ตรงกันข้าม - ถ้ามันคำนวณได้ง่าย มันจะไม่รั่วไหลอะไรเลย (ผู้โจมตีสามารถคำนวณได้เอง ดังนั้นการให้ค่าแก่ผู้โจมตีไม่ได้บอกอะไรเขาเลย' t รู้แล้ว) ตัวอย่างที่ชัดเจนที่สุด ค่า $g^{xy}$ ก็คำนวณยากเช่นกัน แต่การให้ค่านั้นก็ทำให้ปัญหาของผู้โจมตีกลายเป็นเรื่องเล็กน้อย ฉันไม่ได้บอกว่าการให้ค่า $g^{x^2}$ ทำให้ปัญหาของผู้โจมตีง่ายขึ้น ฉันกำลังบอกว่ามันไม่สำคัญที่จะแสดง
Sean avatar
yt flag
กำหนด $x^2$ (ไม่ใช่ $g^{x^2}$) ดังนั้นคำถามของฉันคือ: หากได้รับ $x^2$ พิเศษนี้ การตัดสินใจของ DH จะยังยากอยู่หรือไม่ (ในบริบทของกลุ่มสารตกค้างกำลังสอง)
Ievgeni avatar
cn flag
แต่เราสามารถคำนวณรากที่สองของ $x^2$ ใน $\mathbb{R}$ ได้อย่างง่ายดาย และหนึ่งในรากเหล่านี้จะเท่ากับ $x^2$ ดังนั้นจึงง่ายต่อการตรวจสอบว่าเป็น ddh-tuple หรือไม่
Geoffroy Couteau avatar
cn flag
คำถามน่าคิด! ฉันไม่เห็นการลดสมมติฐานมาตรฐานอย่างเห็นได้ชัด คำแนะนำ: คุณสามารถเริ่มต้นด้วยการพิจารณาปัญหาในเวอร์ชันที่ง่ายขึ้น โดยกำหนด $x^2 \bmod \phi(n)/4$ งานของคุณคือแยกแยะ $g^x$ จากองค์ประกอบสุ่มของ $\mathsf {QR}_n$
Sean avatar
yt flag
เกี่ยวกับความคิดเห็นของ levgeni: แต่ใน $QR_n$, $n$ นี้เป็นส่วนประกอบของ RSA จากนั้นการพยายามหารากของเศษซากกำลังสองจะเทียบเท่ากับการแยกตัวประกอบ $n$ ดูเอกสาร eurocrypt17 ของ Couteau เช่น: https://link.springer.com/chapter/10.1007/978-3-319-56614-6_11
Sean avatar
yt flag
นี่คือคำถามที่คล้ายกันที่ฉันโพสต์เมื่อวานนี้: -- มันสร้างความแตกต่างหรือไม่ที่โมดูลัสคือ $\phi(n)/4$ หรือ $n$ https://crypto.stackexchange.com/questions/91786/group-of-quadratic-residue-over-blum-integer
Sean avatar
yt flag
ฉันเห็นจุดของ $\phi(n)/4$ แล้ว -- สำหรับ $x$ บนเลขชี้กำลังของ $g^x$ ความยากอยู่ที่ว่าหากเปิดเผย totient $\phi(n)$ แล้ว $n$ จะถูกแยกตัวประกอบ สิ่งที่เราทำได้คือขอให้เซิร์ฟเวอร์ที่เชื่อถือได้จัดเตรียม $r \phi(n)$ โดยที่ $r$ เป็นจำนวนเต็มสุ่มจำนวนมาก ด้วยวิธีนี้ จะได้ค่า $x^2$ ที่เท่ากัน ส่วน $r \phi(n)$ ดังนั้นปัญหาจึงเปลี่ยนไปเล็กน้อยเป็น: \n ให้ $x^2 \mod \phi(n)/4*r$ โดยที่ $r$ และ $\phi(n)$ ไม่รู้จัก เป็นไปได้ไหมที่จะแยกแยะ $g^ x$ ด้วยอัลกอริทึมที่มีประสิทธิภาพ?

โพสต์คำตอบ

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