ความปลอดภัยของ ECDLP โดยใช้เส้นโค้งวงรีบนฟิลด์ส่วนขยาย

เป็นที่รู้จักกันว่าสำหรับเส้นโค้งวงรี $E$ กำหนดไว้ในฟิลด์สำคัญ $\mathbb{F}_p$ ดังนั้น $E(\mathbb{F}_p)$ เป็นจำนวนเฉพาะ อัลกอริทึมที่ดีที่สุด (นอกเหนือจากบางกรณี) สำหรับการแก้ลอการิทึมแบบไม่ต่อเนื่องเป็นจำนวนทั่วไปสำหรับกลุ่มอาเบเลียน: Baby-steps Giant-steps, Pollard rho, Kangaroo

สำหรับเส้นโค้งวงรีที่กำหนดผ่านส่วนขยายของฟิลด์มีวิธีแคลคูลัสดัชนีอยู่ อัลกอริธึมที่มีประสิทธิภาพมากที่สุดสองรายการคือ

1. หนึ่งใน Gaudry และ Diem ซึ่งควรจะมีความซับซ้อนตาม Joux และ Vitse, $O(n!\cdot2^{3n(n-1)}\cdot p^{2-2/n})$. สิ่งนี้ใช้ได้จริงตาม Joux และ Vitse เฉพาะสำหรับ $n\leq 4$.
2. Joux กับ Vitse ตัวไหนเห็นผลกว่ากันครับ $n\geq 5$: มันมีค่าใช้จ่าย $\tilde O((n-1)!\cdot (2^{(n-1)(n-2)}\cdot e^n\cdot n^{-1/2})^\omega\cdot p ^2)$.

การประมาณการเหล่านั้นอาจดูคร่าวๆ แต่ดูเหมือนว่าในทางปฏิบัตินั้นประสิทธิภาพจะน้อยกว่าอัลกอริทึมทั่วไป ตัวอย่างเช่นใช้สำหรับ $p\sim 2^{64}$ และ $n=4$. อัลกอริธึม Gaudry และ Diem จะมีค่าใช้จ่าย $O(4!\cdot 2^{36+96})$โดยเฉลี่ยแล้วแย่กว่า $O(\sqrt{p^n})$ซึ่งเป็นต้นทุนของอัลกอริทึมทั่วไป

สมมติอย่างนั้นเหมือนกัน $\โอเมก้า=2$ (กรณีแง่ดี), $p\sim 2^{51}$, $n=5$ ในอัลกอริทึมที่สอง เราจะมีค่าเท่ากับ $O(4!\cdot2^{24}\cdot e^{10}\cdot\frac{1}{5}\cdot 2^{102})\simeq O(2^{142.69})$ซึ่งแย่กว่าค่าประมาณสำหรับอัลกอริทึมทั่วไป

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