CSIDH: ไอโซจีนีซูเปอร์ซิงกูลาร์แบบสลับที่

CSIDH (Commutative Supersingular Isogeny Diffie-Hellman, โดย Castryck และคณะ, 2018) เป็นการแลกเปลี่ยนกุญแจที่อาศัยไอโซเจนี ซึ่งหลีกเลี่ยงการรั่วไหลของจุดทอร์ชันใน SIDH ได้ทั้งหมดด้วยการใช้โครงสร้างพีชคณิตที่แตกต่างโดยพื้นฐาน CSIDH ทำงานกับเส้นโค้งซูเปอร์ซิงกูลาร์เหนือ Fp (ไม่ใช่ Fp2 เหมือน SIDH) สมมติฐานความยากคือการสลับที่ได้ของการกระทำของกลุ่มคลาส โดยแต่ละฝ่ายใช้สมาชิกกลุ่มคลาสลับกับเส้นโค้งเริ่มต้นร่วมกัน และความสลับที่ได้ทำให้ทั้งสองฝ่ายไปถึงเส้นโค้งร่วมเดียวกัน ไม่มีการเผยแพร่ข้อมูลจุดทอร์ชันเสริม กุญแจสาธารณะจึงมีเพียงค่าคงรูป j ค่าเดียว การออกแบบนี้ผ่านการโจมตีของ Castryck-Decru ที่มีต่อ SIDH มาได้

เหนือ Fp ที่มี p = 3 mod 4 เส้นโค้งซูเปอร์ซิงกูลาร์ E มีเอนโดมอร์ฟิซึม pi ที่โดดเด่น ซึ่งก็คือฟรอเบนิอุส และพีชคณิตเอนโดมอร์ฟิซึมของเส้นโค้งมีออร์เดอร์กำลังสองจินตภาพ Z[pi] อยู่ภายใน กลุ่มคลาสของอุดมคติ Cl(Z[pi]) กระทำอย่างอิสระและถ่ายเทบนเซตของเส้นโค้งซูเปอร์ซิงกูลาร์เหนือ Fp เมื่อถือว่าเส้นโค้งที่ไอโซมอร์ฟิกกันเป็นสิ่งเดียวกัน อุดมคติ a ใน Cl(Z[pi]) กระทำบนเส้นโค้ง E เพื่อสร้างเส้นโค้งใหม่ a * E ซึ่งคำนวณได้จากเส้นโค้ง E/E[a] โดย E[a] คือกลุ่มย่อยทอร์ชันที่สอดคล้องกับอุดมคติ a การกระทำนี้สลับที่ได้: a * (b * E) = b * (a * E) = [ab] * E นี่คือการกระทำของกลุ่ม CSIDH ซึ่งเป็นรูปแบบสลับที่ได้ของ Diffie-Hellman

การแลกเปลี่ยนกุญแจ CSIDH ดำเนินการดังนี้ พารามิเตอร์สาธารณะ: เส้นโค้งซูเปอร์ซิงกูลาร์ E0 เหนือ Fp และจำนวนเฉพาะคี่ขนาดเล็ก l_1, ..., l_n กุญแจลับ: Alice เลือก a = (a_1, ..., a_n) โดยแต่ละ a_i อยู่ใน {-m, ..., m} (จำนวนเต็มขนาดเล็กแบบสุ่ม) ส่วน Bob เลือก b = (b_1, ..., b_n) กุญแจสาธารณะของ Alice: E_A = [l_1^a_1 * ... * l_n^a_n] * E0 กุญแจสาธารณะของ Bob: E_B = [l_1^b_1 * ... * l_n^b_n] * E0 ความลับร่วม: Alice ใช้เลขชี้กำลังลับของตนกับ E_B ส่วน Bob ใช้เลขชี้กำลังของตนกับ E_A ความสลับที่ได้ทำให้ทั้งสองฝ่ายได้ E_AB = [product(l_i^(a_i + b_i))] * E0 ความลับร่วมคือ j(E_AB) ไม่มีการเผยแพร่จุดเสริม

การใช้งาน CSIDH อ้างอิงใช้ p = 4 * l_1 * l_2 * ... * l_74 - 1 โดย l_1 ถึง l_74 คือจำนวนเฉพาะคี่ 74 จำนวนแรก (3, 5, 7, ..., 373) ทำให้ p มีขนาดประมาณ 512 บิต องค์ประกอบแต่ละตัวของกุญแจลับ a_i อยู่ใน {-5, ..., 5} (มี 11 ตัวเลือกต่อองค์ประกอบ และมี 74 องค์ประกอบ) อันดับของกลุ่มคลาสมีค่าประมาณ sqrt(p) และปริภูมิกุญแจมีขนาด 11^74 การคำนวณแต่ละขั้นตอนไอโซเจนี: สำหรับจำนวนเฉพาะ l_i แต่ละตัว ให้ค้นหากลุ่มย่อยทอร์ชัน l_i และคำนวณไอโซเจนี l_i โดยใช้สูตรของ Velu เมื่อใช้ sqrt-Velu การคำนวณไอโซเจนีของจำนวนเฉพาะขนาดใหญ่แต่ละขั้นใช้การดำเนินการ O(sqrt(l_i)) ครั้ง การแลกเปลี่ยนกุญแจทั้งหมดใช้เวลาประมาณ 1-5 มิลลิวินาทีบนฮาร์ดแวร์สมัยใหม่สำหรับ CSIDH-512

CSIDH ดั้งเดิมไม่ได้ใช้เวลาในการคำนวณคงที่: จำนวนขั้นตอนของ Velu ขึ้นอยู่กับค่าของกุญแจลับ a_i ทำให้ข้อมูลรั่วไหลผ่านช่องทางข้างเคียงด้านเวลา CTIDH (Constant-Time ISOGENY Diffie-Hellman, โดย Bernstein และคณะ, 2021) แก้ปัญหานี้ด้วยการใช้รูปแบบกุญแจน้ำหนักคงที่และการคำนวณไอโซเจนีแบบเวลาในการคำนวณคงที่ที่ออกแบบอย่างรอบคอบ กุญแจลับของ CTIDH จำกัดให้อยู่ในรูปเวกเตอร์ที่ผลรวมของค่าสัมบูรณ์มีค่าคงที่ (เช่น sum |a_i| = 130) การคำนวณไอโซเจนีดำเนินไปด้วยจำนวนขั้นตอนคงที่โดยไม่ขึ้นกับค่าของกุญแจลับ และใช้การคำนวณไอโซเจนีจำลองเพื่อเติมขั้นตอนที่เลขชี้กำลังลับเป็นศูนย์ CTIDH ให้ความปลอดภัยใกล้เคียงกับ CSIDH-512 พร้อมการรับประกันเวลาในการคำนวณคงที่อย่างเคร่งครัด ซึ่งเหมาะสำหรับการนำไปใช้งานในระบบฝังตัว

ความปลอดภัยเชิงควอนตัมของ CSIDH มีความซับซ้อนมากกว่าโครงร่างที่อาศัยแลตทิซ การโจมตีเชิงควอนตัมที่ดีที่สุดใช้อัลกอริทึมของ Kuperberg (2005) สำหรับปัญหาการเลื่อนที่ซ่อนอยู่ ซึ่งสามารถเจาะโครงสร้างการกระทำของกรุปคลาสได้ในเวลาแบบกึ่งเอ็กซ์โพเนนเชียล L(1/2) = exp(O(sqrt(log p))) ซึ่งดีกว่าการโจมตีแบบคลาสสิกที่ดีที่สุดซึ่งมีความซับซ้อน sqrt(p) อย่างมาก กล่าวคือ คอมพิวเตอร์ควอนตัมทำให้ CSIDH อ่อนแอลงอย่างมีนัยสำคัญเมื่อเทียบกับการโจมตีแบบคลาสสิก สำหรับความปลอดภัยหลังควอนตัมระดับ 128 บิต (ต้านทานการโจมตี L(1/2)) CSIDH ต้องใช้จำนวนเฉพาะ p ที่มีขนาดประมาณ 5000 บิต (CSIDH-5000) เทียบกับ 512 บิตสำหรับความปลอดภัยแบบคลาสสิกระดับ 128 บิต โดยประเมินว่า CSIDH-512 มีความปลอดภัยเชิงควอนตัมเพียง 62–72 บิต ซึ่งต่ำกว่าข้อกำหนดระดับ 1 ของ NIST อย่างมาก

ความปลอดภัยของ CSIDH อาศัยปัญหาผกผันของการกระทำของกรุป (GAIP): เมื่อกำหนด E_A = a * E0 และ E0 แล้ว จงหา a อัลกอริทึมที่รู้จักว่าดีที่สุดคือการลดรูปคล้าย Pohlig-Hellman ร่วมกับวิธีขั้นเล็ก–ขั้นใหญ่ ซึ่งทำงานด้วยความซับซ้อน O(sqrt(|Cl|)) ~ O(p^{1/4}) ในกรณีแบบคลาสสิก ความยากเชิงควอนตัมของ CSIDH (Kuperberg) ทำให้มีความปลอดภัยเชิงควอนตัมน้อยกว่าโครงร่างที่อาศัย LWE การโจมตีเชิงควอนตัมที่ดีที่สุดของ LWE (การร่อนแลตทิซ) ให้ระยะเผื่อความปลอดภัยที่ระมัดระวังกว่า ข้อได้เปรียบของ CSIDH คือความกะทัดรัด: CSIDH-512 มีกุญแจสาธารณะขนาด 64 ไบต์ (มีเพียงค่าคงรูป j) เทียบกับ 800 ไบต์ของ ML-KEM-512 สำหรับแอปพลิเคชันที่ต้องการกุญแจขนาดเล็กที่สุดเท่าที่เป็นไปได้และยอมรับระยะเผื่อความปลอดภัยเชิงควอนตัมที่ต่ำกว่า CSIDH ยังคงเป็นตัวเลือกที่น่าสนใจ

มีการพัฒนารูปแบบต่าง ๆ ของ CSIDH หลายรูปแบบเพื่อแก้ข้อจำกัดด้านความปลอดภัยเชิงควอนตัม BSIDH (B มาจากคำว่า "better") ใช้เส้นโค้งฐานที่มีดีกรีสูงกว่าและผลคูณของเส้นโค้งวงรี เพื่อเพิ่มขนาดของกรุปคลาสขณะที่ยังคงคำนวณได้รวดเร็ว Csurf (CSIDH บนพื้นผิว) ทำงานกับชุดเส้นโค้งซูเปอร์ซิงกูลาร์ที่แตกต่างออกไป เพื่อให้คำนวณการกระทำของกรุปได้เร็วขึ้น ข้อเสนอ CSIDH แบบสกุลสูงกว่าใช้จาโคเบียนของเส้นโค้งสกุล-2 เหนือ Fp ทำให้มีปริภูมิการกระทำของกรุปขนาดใหญ่ขึ้นและอาจมีระยะเผื่อความปลอดภัยเชิงควอนตัมที่ดีกว่า อย่างไรก็ตาม รูปแบบเหล่านี้ยังไม่มีรูปแบบใดได้รับการใช้งานอย่างแพร่หลายหรือได้รับการพิจารณาโดย NIST ส่วนหนึ่งเนื่องจากการวิเคราะห์ความปลอดภัยเชิงควอนตัมของรูปแบบต่าง ๆ ของ CSIDH ยังคงพัฒนาอยู่และมีความพร้อมน้อยกว่าการวิเคราะห์ของโครงร่างที่อาศัยแลตทิซ

CSIDH และ SIDH แตกต่างกันในหลายด้านพื้นฐาน การสลับที่ได้: CSIDH ใช้การกระทำของกรุปที่สลับที่ได้ (กรุปคลาส) ส่วน SIDH เป็นการแลกเปลี่ยนกุญแจแบบไม่โต้ตอบที่ใช้ไอโซจีนีแบบสลับที่ไม่ได้ร่วมกับจุดทอร์ชันเสริม ฟิลด์ฐาน: CSIDH ทำงานเหนือ Fp ส่วน SIDH ทำงานเหนือ Fp2 (ส่วนขยายกำลังสอง) ขนาดกุญแจสาธารณะ: CSIDH มีขนาด 64 ไบต์ (ค่าคงรูป j เพียงค่าเดียวเหนือ Fp) ส่วน SIDH มีขนาด 324 ไบต์ขึ้นไป (เส้นโค้งและจุด Fp2 สองจุด) ความปลอดภัย: CSIDH รอดพ้นจากการโจมตีของ Castryck-Decru ส่วน SIDH ถูกทำลาย ความปลอดภัยเชิงควอนตัม: CSIDH ต้องใช้จำนวนเฉพาะขนาด 5000 บิตเพื่อให้มีความปลอดภัยเชิงควอนตัมระดับ 128 บิต ส่วน SIDH มีความต้านทานเชิงควอนตัมใกล้เคียงกันก่อนถูกโจมตีแบบคลาสสิกจนแตก ประสิทธิภาพ: CSIDH-512 ใช้เวลาประมาณ 1–5 มิลลิวินาที ส่วน SIDH มีประสิทธิภาพใกล้เคียงกัน แต่ CSIDH-5000 จะช้ากว่ามาก

การสลับที่ได้ของ CSIDH ทำให้สามารถแลกเปลี่ยนกุญแจแบบไม่โต้ตอบ (NIKE) ได้: Alice เผยแพร่ E_A = a * E0 ส่วน Bob เผยแพร่ E_B = b * E0 ต่อมา โดยไม่ต้องสื่อสารเพิ่มเติม ผู้ใดก็สามารถคำนวณความลับร่วมจากกุญแจสาธารณะตัวใดตัวหนึ่งได้: Alice คำนวณ a * E_B = a * (b * E0) = ab * E0 ส่วน Bob คำนวณ b * E_A = b * (a * E0) = ab * E0 คุณสมบัติ NIKE นี้มีประโยชน์สำหรับแอปพลิเคชันที่การแลกเปลี่ยนกุญแจแบบโต้ตอบทำได้ยาก เช่น การเข้ารหัสอีเมลที่ผู้ส่งและผู้รับไม่ได้ออนไลน์พร้อมกัน NIKE จาก CSIDH มีลักษณะคล้ายกับ NIKE ของ Diffie-Hellman แต่เป็นแบบหลังควอนตัม ML-KEM (ซึ่งอาศัย LWE) ไม่รองรับ NIKE โดยธรรมชาติ หากไม่มีการออกแบบโพรโทคอลเพิ่มเติม

CSIDH ยังไม่ได้รับการกำหนดมาตรฐานและยังไม่ถูกนำไปใช้งานในระบบจริง ปัจจุบันเป็นหัวข้อวิจัยที่ดำเนินอยู่อย่างต่อเนื่องและมีการใช้งานให้ทดลองใช้แล้ว ได้แก่ CTIDH (เวลาแน่นอน), csidh-reference (Python สำหรับการเรียนการสอน) และ supersingular-isogeny-toolbox (ภาษา C ที่ปรับให้เหมาะสม) อุปสรรคสำคัญต่อการนำไปใช้งานคือความปลอดภัยเชิงควอนตัม: ความปลอดภัยเชิงควอนตัมของ CSIDH-512 ซึ่งประเมินไว้ที่ 62–72 บิต ต่ำกว่าระดับ 1 ของ NIST (128 บิต) จึงไม่เหมาะสำหรับแอปพลิเคชันหลังควอนตัมที่ต้องเป็นไปตามข้อกำหนดของ NIST CSIDH-5000 จะมีระดับความปลอดภัยตามเกณฑ์ แต่จะช้าลงอย่างมาก การวิจัยยังคงมุ่งปรับปรุงการวิเคราะห์ความปลอดภัยเชิงควอนตัมและพัฒนารูปแบบต่าง ๆ ที่ช่วยลดช่องว่างนี้ อย่างไรก็ตาม ณ ปี 2024 CSIDH ยังคงเป็นพื้นฐานการเข้ารหัสต้นแบบสำหรับงานวิจัย ไม่ใช่กลไกที่พร้อมนำไปใช้งานจริง

เหตุใดการกระทำของกรุปคลาสที่สลับที่ได้ของ CSIDH จึงทำให้สามารถแลกเปลี่ยนกุญแจแบบไม่โต้ตอบได้

CSIDH ใช้การกระทำของกรุปคลาสที่สลับที่ได้ของ Cl(Z[pi]) บนเส้นโค้งซูเปอร์ซิงกูลาร์เหนือ Fp โดยที่ pi คือเอนโดมอร์ฟิซึมของ Frobenius กุญแจสาธารณะเป็นค่าคงรูป j เพียงค่าเดียว (64 ไบต์) ไม่มีการเผยแพร่จุดทอร์ชันเสริม จึงหลีกเลี่ยงช่องโหว่ของ SIDH การกระทำของกรุปคลาสสลับที่ได้ จึงรองรับ NIKE การโจมตีแบบคลาสสิกที่ดีที่สุดมีความซับซ้อน O(p^{1/4}) ส่วนการโจมตีเชิงควอนตัมที่ดีที่สุด (Kuperberg) ทำงานในเวลาแบบกึ่งเอ็กซ์โพเนนเชียล L(1/2) จึงต้องใช้จำนวนเฉพาะขนาด 5000 บิตเพื่อให้มีความปลอดภัยเชิงควอนตัมระดับ 128 บิต CTIDH มีการใช้งานที่ใช้เวลาแน่นอน CSIDH-512 มีความปลอดภัยเชิงควอนตัมเพียงประมาณ 65 บิต CSIDH ยังไม่ได้รับการกำหนดมาตรฐาน การวิจัยมุ่งพัฒนารูปแบบต่าง ๆ ที่เพิ่มความต้านทานเชิงควอนตัมขณะยังคงรักษากุญแจขนาดกะทัดรัด