CSIDH: Isogenies تبادلية فائقة التفرد

يُعدّ CSIDH ‏(تبادل مفاتيح Diffie-Hellman باستخدام الإيزوجيني التبادلي الفائق التفرد، Castryck وآخرون، 2018) تبادلًا للمفاتيح قائمًا على الإيزوجينيات، ويتجنب تمامًا تسرب نقاط torsion في SIDH باستخدام بنية جبرية مختلفة جذريًا. يعمل CSIDH مع منحنيات فائقة التفرد على Fp، وليس على Fp2 كما في SIDH. وافتراض الصعوبة هو تبديلية تأثير زمرة الأصناف: يطبّق كل طرف عنصرًا سريًا من زمرة الأصناف على منحنى بدء مشترك، وتضمن التبديلية وصولهما معًا إلى المنحنى المشترك نفسه. ولا تُنشر أي معلومات مساعدة عن نقاط torsion؛ فالمفتاح العام ليس سوى ثابت j-invariant واحد. وقد صمد هذا التصميم أمام هجوم Castryck-Decru على SIDH.

على Fp حيث p = 3 mod 4، تمتلك المنحنيات فائقة التفرد E مؤثرًا ذاتيًا مميزًا pi ‏(وهو Frobenius)، وتحتوي جبرية المؤثرات الذاتية فيها على الترتيب التربيعي التخيلي Z[pi]. وتؤثر زمرة أصناف المثاليات Cl(Z[pi]) بحرية وبصورة انتقالية على مجموعة المنحنيات فائقة التفرد على Fp ‏(حتى التماثل). تؤثر مثالية a في Cl(Z[pi]) على منحنى E لإنتاج منحنى جديد a * E، ويُحسب ذلك باعتباره المنحنى E/E[a]، حيث E[a] هي مجموعة torsion الموافقة للمثالية 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-torsion واحسب إيزوجيني l_i باستخدام صيغ Velu. ومع sqrt-Velu، تستغرق كل خطوة إيزوجيني لعدد أولي كبير O(sqrt(l_i)) من العمليات. ويستغرق تبادل المفاتيح الكامل نحو 1-5 ms على الأجهزة الحديثة بالنسبة إلى CSIDH-512.

لا يعمل CSIDH الأصلي بزمن ثابت؛ إذ يعتمد عدد خطوات Velu على قيم المفتاح السري a_i، مما يؤدي إلى تسريب المعلومات عبر القنوات الجانبية للتوقيت. ويعالج CTIDH ‏(تبادل المفاتيح باستخدام 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 بت فقط، وهو أقل بكثير من متطلبات NIST Level 1.

يعتمد أمن CSIDH على مسألة عكس فعل الزمرة (GAIP): بالنظر إلى E_A = a * E0 وE0، أوجد a. وأفضل خوارزمية معروفة هي اختزال شبيه بـ Pohlig-Hellman مدموجًا مع baby-step-giant-step، ويعمل هذا الاختزال تقليديًا في O(sqrt(|Cl|)) ~ O(p^{1/4}). وتجعل الصعوبة الكمومية (Kuperberg) أمان CSIDH الكمومي أقل من أمان المخططات المعتمدة على LWE. ويوفر أفضل هجوم كمومي على LWE (غربلة الشبكات) هوامش أمان أكثر تحفظًا. وتتمثل ميزة CSIDH في صغر حجمه: إذ يبلغ حجم المفاتيح العامة في CSIDH-512 ‏64 بايتًا (ثابت j واحدًا فقط)، مقارنةً بـ 800 بايت في ML-KEM-512. ولذلك يظل CSIDH مثيرًا للاهتمام للتطبيقات التي تتطلب أصغر مفاتيح ممكنة وتقبل هوامش أمان كمومي أقل.

تعالج عدة متغيرات من CSIDH قيوده المتعلقة بالأمن الكمومي. يستخدم BSIDH (الحرف B اختصارًا لـ «better») منحنيات أساس ذات درجات أعلى وجداءات من المنحنيات الإهليلجية لزيادة حجم زمرة الأصناف مع الحفاظ على سرعة الحساب. ويعمل Csurf (CSIDH on the surface) مع مجموعة مختلفة من المنحنيات فائقة التفرد لتمكين حساب فعل الزمرة بسرعة أكبر. وتستخدم مقترحات 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 ms؛ وكان 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 بتًا، عن NIST Level 1 (128 بتًا)، ما يجعله غير مناسب لتطبيقات ما بعد الكم التي تتطلب الامتثال لمعايير NIST. وسيحقق CSIDH-5000 مستوى الأمان المطلوب، لكنه سيكون أبطأ بدرجة كبيرة. ويستمر البحث في تحسين تحليل الأمن الكمومي وفي تطوير متغيرات تسد هذه الفجوة، لكن CSIDH يظل بدائية بحثية أولية لا بدائية جاهزة للنشر، وذلك حتى عام 2024.

لماذا يتيح فعل زمرة الأصناف التبادلية في CSIDH تبادل المفاتيح غير التفاعلي؟

يستخدم CSIDH فعل زمرة الأصناف التبادلية لـ Cl(Z[pi]) على المنحنيات فائقة التفرد فوق Fp، حيث إن pi هو مؤثر فروبينيوس. والمفاتيح العامة ليست إلا ثوابت j (بحجم 64 بايتًا). ولا تُنشر أي نقاط التواء مساعدة، مما يتجنب ثغرة SIDH. وأفضل هجوم تقليدي هو O(p^{1/4})؛ أما أفضل هجوم كمومي (Kuperberg) فيعمل في زمن شبه أسي L(1/2)، ما يتطلب أعدادًا أولية بحجم 5000 بت لتحقيق أمان كمومي بمستوى 128 بت. ويوفر CTIDH تنفيذًا بزمن ثابت. ولا يوفر CSIDH-512 سوى نحو 65 بتًا من الأمان الكمومي. ولم يُعتمد CSIDH معيارًا؛ ويركز البحث على متغيرات تحسن المقاومة الكمومية مع الحفاظ على المفاتيح الصغيرة.