Isogenies للمنحنيات الإهليلجية: الأساس الرياضي

الإيزوجيني بين منحنيين إهليلجيين E وE' فوق حقل k هي دالة كسرية غير ثابتة phi: E -> E'، وهي أيضًا تجانس زُمري — أي إنها تنقل قانون المجموعة في E إلى قانون المجموعة في E'. لكل إيزوجيني phi إيزوجيني مزدوجة phi_hat: E' -> E، بحيث يساوي تركيب phi_hat مع phi المقدار multiplication-by-deg(phi) على E. تساوي درجة الإيزوجيني حجم نواتها؛ فالإيزوجيني من الدرجة l لها نواة حجمها l. وتعمّم الإيزوجينيات الضرب القياسي: فالضرب في n هو إيزوجيني من E إلى نفسه ودرجتها n^2. وتُحسب الإيزوجينيات فوق الحقول المنتهية على هيئة دوال كسرية، أي كثيرات حدود، يمكن تقييمها بكفاءة.

توفر صيغ Velu (1971) صيغًا صريحة لحساب إيزوجيني phi: E -> E/G عند إعطاء زمرة جزئية G من E. يحدد G بالكامل المنحنى الناتج E/G = E' والدالة الكسرية phi. وتحسب صيغ Velu معاملات المنحنى الناتج والدالة الكسرية على هيئة دوال كسرية درجتها تساوي |G|. وعندما تكون زمرة النواة G ذات رتبة أولية l، تكون الإيزوجيني من الدرجة l ويمكن حسابها باستخدام O(l) عملية. وتقلل خوارزميات sqrt-Velu (Bernstein وآخرون، 2019) ذلك إلى O(sqrt(l)) عملية للقيم الكبيرة لـ l، مما يتيح إيزوجينيات CSIDH ذات الأوليات الكبيرة بكفاءة. وتُعد صيغ Velu الأداة الحسابية الأساسية في جميع أنواع التشفير القائم على الإيزوجيني.

يمكن تنظيم المنحنيات الإهليلجية فوق حقل منتهٍ Fp في رسم بياني للإيزوجينيات. وتمثل الرؤوس ثوابت j للمنحنيات الإهليلجية، وهي ثوابت معيارية تحدد المنحنى حتى التماثل. وتمثل الحواف إيزوجينيات l؛ إذ يملك كل منحنى اعتيادي بالضبط l+1 إيزوجيني l خارجة عندما تكون 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 لإيجاد claw-finding، في زمن 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. وسر أليس هو إيزوجيني 2^a، وهي phi_A: E -> E_A ذات نواة مولدة بعنصر عشوائي من نقاط الالتواء من الرتبة 2^a. أما سر بوب فهو إيزوجيني 3^b، وهي phi_B: E -> E_B. ويتبادل الطرفان صور نقاط الالتواء: تنشر أليس E_A وphi_A(P_B) وphi_A(Q_B)، وينشر بوب E_B وphi_B(P_A) وphi_B(Q_A). ويتيح ذلك لكل طرف حساب إيزوجينيات انطلاقًا من منحنى الطرف الآخر، والوصول إلى ثابت j المشترك نفسه.

حلقة التشاكلات الذاتية End(E) لمنحنى إهليلجي هي حلقة جميع الإيزوجينيات من E إلى نفسه، بما في ذلك عمليات الضرب القياسي. وبالنسبة إلى المنحنيات الاعتيادية فوق Fp، تكون 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 إلى سلسلة من a إيزوجينيات منفردة من الدرجة 2؛ فكل إيزوجيني من الدرجة 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، وهو مستوى NIST 1. وللمقارنة، يبلغ حجم المفاتيح العامة في 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، ويستخدمان صعوبة حلقة التشاكلات الذاتية.