ไอโซจีนีของเส้นโค้งวงรี: พื้นฐานทางคณิตศาสตร์

ไอโซเจนีระหว่างเส้นโค้งวงรี E และ E' เหนือฟิลด์ k คือการแมปเชิงตรรกยะที่ไม่คงที่ phi: E -> E' ซึ่งเป็นโฮโมมอร์ฟิซึมของกรุปด้วย — กล่าวคือแมปกฎการดำเนินการของกรุปจาก E ไปยังกรุปของ E' ไอโซเจนี phi ทุกตัวมีไอโซเจนีคู่ phi_hat: E' -> E โดยที่ phi_hat ประกอบกับ phi เท่ากับการคูณด้วย deg(phi) บน E ดีกรีของไอโซเจนีเท่ากับขนาดของเคอร์เนล: ไอโซเจนีดีกรี l มีเคอร์เนลขนาด l ไอโซเจนีทำให้แนวคิดการคูณสเกลาร์เป็นกรณีทั่วไปมากขึ้น: การคูณด้วย n เป็นไอโซเจนีจาก E ไปยังตัวมันเองที่มีดีกรี n^2 ไอโซเจนีเหนือฟิลด์จำกัดคำนวณได้ในรูปฟังก์ชันตรรกยะ (พหุนาม) ซึ่งสามารถประเมินค่าได้อย่างมีประสิทธิภาพ

สูตรของ Velu (1971) ให้สูตรที่ชัดเจนสำหรับคำนวณไอโซเจนี phi: E -> E/G เมื่อกำหนดกลุ่มย่อย G ของ E เส้นโค้งภาพ E/G = E' และการแมปเชิงตรรกยะ phi ถูกกำหนดโดย G อย่างสมบูรณ์ สูตรของ Velu คำนวณสัมประสิทธิ์ของเส้นโค้งภาพและการแมปเชิงตรรกยะในรูปฟังก์ชันตรรกยะที่มีดีกรีเท่ากับ |G| สำหรับกลุ่มย่อยเคอร์เนล G ที่มีอันดับเฉพาะ l ไอโซเจนีจะมีดีกรี l และคำนวณได้ด้วยการดำเนินการ O(l) รายการ อัลกอริทึม sqrt-Velu (Bernstein และคณะ, 2019) ลดจำนวนนี้เหลือการดำเนินการ O(sqrt(l)) รายการสำหรับ l ขนาดใหญ่ ทำให้ไอโซเจนีของจำนวนเฉพาะขนาดใหญ่ใน CSIDH มีประสิทธิภาพ สูตรของ Velu เป็นกลไกหลักด้านการคำนวณของคริปโตกราฟีที่อิงไอโซเจนีทั้งหมด

เส้นโค้งวงรีเหนือฟิลด์จำกัด Fp สามารถจัดระบบเป็นกราฟไอโซเจนีได้ จุดยอดคืออินวาเรียนต์ j ของเส้นโค้งวงรี (อินวาเรียนต์มาตรฐานที่กำหนดเส้นโค้งได้จนถึงอิซอมอร์ฟิซึม) ส่วนเส้นเชื่อมคือ l-ไอโซเจนี: เส้นโค้งแบบสามัญแต่ละเส้นมี l-ไอโซเจนีขาออกจำนวน l+1 รายการพอดีสำหรับจำนวนเฉพาะ l ขนาดเล็ก (ตามโครงสร้างของกลุ่มย่อย l-ทอร์ชัน) กราฟ l-ไอโซเจนีเหนือ Fp จึงเป็นกราฟแบบสม่ำเสมอระดับ (l+1) สมบัติ Ramanujan ของกราฟเหล่านี้ (กราฟขยาย) หมายความว่าการเดินสุ่มบนกราฟผสมกันอย่างรวดเร็ว ซึ่งให้สมมติฐานความยากที่อยู่เบื้องหลังคริปโตกราฟีที่อิงไอโซเจนี: การเดินสุ่มความยาว O(log p) ให้การแจกแจงสม่ำเสมอเหนืออินวาเรียนต์ j

เส้นโค้งวงรีเหนือ Fp แบ่งออกเป็นสองประเภท เส้นโค้งแบบสามัญมีอันดับ p ที่ไม่เป็นศูนย์ ซึ่งหมายความว่ามีคลาสของอิซอมอร์ฟิซึมจำนวน p^2 คลาส และมีกราฟไอโซเจนีที่ซับซ้อนในรูปโครงสร้างภูเขาไฟ (ปล่องและชั้นพื้น) เส้นโค้งซูเปอร์ซิงกูลาร์มีอันดับ p เท่ากับ 0 และทั้งหมดอยู่ในกราฟไอโซเจนีที่เชื่อมต่อกันเพียงกราฟเดียวเหนือ Fp2 จำนวนอินวาเรียนต์ j ของเส้นโค้งซูเปอร์ซิงกูลาร์เหนือ Fp มีค่าประมาณ p/12 SIDH และ SIKE ใช้เส้นโค้งซูเปอร์ซิงกูลาร์ เนื่องจากกราฟไอโซเจนีของเส้นโค้งเหล่านี้เป็นกราฟ Ramanujan ที่มีคุณสมบัติการขยายตัวสูง และไม่มีโครงสร้างภูเขาไฟที่อาจเปิดเผยทิศทางการเดินได้ CSIDH ก็ใช้เส้นโค้งซูเปอร์ซิงกูลาร์เช่นกัน แต่ใช้เหนือ Fp (ไม่ใช่ Fp2) โดยอาศัยโครงสร้างพีชคณิตที่แตกต่างกัน

คริปโตกราฟีที่อิงไอโซเจนีตั้งอยู่บนปัญหายากสองปัญหาที่เกี่ยวข้องกัน ปัญหาไอโซเจนีของเส้นโค้งซูเปอร์ซิงกูลาร์ (SSIP): เมื่อกำหนดเส้นโค้งวงรีซูเปอร์ซิงกูลาร์สองเส้น E และ E' เหนือ Fp2 ให้หาไอโซเจนี phi: E -> E' ปัญหาไอโซเจนีของเส้นโค้งซูเปอร์ซิงกูลาร์เชิงคำนวณ (CSSI): เมื่อกำหนด E, E' = phi(E) และดีกรีของ phi ให้หา phi อัลกอริทึมแบบคลาสสิกที่ดีที่สุดสำหรับ SSIP ใช้เวลา O(p^{1/4}) อัลกอริทึมควอนตัมที่ดีที่สุด (การค้นหากรงเล็บของ Tani) ใช้เวลา O(p^{1/6}) เมื่อ p = 2^{434} จะให้ความปลอดภัยแบบคลาสสิก 128 บิต การเร่งความเร็วด้วยควอนตัมนี้ด้อยกว่าการเร่งความเร็วแบบเลขชี้กำลังของอัลกอริทึมของ Shor ที่โจมตี RSA/ECC อย่างมาก ทำให้แบบแผนที่อิงไอโซเจนีมีความปลอดภัยหลังยุคควอนตัม

SIDH (Supersingular Isogeny Diffie-Hellman) ใช้จำนวนเฉพาะที่มีโครงสร้างเฉพาะ p = 2^a * 3^b - 1 ซึ่งรับประกันว่าเส้นโค้ง E เหนือ Fp2 มีจุดทอร์ชัน 2^a (เซตของจุด P ที่ 2^a * P = 0) และมีจุดทอร์ชัน 3^b ที่เข้าถึงได้ ความลับของ Alice คือไอโซเจนี 2^a phi_A: E -> E_A ซึ่งมีเคอร์เนลสร้างโดยสมาชิกสุ่มของจุดทอร์ชัน 2^a ความลับของ Bob คือไอโซเจนี 3^b phi_B: E -> E_B ทั้งสองฝ่ายแลกเปลี่ยนภาพของจุดทอร์ชัน: Alice เผยแพร่ E_A และ phi_A(P_B), phi_A(Q_B) ส่วน Bob เผยแพร่ E_B และ phi_B(P_A), phi_B(Q_A) ทำให้แต่ละฝ่ายคำนวณไอโซเจนีจากเส้นโค้งของอีกฝ่าย และได้อินวาเรียนต์ j ที่ใช้ร่วมกันเป็นค่าเดียวกัน

ริงเอนโดมอร์ฟิซึม End(E) ของเส้นโค้งวงรีคือริงของไอโซเจนีทั้งหมดจาก E ไปยังตัวมันเอง (รวมการคูณสเกลาร์ด้วย) สำหรับเส้นโค้งแบบสามัญเหนือ Fp, End(E) เป็นออร์เดอร์ในฟิลด์กำลังสองเชิงจินตภาพ สำหรับเส้นโค้งซูเปอร์ซิงกูลาร์ End(E) เป็นออร์เดอร์สูงสุดในพีชคณิตควอเทอร์เนียนที่แรมิฟายเหนือ p และอนันต์ โครงสร้างของ End(E) กำหนดเส้นโค้งได้อย่างสมบูรณ์จนถึงอิซอมอร์ฟิซึม ปัญหาริงเอนโดมอร์ฟิซึม — การคำนวณ End(E) เมื่อกำหนด E — เชื่อกันว่าเป็นปัญหายาก (เทียบเท่ากับ SSIP สำหรับเส้นโค้งซูเปอร์ซิงกูลาร์) การโจมตีของ Castryck-Decru ต่อ SIDH/SIKE ใช้ข้อมูลเพิ่มเติมที่รั่วไหลจากโพรโทคอล SIDH เพื่อสร้างส่วนหนึ่งของริงเอนโดมอร์ฟิซึมขึ้นใหม่ได้อย่างมีประสิทธิภาพ และทำลายแบบแผนดังกล่าว

ไอโซเจนีดีกรี l phi: E -> E' สามารถแทนด้วยพหุนามดีกรี l (หรือ l/2 หลังปรับให้เหมาะสมด้วยสมมาตร โดยใช้ข้อเท็จจริงที่ว่าจุดผกผันมีพิกัด x เดียวกัน) การคำนวณ phi(P) สำหรับจุด P ที่กำหนดใช้การคูณ O(l) รายการด้วยสูตรของ Velu สำหรับ SIDH ที่ l = 2^a ซึ่งมีค่าประมาณ 2^216 วิธีนี้ดูเหมือนใช้ทรัพยากรมากเกินไป แต่ SIDH ใช้ข้อเท็จจริงที่ว่าไอโซเจนี 2^a สามารถแยกเป็นสายโซ่ของไอโซเจนี 2 รายการจำนวน a รายการได้ — ไอโซเจนี 2 แต่ละรายการมีต้นทุนต่ำ และสายโซ่ยาว a ขั้นจะสร้างไอโซเจนี 2^a ในทำนองเดียวกันก็ใช้กับ 3^b ได้ อัลกอริทึม sqrt-Velu ทำให้การคำนวณไอโซเจนีของจำนวนเฉพาะคี่ขนาดใหญ่ใน CSIDH ทำได้ด้วยการดำเนินการ O(sqrt(l)) แทน O(l) ทำให้ CSIDH ใช้งานได้จริง

SIKE (Supersingular Isogeny Key Encapsulation) เป็นผู้สมัครของ NIST ในการแข่งขัน PQC ที่ผ่านมาทุกระยะจนถึงรอบที่สี่ ซึ่งเป็นช่วงที่ถูกทำลาย SIKE มีจุดเด่นด้านขนาดคีย์ที่เล็กที่สุดในบรรดาผู้สมัครของ NIST ทั้งหมด: 374 ไบต์สำหรับ SIKEp434 (ระดับ 1 ของ NIST) เมื่อเปรียบเทียบกัน ML-KEM-512 มีคีย์สาธารณะขนาด 800 ไบต์ SIKE มีขนาดกะทัดรัดเช่นนี้ได้เพราะความลับที่ใช้ร่วมกันสร้างจากอินวาเรียนต์ j เพียงค่าเดียว (สมาชิกของฟิลด์ขนาดประมาณ ~430 บิต) ความกะทัดรัดนี้แลกมาด้วยประสิทธิภาพที่ต่ำกว่า: SIKE ช้ากว่าผู้สมัครอื่น 100-1000 เท่า เมื่อ Castryck และ Decru ทำลาย SIKE ในเดือนกรกฎาคม 2022 ด้วยการโจมตีแบบคลาสสิกที่ทำงานเสร็จภายในไม่กี่นาทีบนแล็ปท็อป SIKE ก็ถูกตัดออกจากการแข่งขันของ NIST ทันที

คริปโตกราฟีที่อิงไอโซเจนีมีตำแหน่งเฉพาะในบรรดาแนวทางหลังยุคควอนตัม ขนาดคีย์: เล็กกว่าแบบที่อิงแลตทิซมาก (ML-KEM: มากกว่า 800 ไบต์) หรือแบบลายเซ็นที่อิงแฮช (SLH-DSA: คีย์สาธารณะ 32-49 ไบต์ แต่ลายเซ็นมีขนาด 7856-49856 ไบต์) ประสิทธิภาพ: ช้ากว่าทางเลือกทั้งหมดมาก (SIKE ช้ากว่า ML-KEM 100-1000 เท่า) สมมติฐานด้านความปลอดภัย: แตกต่างจาก LWE (ที่ใช้ใน ML-KEM/ML-DSA), SIS หรือฟังก์ชันแฮช จึงให้ความหลากหลายทางคริปโตกราฟี พื้นฐานความปลอดภัยหลังยุคควอนตัม: ปัญหาเส้นทางไอโซเจนียังไม่มีอัลกอริทึมควอนตัมแบบเวลาพหุนามที่เป็นที่รู้จัก แตกต่างจาก RSA/ECC ซึ่งอัลกอริทึมของ Shor สามารถทำลายได้อย่างสมบูรณ์ การโจมตีแบบคลาสสิกที่ทำลาย SIKE แสดงให้เห็นว่ายังมีการทำความเข้าใจความยากของไอโซเจนีไม่ครบถ้วน แตกต่างจากปัญหา LWE ที่มีการศึกษาอย่างกว้างขวาง

แม้ SIKE จะถูกทำลายแล้ว แต่คริปโตกราฟีที่อิงไอโซเจนียังคงเป็นสาขาวิจัยที่มีการดำเนินงานอย่างต่อเนื่อง SQISign (Short Quaternion and Isogeny Signature) เป็นแบบแผนลายเซ็นที่อิงไอโซเจนีซึ่งมีลายเซ็นขนาด 177 ไบต์ (เทียบกับ 2420 ไบต์ของ ML-DSA สำหรับระดับ 2) — เป็นลายเซ็น PQC ที่เล็กที่สุดเท่าที่ทราบ SQISign ใช้ปัญหายากในการคำนวณไอโซเจนีที่มีดีกรีกำหนดระหว่างเส้นโค้งซูเปอร์ซิงกูลาร์สองเส้นที่กำหนด ซึ่งทำให้เป็นรูปแบบอย่างเป็นทางการในชื่อปัญหาริงเอนโดมอร์ฟิซึม FESTA (Fast Encryption from Supersingular Torsion Attacks) เป็นการออกแบบ KEM ใหม่ที่หลีกเลี่ยงข้อมูลเสริมของจุดทอร์ชัน ซึ่งเป็นสาเหตุที่ทำให้ SIDH มีช่องโหว่ CTIDH (Constant-Time CSIDH) ปรับปรุงประสิทธิภาพของ CSIDH แบบแผนเหล่านี้ทำให้งานวิจัยไอโซเจนียังคงมีความสำคัญ แม้ SIKE จะถูกตัดออกแล้ว

ไอโซเจนีระหว่างเส้นโค้งวงรีคืออะไร

ไอโซเจนีคือการแมปเชิงตรรกยะ phi: E -> E' ที่เป็นโฮโมมอร์ฟิซึมของกรุปด้วย โดยมีดีกรีเท่ากับขนาดของเคอร์เนล สูตรของ Velu คำนวณเส้นโค้งภาพและการแมปจากกลุ่มย่อยเคอร์เนล กราฟไอโซเจนีจัดเส้นโค้งเป็นจุดยอด โดยมีเส้นเชื่อม l-ไอโซเจนีที่รวมกันเป็นกราฟ Ramanujan แบบสม่ำเสมอระดับ (l+1) เส้นโค้งซูเปอร์ซิงกูลาร์ (ที่ใช้ใน SIDH/SIKE/CSIDH) มีกราฟไอโซเจนีที่มีคุณสมบัติการขยายตัวสูง ปัญหา SSIP และ CSSI เป็นพื้นฐานของความปลอดภัยของไอโซเจนี SIDH ใช้โครงสร้างของจุดทอร์ชันร่วมกับสายโซ่ไอโซเจนี 2 และ 3 สลับกัน การคำนวณริงเอนโดมอร์ฟิซึมเทียบเท่ากับ SSIP SQISign และ FESTA เป็นแนวทางวิจัยหลัง SIKE ที่ยังดำเนินอยู่ โดยใช้ความยากของปัญหาริงเอนโดมอร์ฟิซึม