Score:0

จำนวนสมาชิก EC $P^3+c$ กับ 3 gen $G$, $F = P\cdot G,H=P^2\cdot G$ และสมาชิกแบบสุ่ม 2 ตัว $M_1+iG+jF+kH=M_2$ ใช้เวลานานเท่าใดในการหา $i,j,k$?

ธง at

กำหนด EC ด้วยจำนวนสมาชิก $C=P^3+c$ กับ $พี$ นายกรัฐมนตรี $P \ประมาณ \sqrt[3]{C}$ และ $ค>0$. จากเครื่องกำเนิดไฟฟ้าที่กำหนด $G$ เราสร้างเครื่องกำเนิดไฟฟ้าเพิ่มเติมสองเครื่อง $F,H$ กับ $$F = P \cdot G$$ $$H = P^2 \cdot G$$

(ทั้งหมดจะยังคงสร้างลำดับของความยาว $P^3+ค$)
รับสมาชิกสุ่ม $M_1$ ของ EC นั้น เราสามารถสร้าง $P\times P \times P$ ลูกบาศก์ของสมาชิกที่แตกต่างกันด้วย $$ M_1 +i\cdot G+j\cdot F+k\cdot H = V_{M_1ijk}$$ $$ i,j,k \ใน [0,P-1]$$ $$|\{V_{M_1ijk}\}| = P^3$$

สมาชิกสุ่มคนอื่น ๆ ทุกคน $M_2$ สามารถผลิตได้จาก $M_1$ กับ: $$M_2 = M_1+i\cdot G+j\cdot F+k\cdot H $$ $$ i,j,k \ใน [0,P]$$


คำถาม:
ให้สมาชิกสุ่มสองคน $M_1,M_2 $ ต้องใช้กี่ขั้นตอนในการค้นหาสิ่งที่เกี่ยวข้อง $i,j,k$ (ตามเวลาเฉลี่ย)? วิธีที่จะทำงาน?
จะปลอดภัยกว่า (มาก) ไหมถ้าเราเลือก $P = 2\cdot p+1$ กับ $p$ นายกรัฐมนตรี?
จะปลอดภัยกว่า (มาก) หรือไม่ หากเราเลือกปัจจัยหลัก (ลับ) สามประการ $P_1,P_2,P_3$ แทน? กับ $P_1 \cdot P_2 \cdot P_3 \ประมาณ C$

(ฉันกำลังมองหาค่าประมาณคร่าวๆที่เกี่ยวข้องกับ $C,P$ ใน ($O$-สัญกรณ์). เราสามารถเช่น ละเว้นผลกระทบที่เกี่ยวข้องกับความยาวบิตที่แตกต่างกันที่การคูณ 2 จำนวน )


ศัตรู ไม่ทราบเกี่ยวกับ EC ที่ใช้แล้ว เครื่องปั่นไฟ $G,F,H$ และผกผันของพวกเขา $G^{-1},F^{-1},H^{-1}$, สมาชิกสุ่ม $M_1,M_2$ และโครงสร้างภายใน เขาไม่รู้เรื่อง $P,d$ แต่เนื่องจากมีตัวเลือกไม่มากนัก เราถือว่าเขารู้เรื่องนี้เช่นกัน
เขาต้องการค้นหาที่ไม่รู้จัก $i,j,k$ สำหรับการสุ่มที่รู้จักกัน $M_1,M_2$.


คำถามด้านข้าง: มีข้อจำกัดใดๆ ของ EC ที่ปลอดภัยที่สามารถใช้สำหรับสิ่งนี้หรือไม่? เช่น. จะใช้ M-221 กับ $y^2 = x^3+117050x^2+x$ $\bmod p = 2^{221} - 3$ ทำงานนี้?


การทดลอง:
ถ้าเรามีเครื่องปั่นไฟเพียงเครื่องเดียว $G$ มันควรจะใช้เวลา $O(\sqrt{C})$ โดยใช้ขั้นตอนทารกขั้นตอนยักษ์ ถ้า $พี$ เป็นที่รู้จัก $i,j,k$ สามารถสร้างได้จากสิ่งนี้
กับ $F,H$ เราสามารถทำพื้นผิวรอบๆ $M_1$ และเป็นเส้นตรงด้วย $G$ ที่ $M_2$ จนถึงทางแยกเหล่านั้น สิ่งนี้จะใช้เวลา $O(P^2+P)\ลูกศรขวา O(P^2)$ ซึ่งจะมีขนาดใหญ่กว่า $O(\sqrt{C})=O(P\sqrt{P})$. ดังนั้น $F,H$ ไม่มีความช่วยเหลือที่นี่
เครื่องกำเนิดไฟฟ้าเหล่านั้นได้ $F,H$ ช่วยทำให้เร็วขึ้นไหม?

Score:1
ธง my

ให้สมาชิกสุ่มสองคน $M_1, M_2$ ต้องใช้กี่ขั้นตอนในการค้นหาสิ่งที่เกี่ยวข้อง $i,j,k$ (ตามเวลาเฉลี่ย)?

ปัญหาในการหา $i, j, k$ เทียบเท่ากับปัญหาบันทึกแยก:

  • หากคุณสามารถแก้ปัญหาบันทึกแยกได้ คุณก็สามารถคำนวณได้ $i, j, k$ (โดยการคำนวณล็อกแบบไม่ต่อเนื่องของ $M_2 - M_1$แล้วแสดงฐานการเข้าสู่ระบบแบบไม่ต่อเนื่องนั้น $พี$)

  • ถ้าคุณสามารถคำนวณได้ $i, j, k$คุณสามารถแก้ปัญหาบันทึกแยกได้ (ในการคำนวณบันทึกแยกของจุด M คุณจะเลือกจุดใดก็ได้ $M_1$, ชุด $M_2 = M + M_1$,คำนวณ $i, j, k$; จากนั้นบันทึกแบบไม่ต่อเนื่องของ $M$ เป็น $i + jP + kP^2$

สำหรับเส้นโค้งที่ไม่มีจุดอ่อนที่ทราบ เชื่อกันว่าการคำนวณบันทึกแบบไม่ต่อเนื่องนั้นต้องใช้ $O(\sqrt{C})$ เวลา; หากคุณเลือกเส้นโค้งที่มีจุดอ่อนที่ทราบ (เช่น เส้นโค้งที่เป็นมิตรในการจับคู่ซึ่งมีการดำเนินการจับคู่กับฟิลด์จำกัดที่บันทึกแยกได้ง่ายกว่า) เวลาในการแก้ปัญหาของคุณก็จะลดลงตามไปด้วย

โพสต์คำตอบ

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