กำหนด 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$ ช่วยทำให้เร็วขึ้นไหม?