TLDR: ถ้าเราเชี่ยวชาญจุดกำเนิด $G$ ของกลุ่ม Elliptic Curve ของลำดับเฉพาะ เราสามารถทำได้อย่างสม่ำเสมอ กำหนด GCD ของสองจุดสำหรับตัวสร้างนั้น แต่เราไม่สามารถมีประสิทธิภาพ หา สำหรับจุดโดยพลการและกลุ่มความสนใจในการเข้ารหัสซึ่งปัญหาลอการิทึมแบบไม่ต่อเนื่องนั้นยาก
ก่อนจะหาอะไร เราต้องรู้ก่อนว่ามันคืออะไร ดังนั้นคำถามย่อยของปอนโช:
'GCD ของสองจุดบนเส้นโค้งที่สำคัญ' หมายถึงอะไร
GCD ย่อมาจากตัวหารร่วมมาก ดังนั้นเราจึงจำเป็นต้องกำหนดแนวคิดสามประการ
เราสามารถกำหนดสิ่งนั้นได้อย่างสม่ำเสมอ! เราตั้งสมมติฐานว่า "เส้นโค้งเฉพาะ" คือกลุ่มย่อยของคำสั่งเฉพาะ $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 ที่ต่างกัน
ฉันไม่รู้จักแอปพลิเคชันใด ๆ ในการเข้ารหัสหรืออย่างอื่น
เวอร์ชันสั้นคือคุณไม่สามารถกำหนด GCD ของจุดได้ เนื่องจากจะต้องกำหนดแนวคิดที่ชัดเจนเกี่ยวกับการเปรียบเทียบลำดับของจุดก่อน เช่น วิธีการทดสอบ $[k]P > [j]P , k>j$ และ $P \ใน E$, ที่ไหน $E$ คือชุดของจุดที่กำหนดโดยเส้นโค้งวงรีและตัวสร้างที่เกี่ยวข้อง $พี$.
การเปรียบเทียบคำสั่งดังกล่าวเกี่ยวข้องกับแนวคิดของระยะห่างระหว่าง $[k]P$ และ $[j]P$ ภายในช่องว่างที่กำหนด เกี่ยวกับระยะทางในสนามจำกัดด้วยองค์ประกอบ p $F_p$ ที่ไหน $E$ กำหนดไว้ น่าเสียดายที่เราไม่สามารถเปรียบเทียบระยะทางได้แต่อย่างใด $F_p$.
ดังที่ Silverman ได้กล่าวไว้ มีวิธีที่ดีในการกำหนดระยะห่างระหว่างองค์ประกอบใน $Z_p$ และ $Q_p$แต่ไม่มีวิธีที่ดีในการกำหนดระยะห่างระหว่างองค์ประกอบของ $F_p$หรือสำหรับจุดบนเส้นโค้งวงรีที่มีพิกัดอยู่ $F_p$.
มีแผนที่ธรรมชาติ $E(Q_p) ถึง E(F_p)$ แต่น่าเสียดายที่ไม่มีแผนที่กลับด้านที่ดีจริงๆ Silverman กล่าวถึงเรื่องนี้ในเอกสารต่อไปนี้ ในบริบทของการพยายามยกขึ้นแล้วใช้การยกเพื่อแก้ปัญหา ECDLP
ยกและเส้นโค้งวงรีแยกลอการิทึม, พื้นที่ที่เลือกของการเข้ารหัส (SAC 2008), เอกสารประกอบการบรรยายในวิทยาการคอมพิวเตอร์ 5381, Springer--Verlag, Berlin, 2009, 82-102
คนส่วนใหญ่ไม่เข้าใจว่าการถามคำถามมากมายจะปลดล็อกการเรียนรู้และปรับปรุงความสัมพันธ์ระหว่างบุคคล ตัวอย่างเช่น ในการศึกษาของ Alison แม้ว่าผู้คนจะจำได้อย่างแม่นยำว่ามีคำถามกี่ข้อที่ถูกถามในการสนทนา แต่พวกเขาไม่เข้าใจความเชื่อมโยงระหว่างคำถามและความชอบ จากการศึกษาทั้ง 4 เรื่องที่ผู้เข้าร่วมมีส่วนร่วมในการสนทนาด้วยตนเองหรืออ่านบันทึกการสนทนาของผู้อื่น ผู้คนมักไม่ตระหนักว่าการถามคำถามจะมีอิทธิพลหรือมีอิทธิพลต่อระดับมิตรภาพระหว่างผู้สนทนา
