Score:3

เราสามารถหา GCD ของสองจุดบนเส้นโค้งได้หรือไม่?

ธง ca

ในทางคณิตศาสตร์ เป็นไปได้ไหมที่จะหา GCD ของจุดสองจุดบนเส้นโค้งเฉพาะ ซึ่งจุดหนึ่งไม่มีลำดับเหมือนที่คุณทำใน Extended Euclidean Algorithm

poncho avatar
my flag
'GCD ของสองจุดบนเส้นโค้งที่สำคัญ' หมายถึงอะไร
meshcollider avatar
gb flag
ไม่มีสิ่งที่เรียกว่า "การหาร" หรือ "การคูณ" ของจุดบนเส้นโค้ง ดังนั้นจึงไม่มี "ตัวหารร่วมมาก"
Score:3
ธง ng

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 ที่ต่างกัน

ฉันไม่รู้จักแอปพลิเคชันใด ๆ ในการเข้ารหัสหรืออย่างอื่น

meshcollider avatar
gb flag
คุณตีความว่าเป็น GCD ของ "กุญแจลับ" หรือไม่?
fgrieu avatar
ng flag
@meshcollider : โดยพื้นฐานแล้วใช่และฉันขโมยสูตรของคุณในการแก้ไขคำตอบพร้อมคำใหม่ที่ทำให้ GCD ของคะแนนเป็นจุด
poncho avatar
my flag
สองสิ่ง: 1) คำจำกัดความของ "GCD ของสองจุด" ดังกล่าวจะขึ้นอยู่กับว่า $G$ คืออะไร" (หากเราเลือก $G$ ที่แตกต่างกัน GCD ของสองจุดจะแตกต่างกัน) 2) ให้ฟังก์ชันที่คำนวณ GCD ตามที่กำหนด เราสามารถคำนวณ DLog ได้อย่างมีประสิทธิภาพ (จึงไม่ง่ายไปกว่าปัญหา DLog)
fgrieu avatar
ng flag
@poncho: 1) ใช่ และฉันดูแลที่จะระบุด้วย "ให้ด้วยจุดกำเนิด $G$" (คำแปลเบื้องต้นของ _muni d'un générateur_ ซึ่งจะมีความหมายที่ต้องการในภาษาฝรั่งเศส แต่ฉัน ไม่รู้ว่าเป็นภาษาอังกฤษเข้าใจไหม) 2) ขอบคุณ ตอนแรกฉันไม่รู้ ฉันอัปเดตคำตอบพร้อมหลักฐาน แต่ก็ไม่แน่น: ต้องการให้เราสามารถคำนวณ GCD ของสองจุด $P$ และ $Q$ ได้อย่างมีประสิทธิภาพ ฉันสงสัยว่าสิ่งนี้สามารถปรับปรุงได้หรือไม่และอย่างไร
Score:2
ธง lu

เวอร์ชันสั้นคือคุณไม่สามารถกำหนด 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

kodlu avatar
sa flag
คำตอบของคุณขัดแย้งกับคำตอบอื่นหรือไม่? โปรดแสดงความคิดเห็น
G. Stergiopoulos avatar
lu flag
สองสิ่ง. อันดับแรก ฉันให้คำตอบที่ชัดเจนสำหรับคำถามเดิมว่าทำไมคุณไม่สามารถสร้างอัลกอริทึมที่เหมาะสมสำหรับ GCD ได้ โดยอธิบายว่าทำไม/วิธีที่คุณไม่สามารถถ่ายโอนอัลกอริทึมแบบยุคลิดไปยังกลุ่มเส้นโค้งวงรีบนฟิลด์จำกัดได้เนื่องจากขาดคำจำกัดความที่เหมาะสม ของระยะทาง. ฉันเชื่อว่าสิ่งนี้ไม่ได้มาจากคำตอบแรกที่อธิบายอย่างละเอียดว่าอัลกอริทึมเป็นอย่างไร แต่ไม่ได้ให้คำตอบจริง ๆ ว่าสิ่งนี้สามารถเกิดขึ้นได้จริงหรือไม่ [ต่อ]
G. Stergiopoulos avatar
lu flag
[ต่อ] ประการที่สอง ฉันขอยืนยันว่าคุณไม่สามารถ _define_ GCD ของสองจุดตามที่ระบุไว้ในคำตอบก่อนหน้าได้ เนื่องจากคำจำกัดความต้องแม่นยำอย่างเข้มงวดโดยยึดตามชุด/กฎเฉพาะที่ฉันร่างไว้ที่นี่ นั่นคือ เนื่องจากระยะทางหรือการเปรียบเทียบองค์ประกอบที่สั่งไม่ได้ ถูกกำหนดแล้วคำตอบก่อนหน้าไม่ใช่คำจำกัดความ แต่เป็นทฤษฎี (แม้ว่าจะเป็นความคิดที่รอบคอบ)
kodlu avatar
sa flag
ขอบคุณสำหรับความคิดเห็นที่กว้างขวางของคุณ
poncho avatar
my flag
นอกจากนี้ หากเรามีวิธีที่กำหนด $[j]G$, $[k]G$ พิจารณาว่า $j > k$ เราสามารถใช้สิ่งนั้นเพื่อคำนวณบันทึกแยกได้อย่างมีประสิทธิภาพ (โดยใช้การค้นหาแบบไบนารี) ดังนั้นเราจึง หวังว่าจะเป็นปัญหาหนัก
G. Stergiopoulos avatar
lu flag
ถูกต้อง @poncho แต่ฉันค่อนข้างแน่ใจ ตามที่ได้อธิบายไว้ในคำตอบว่า (อย่างน้อยปัญหานี้) ไม่สามารถแก้ไขได้อย่างแน่นอนโดยใช้การแปลงที่รู้จัก
fgrieu avatar
ng flag
ฉันยอมรับว่าเราไม่สามารถกำหนดระยะทางหรือตัวหาร ดังนั้น GCD บนเส้นโค้งวงรี _alone_ แต่เราทำได้ถ้าเราเพิ่มจุดกำเนิด $G$ (หมายความว่ามันเป็นเส้นโค้งของคำสั่งเฉพาะ) ระยะห่างระหว่าง $P$ และ $Q$ บนเส้นโค้งคือจำนวนเต็มที่น้อยที่สุด $d\in[0,\lfloor n/2\rfloor)$ โดยที่ $P=Q+d\,G$ หรือ $Q=P +d\,G$ $P$ หาร $Q$ ด้วย $P/Q=R$ iif มีอยู่ $u,v,w\in[0,n)$ ด้วย $P=u\,G$, $Q=v\,G$, $R=w\,G$, $v\ne0$ และ $u=v\,w$
G. Stergiopoulos avatar
lu flag
เราไม่สามารถกำหนดระยะทางได้แม้จะใช้เครื่องกำเนิดไฟฟ้าเป็นจุดอ้างอิงก็ตาม ให้ฉันอธิบาย สิ่งที่คุณกำลังอธิบายคือแนวคิดของระยะทางในตัวคูณ _scalar_ ซึ่งไม่เหมือนกับระยะทางของจุดสองจุด GCD ของจุดบนเส้นโค้งต้องการแนวคิดของการเปรียบเทียบบนระนาบ อย่างมีประสิทธิภาพ การเปรียบเทียบสเกลาร์เป็นการแปลงรูปแบบหนึ่งในเรื่องนี้ แต่อย่างที่ฉันอธิบายในคำตอบของฉัน อย่างน้อยก็จนกว่าจะรู้ การวัดระยะทางในระนาบเชิงซ้อนหรือจำนวนเต็มในเขตข้อมูลจำกัดนั้นเป็นไปไม่ได้ และนี่คือเหตุผลที่แท้จริงว่าทำไมการเปรียบเทียบแบบสเกลาร์ของคุณจึงไม่สามารถกำหนด GCD บนเส้นโค้งได้
fgrieu avatar
ng flag
ฉันไม่เห็นอะไรผิดปกติกับคำจำกัดความที่ฉันให้ไว้ในคำตอบหรือในความคิดเห็น (ขยาย) ก่อนหน้าของฉัน [อัปเดต]: ฉันยอมรับว่านี่คือ _not_ a GCD บนเส้นโค้ง แต่เป็น GCD บนเส้นโค้งที่ใช้ตัวสร้างเฉพาะ ฉันยอมรับว่าไม่มีวิธีที่มีประสิทธิภาพในการคำนวณ GCD นี้ ตรงกันข้ามกับ GCD ปกติ เว้นแต่ว่า DLP จะง่ายสำหรับกลุ่มที่พิจารณา และฉันยอมรับว่าฉันไม่เห็นการประยุกต์ใช้กับแนวคิดนี้
G. Stergiopoulos avatar
lu flag
มันไม่ได้เกี่ยวกับคำตอบของคุณว่าผิด แนวทางอัลกอริทึมของคุณนั้นถูกต้องในทางทฤษฎี ฉันตอบว่า *ทำไม* คุณไม่สามารถหาวิธีใช้วิธีการของคุณเพื่อสร้าง GCD ที่ใช้งานได้จริง เหตุผลทางคณิตศาสตร์พื้นฐานเนื่องจากข้อจำกัดทางเรขาคณิต และสิ่งที่ผู้เชี่ยวชาญในสาขานี้ (ซิลเวอร์แมน) ทำในการค้นหาคำตอบนี้ข้อโต้แย้งทางคณิตศาสตร์ของฉันคือสิ่งที่ Silverman พูดเกี่ยวกับระยะทาง ข้อโต้แย้งที่สองของฉันคือคำตอบของคุณเป็นอัลกอริทึมเชิงทฤษฎีและไม่ใช่คำจำกัดความของ GCD ตามที่อธิบายไว้ในความคิดเห็นก่อนหน้า

โพสต์คำตอบ

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