TLDR: ถ้าเราเชี่ยวชาญจุดกำเนิด $G$ ของกลุ่ม Elliptic Curve ของลำดับเฉพาะ เราสามารถทำได้อย่างสม่ำเสมอ กำหนด GCD ของสองจุดสำหรับตัวสร้างนั้น แต่เราไม่สามารถมีประสิทธิภาพ หา สำหรับจุดโดยพลการและกลุ่มความสนใจในการเข้ารหัสซึ่งปัญหาลอการิทึมแบบไม่ต่อเนื่องนั้นยาก
ก่อนจะหาอะไร เราต้องรู้ก่อนว่ามันคืออะไร ดังนั้นคำถามย่อยของปอนโช:
'GCD ของสองจุดบนเส้นโค้งที่สำคัญ' หมายถึงอะไร
GCD ย่อมาจากตัวหารร่วมมาก ดังนั้นเราจึงจำเป็นต้องกำหนดแนวคิดสามประการ
- "เส้นโค้งเฉพาะ" คืออะไร ในเรื่องนี้, เส้นโค้ง หมายถึง เส้นโค้งวงรี. และ นายกรัฐมนตรี เป็นคุณสมบัติของอย่างใดอย่างหนึ่ง
- ฐาน เขตข้อมูล จำกัดคำสั่งของ (คำสั่งสำคัญนั้นมักจะถูกบันทึกไว้ $p$แล้วเขตข้อมูลเป็นเพียงโมดูโลจำนวนเต็ม $p$);
- ลำดับของเส้นโค้ง นั่นคือ จำนวนองค์ประกอบใน กลุ่มที่แน่นอน ของจุดต่างๆ ของเส้นโค้ง รวมถึงความเป็นกลาง
- หรือคำสั่งของก กลุ่มย่อย ของเส้นโค้ง (แล้วมักจะสังเกตว่า $n$แล้วแต่เราจะทำ)
- แนวคิดของ "ตัวหาร" ของจุดหนึ่งของเส้นโค้งวงรีเฉพาะ ซึ่งเราจะถือว่าเป็นจุดของเส้นโค้งวงรีที่มีคุณสมบัติบางอย่างที่จะกำหนด
- แนวคิดเรื่อง "ยิ่งใหญ่ที่สุด" ในบรรดาจุดต่างๆ ของเส้นโค้งวงรี
เราสามารถกำหนดสิ่งนั้นได้อย่างสม่ำเสมอ! เราตั้งสมมติฐานว่า "เส้นโค้งเฉพาะ" คือกลุ่มย่อยของคำสั่งเฉพาะ $n$ ของเส้นโค้งวงรี (อาจเป็นเส้นโค้งทั้งหมด ซึ่งสามารถใช้ฟิลด์เฉพาะได้ เช่น secp256k1, secp256r1), และ $G$ จุดที่กำหนดของเส้นโค้ง / องค์ประกอบของกลุ่ม นอกเหนือจากค่าที่เป็นกลาง ตอนนี้ชุดของ $n$ จำนวนเต็มใน $[0,น)$ คือ isomorphic กับเส้นโค้ง โดย isomorphism เล็กน้อย $i\mapsto i\,G$ กำหนดตามปกติ: $0\,G$ เป็นกลางของกลุ่ม $i\,G$ เป็น $((i-1)\,G)+G$ สำหรับใดๆ $i\in[1,n)$ กับ $+$ กฎหมายของกลุ่ม
เราสามารถกำหนด "ตัวหาร" และ "มากที่สุด" บนชุด $[0,น)$. และเราสามารถกำหนด GCD ของสององค์ประกอบของชุดนั้นได้ $\gcd(0,0)=0$ ). จากนั้นเราสามารถใช้ isomorphism นี้เพื่อกำหนดตัวหารร่วมมากของจุดสองจุดของกลุ่ม Elliptic Curve ของลำดับเฉพาะที่มีจุดกำเนิด $G$.
กล่าวอีกนัยหนึ่ง ฉันกำหนด GCD ของคะแนน $พี$ และ $คิว$ เป็นจุดที่จับคู่คีย์ส่วนตัว (สำหรับตัวสร้าง $G$) คือ GCD ของคีย์ส่วนตัวที่ตรงกัน $พี$ และ $คิว$, กับ จับคู่คีย์ส่วนตัว จำนวนเต็มใน $[0,น)$.
หากเราสามารถแก้ปัญหาลอการิทึมแบบไม่ต่อเนื่องในกลุ่มที่พิจารณาได้อย่างมีประสิทธิภาพ เราก็สามารถคำนวณ GCD ได้อย่างมีประสิทธิภาพ (เราแก้ DLP สองตัว คำนวณ GCD ของจำนวนเต็ม และกลับไปที่เส้นโค้ง)
อัปเดต: การสนทนาเป็นจริงในระดับหนึ่ง หากเราสามารถคำนวณ GCD ได้อย่างมีประสิทธิภาพ ใดๆ สองจุด $พี$ และ $คิว$จากนั้นเราสามารถใช้อัลกอริทึมนั้นเพื่อคำนวณลอการิทึมแบบไม่ต่อเนื่องได้อย่างมีประสิทธิภาพ $i$ แต่อย่างใด $พี$. Sketch: เราเลือกจำนวนเฉพาะแรก $r_j$ จนกระทั่ง $n<\ผลิตภัณฑ์ r_j$และสำหรับแต่ละคน $เจ$ เราพบ $i\bmod r_j$ โดยขอ GCD ของ $(P+k\,G,r_j\,G)$ ซึ่งเป็นอย่างใดอย่างหนึ่ง $G$ หรือ $r_j\,G$โดยภายหลังได้เปิดเผยว่า $i+k\equiv0\pmod{r_j}$. แล้วเราจะพบว่า $i$ โดยทฤษฎีบทส่วนที่เหลือของจีน การปรับให้เหมาะสมเป็นไปได้เพื่อจัดกลุ่มข้อความค้นหาจำนวนมากเป็นหนึ่งเดียว เช่น. ส่ง $(P+k\,G,30\,G)$ และทดสอบว่าผลเป็นอย่างไร $G$, $2\,G$, $3\,G$, $5\,G$, $6\,G$, $10\,G$, $15\,G$ หรือ $30\,G$. การลดขนาดเพิ่มเติมทำได้โดยการคำนวณลอการิทึมแบบไม่ต่อเนื่องของเอาต์พุตของ oracle โดยใช้ Baby-Step/Giant-Step ที่ต่างกัน
ฉันไม่รู้จักแอปพลิเคชันใด ๆ ในการเข้ารหัสหรืออย่างอื่น