⚛️ quantum physics

CRT-Decomposed $Σ$ -Protocols for CSIDH

تقدم هذه الورقة بروتوكول $\Sigma$ مفككاً وفق تحليل الأعداد الأولية (CRT) لـ CSIDH يحقق تمام الاكتمال، والمعرفة الصفرية، والاستخراج المستقيم الفعال في نموذج الـ QROM دون افتراضات استدلالية، مع التحقق بصرامة من صحته الجبرية وإثبات أن أمنه يعتمد حالياً على معاملات مستقبلية ذات عوامل أولية كبيرة نظراً للانخفاض الكبير في تكلفة الهجوم الكلاسيكي عند نشر منحنيات قفزات الـ CRT.

المؤلفون الأصليون: I. Dey, I. Cherkaoui

نُشر 2026-09-23

📖 4 دقيقة قراءة🧠 قراءة متعمّقة

CC BY 4.0

المؤلفون الأصليون: I. Dey, I. Cherkaoui

البحث الأصلي مرخَّص بموجب CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ هذا شرح مولَّده بالذكاء الاصطناعي للبحث أدناه. لم يكتبه المؤلفون ولم يصادقوا عليه. وللتحقق من الدقة التقنية، يرجى الرجوع إلى البحث الأصلي. اقرأ إخلاء المسؤولية الكامل

في العالم الرقمي، غالبًا ما تعتمد الخصوصية على توازن دقيق: يرغب المستخدم في إثبات حقه في إنفاق المال أو الوصول إلى خدمة ما دون الكشف عن هويته أو التفاصيل المحددة للمعاملة. هذا هو مجال التوقيعات العمياء، وهي أداة تشفير تسمح للبنك بالمصادقة على عملة ما دون أن يرى أبداً أين سيتم إنفاقها. لعقود من الزمن، استند أمن هذه الأنظمة إلى ألغاز رياضية تتضمن أرقاماً كبيرة، لكن صعود الحواسيب الكمومية القوية يهدد بحل تلك الألغاز، مما يجعل حمايات الخصوصية الحالية عتيقة وغير مجدية. ولمواجهة ذلك، يتجه العلماء إلى نوع مختلف من الرياضيات القائم على هندسة المنحنيات الإهليلجية، وتحديداً طريقة تسمى التشفير القائم على "الإيزوجيني" (isogeny-based cryptography). يستخدم هذا النهج نوعاً فريداً من الحركة بين المنحنيات يكون من السهل القيام به في اتجاه واحد ولكن من الصعب للغاية عكسه، مما يخلق أساساً للأمن لا يمكن للآلات الكمومية كسرُه بسهولة. ومع ذلك، كان بناء أنظمة عملية على هذا الأساس أمراً صعباً لأن الطرق القياسية لإثبات معرفة المفتاح السري غالباً ما تعتمد على عملية تفشل عند مواجهة الخصوم الكموميين.

قام فريق من الباحثين في جامعة جنوب شرق التكنولوجية في أيرلندا بتطوير طريقة جديدة لبناء هذه الإثباتات تتجنب نقاط الضعف القاتلة في الطرق السابقة. يركز عملهم على نظام محدد يُعرف باسم CSIDH، والذي يستخدم بنية رياضية تسمى "مجموعة الفئات" (class group) للتنقل بين المنحنيات الإهليلجية. اكتشف الباحثون أنه عندما تكون البنية الداخلية لهذه المجموعة معروفة بالكامل، كما هو الحال في نسخة محددة تسمى CSIDH-512، يمكن تفكيكها إلى قطع أصغر ومستقلة باستخدام مبدأ رياضي كلاسيكي يُعرف باسم "نظرية الباقي الصينية". وبدلاً من معاملة المفتاح السري ككتلة واحدة متراصة، صمموا بروتوكولاً يثبت معرفة كل قطعة صغيرة على حدة. هذا التغيير الهيكلي يسمح للنظام باستخراج المفتاح السري مباشرة من الإثبات باستخدام حساب بسيط، بدلاً من الاعتماد على لعبة تخمين معقدة ومتكررة يمكن للحواسيب الكمومية تعطيلها.

إن جوهر إنجازهم هو نوع جديد من الإثبات التفاعلي الذي يتميز بأنه كامل تماماً وآمن تماماً ضد التنصت. في هذا النظام، يتبادل المُثبِت (prover) والمُتحقق (verifier) الرسائل لتأكيد أن المُثبِت يعرف المفتاح السري دون الكشف عن المفتاح نفسه. أثبت الباحثون أنه إذا تمكن المُثبِت من الإجابة بنجاح على تحديين مختلفين لنفس الخطوة، فيمكن استعادة السر فوراً عن طريق طرح الإجابات وإجراء عملية قسمة واحدة. هذه العملية، التي يسمونها "الاستخراج الجبري" (algebraic extraction)، تحدث في خط مستقيم دون الحاجة إلى إعادة التشغيل أو البدء من جديد. وهذا تمييز حاسم؛ لأن إثباتات الأمان السابقة لأنظمة مماثلة كانت تعتمد على "إعادة ضبط" (rewinding) المهاجم إلى حالة سابقة لإجباره على ارتكاب خطأ، وهي تقنية لا يمكن تبريرها ضد حاسوب كمومي لا يمكن إيقافه مؤقتاً أو نسخه. ومن خلال إزالة هذه الخطوة، يوفر البروتوكول الجديد مساراً للأمن يصمد حتى في المستقبل حيث تصبح الحواسيب الكمومية شائعة.

لضمان أن تصميمهم لم يكن مجرد فكرة نظرية، قام الفريق بتنفيذ النظام بأكمله على حاسوب باستخدام المعايير الدقيقة لمجموعة CSIDH-512. وتحققوا من المنطق الرياضي للبروتوكول عبر عشرة آلاف حالة عشوائية، مؤكدين أن الخطوات الجبرية تعمل بالضبط كما هو متوقع في كل مرة. كما أجروا عمليات محاكاة لقياس كيفية سلوك النظام تحت الهجوم. أكدت هذه الاختبارات أن أمن النظام يتبع القوانين الرياضية المتوقعة، وأن صعوبة كسرها تزدل بشكل يمكن التنبؤ به مع زيادة عدد الجولات. ومع ذلك، كان الباحثون حذرين أيضاً في تحديد حدود نهجهم؛ فقد أظهروا أنه بينما يؤدي تقسيم المشكلة إلى قطع أصغر إلى جعل استخراج السر ممكناً، فإنه يعرض النظام أيضاً لنوع من الهجمات التي تقلل من صعوبة كسر المفتاح. بالنسبة لمعايير CSIDH-512 الحالية، يؤدي هذا الانخفاض إلى خفض الأمن من مستوى يتطلب حوالي 2^128.6 من تقييمات فعل المجموعة إلى حوالي 2^67.3 تقييماً، وهو انخفاض كبير يجعل المعايير الحالية غير كافية لتحقيق أمن كلاسيكي بمستوى 128 بت.

بناءً على ذلك، خلص الباحثون إلى أنه على الرغم من أن بناءهم صحيح رياضياً ومكتمل هيكلياً، إلا أنه ليس جاهزاً بعد للنشر الفوري باستخدام معايير CSIDH-512 الحالية. فالنظام يعمل بشكل مثالي، لكن الميزة ذاتها التي تجعله فعالاً — وهي الكشف عن الخطوات الوسيطة — تجعله أيضاً عرضة لطريقة هجوم معروفة. ويرى الباحثون أن الحل يكمكم في مجموعات المعايير المستقبلية حيث تكون المكونات الرياضية أكبر بكثير. فإذا بُنيت المجموعة من عوامل أولية كبيرة جداً بشكل فردي، فإن خسارة الأمن الناتجة عن كشف الخطوات الوسيطة ستصبح ضئيلة، وسيبقى النظام آمناً. كما قارنت الورقة طريقتهم بالأنظمة الموجودة، مشيرة إلى أنه بينما تكون توقيعاتهم أكبر حالياً، فإن المقابل هو نموذج أمني لا يتدهور عند مواجهة التهديدات الكمومية. ويقف هذا العمل كدليل صارم على أن البنية الجبرية يمكن أن تحل محل إثباتات الأمان المعقدة والمليئة بالأخطاء، بشرما يتم اختيار الأرقام الأساسية بعناية كافية للصمود أمام الثغرات الجديدة التي تفرضها تلك البنية.

ملخص تقني: بروتوكولات $\Sigma$ المفككة عبر نظرية الباقي الصينية (CRT) لعمليات زمرة CSIDH

بيان المشكلة
تتناول الورقة ثغرة حرجة في البراهن الأمنية لبروتوكولات التوقيع الأعمى والتعريف بالهوية القائمة على الإيزوجيني (isogeny)، وتحديداً تلك المبنية على عمل زمرة CSIDH (الدي في-هي لـ CSIDH التبادلية فوق المنحنيات الفائقة). تعتمد البروتوكولات الأكثر تطوراً حالياً (مثل CSI-Otter وTanuki) على بروتوكولات تعريف تفاعلية تعتمد براهينها الأمنية على "لمّا التفرع" (forking lemma). تتطلب هذه اللمّا "إعادة تشغيل" (rewinding) للمهاجم الكمي لاستخراج المفتاح السري، وهي عملية تسبب خسارة أمنية تربيعية وتعتبر غير صالحة نظرياً ضد المهاجمين الكميين الذين لا يمكن استنساخ حالاتهم الداخلية. بناءً على ذلك، تضطر هذه البراهن إلى استخدام معاملات أكبر وأبطأ للتعويض عن هذه الخسارة. تسعى الورقة إلى القضاء على خطوة إعادة التشغيل هذه من خلال الاستفادة من البنية الجبرية لزمرة الفئات (class group) في CSIDH لتمكين "الاستخراج في الخط المستقيم" (straight-line extraction).

المنهجية
يصيغ المؤلفون بروتوكول إثبات معرفة (zero-knowledge proof of knowledge - $\Sigma$ -protocol) يستغل بنية نظرية الباقي الصينية (CRT) لزمرة فئات CSIDH. هذا النهج قابل للتطبيق فقط عندما تكون بنية الزمرة معروفة بدقة، وهو شرط لا يتحقق حالياً إلا في CSIDH-512.

تفكيك CRT: يتم تفكيك زمرة الفئات $C\ell(\mathcal{O})$ ذات الرتبة $N$ إلى مكونات حلقية مستقلة تقابل عوامل القوى الأولية لـ $N$ . يتم تقسيم المفتاح السري $s$ إلى مكونات $s_i$ بمقياس كل عامل أولي $q_i$ .
منحنيات القفز (Hop Curves): ينشر البروتوكول سلسلة من "منحنيات القفز" ( $F_0, \dots, F_k$ ) التي تمثل الحالات الوسيطة لعمل الزمرة. تقابل كل قفزة $i$ مشكلة متجه (vectorization) ضمن زمرة فرعية محددة $\langle h_i \rangle$ من الرتبة $q_i$ .
هيكل البروتوكول: يتكون البروتوكول من $k$ من القفزات، تُنفذ كل منها في $t$ من الجولات المتوازية. في كل جولة، يلتزم المُثبت (prover) بـ "إزاحة عشوائية"، ويصدر المُتحقق (verifier) تحدياً ثنائياً ( $c \in \{0,1\}$ )، ويستجيب المُثبت بقيمة $z$ .
الاستخراج الجبري: على عكس البراهن القياسية التي تتطلب إعادة التشغيل لإيجاد مخطوطتين مقبولتين بتحديات مختلفة، يسمح هذا البروتوكول باستعادة السر عبر صيغة جبرية مغلقة. بالنظر إلى مخطوطتين مقبولتين لنفس الالتزام، يكون المكون السري ببساطة هو الفرق بين الاستجابتين ( $z_0 - z_1$ )، متبوعاً بالمعكوس القياسي وإعادة تركيب CRT.
تجميع QROM: نظراً لأن كل جولة تسمح باستجابتين بالضبط، فإن البروتوكول متوافق مع تحويل Unruh. يتيح هذا تحويل البروتوكول التفاعلي إلى إثبات معرفة غير تفاعلي في نموذج الأوراكل العشوائي الكمي (QROM) مع استخراج في الخط المستقيم، مما يتجنب تماماً "لمّا التفرع".

المساهمات الرئيسية
تقدم الورقة خمس مساهمات رئيسية:

التعريف الرسمي: تصيغ الورقة تعريف "القابلية للاستخراج الضعيف" (weak extractability) لعمليات المجموعات التشفيرية، حيث تُعرف مفهوماً أمنياً حيث يمكن للمستخرج استعادة السر باستخدام العمليات الحلقية فقط (دون تقليل الشبكة أو الاستدلالات التجريبية) من المخطوطات المقبولة.
بناء البروتوكول ( $\Pi_{CRT}$ ): تصيغ البروتوكول الذي يثبت أربع خصائص:
- الاكتمال التام (Perfect Completeness): المُثبتون الشرفاء ينجحون دائماً.
- الخصوصية الخاصة المثالية (Perfect Special HVZK): لا تكشف المخطوطات أي معلومات عن السر، حتى للمراقبين غير المحدودين.
- المتانة الخاصة الثنائية (2-Special Soundness): يمكن استعادة السر جبرياً من مخطوطتين عبر عملية طرح بسيطة ومعكوس قياسي.
- خطأ المعرفة (Knowledge Error): احتمال نجاح المُثبت دون امتلاك المفتاح هو $2^{-t}$ .
التحقق الآلي: قام المؤلفون بتنفيذ الطبقة الجبرية فوق المعامل (modulus) الدقيق المكون من 258 بت لـ CSIDH-512. وقد تحققوا من 10,000 حالة عشوائية، مؤكدين أن الاستخراج الجبري يعمل بشكل مثالي وأن منطق البروتوكول سليم دون حساب إيزوجنيات فعلية.
تحديد النتائج (النتائج السلبية):
- حد فضاء التحدي: لا يؤدي تفكيك CRT إلى توسيع فضاء التحدي لكل جولة؛ تظل التحديات الثنائية ضرورية ما لم يتم نشر منحنيات متعددة، مما يزيد من حجم المفتاح.
- التكلفة الأمنية: نشر منحنيات القفز الوسيطة يقلل من الأمن الكلاسيكي لاستعادة المفتاح من $\approx 2^{128.6}$ إلى $\approx 2^{67.3}$ من تقييمات عمل الزمرة. وذلك لأن المشكلة تتفكك إلى حالات متجه مستقلة في زمر فرعية، يمكن حلها عبر هجمات "التقاء في المنتصف" (meet-in-the-middle) على أكبر مكون.
أمن QROM: تثبت الورقة أن البروتوكول، عند تجميعه عبر تحويل Unruh، ينتج إثبات معرفة غير تفاعلي بـ استخراج عبر الإنترنت (online extraction) في QROM، مما يزيل الخسارة الضربيه لـ "لمّا التفرع".

النتائج والتحليل الكمي

الاستنتاج (Instantiation): تم تطبيق المخطط على CSIDH-512. تحتوي زمرة الفئات على 5 عوامل أولية (أطوالها بالبت هي: 2، 6، 21، 96، 135).
الحدود الأمنية:
- كلاسيكياً: يتحدد الأمن بالعامل الأولي الأكبر ( $q_{max} \approx 2^{135}$ ). تكلفة هجوم "التقاء في المنتصف" هي $O(\sqrt{q_{max}}) \approx 2^{67.3}$ . تشير الورقة إلى أن CSIDH-512 لا يحقق أماناً كلاسيكياً بمستوى 128 بت تحت هذا البناء بسبب منحنيات القفز المنشورة.
- كمياً: يتقيد الأمن بـ "مناخل كوبربيرج" (Kuperberg-style sieves)، على غرار مخططات CSIDH الأخرى.
الأداء:
- حجم التوقيع: بالنسبة لـ $t=128$ جولة و $k=5$ مكونات، يبلغ حجم التوقيع حوالي 24.1 KiB (مقارنة بـ 263 بايت لـ CSI-FiSh و 8 KiB لـ CSI-Otter).
- الحساب: الاستخراج الجبري والمحاكاة يستغرقان أقل من ميكروثانية. التكلفة المهيمنة تظل هي تقييم الإيزوجني (المقدر بـ 40 مللي ثانية لكل عملية)، مما يجعل إجمالي وقت التوقيع حوالي 25.6 ثانية للبروتوكول الكامل.
المحاكاة: أكدت محاكاة مونت كارلو أن خطأ الصمود يطابق الحد النظري $2^{-t}$ ضمن فترات ثقة 95%.

الأهمية والادعاءات
تدعي الورقة أن البناء كامل هيكلياً وصحيح لزمر الفئات ذات البنية المعروفة مثل CSIDH-512. تكمن أهميته الأساسية في توفير اختزال أمني آمن كمياً لبروتوكولات إثبات المعرفة القائمة على الإيزوجني من خلال القضاء على خطوة إعادة التشغيل، وهي ثغرة معروفة في البراهن الأمنية لما بعد الكم.

ومع ذلك، المؤلفون صريحون بشأن المقايضات:

التواضع في الأمن: المخطط ليس آمناً كمياً بمستوى 128 بت لـ CSIDH-512 بسبب تدهور الأمن الناتج عن نشر منحنيات القفز. يذكر المؤلفون أن البناء "آمن كمياً فقط على مجموعات المعاملات المستقبلية التي تمتلك عوامل أولية كبيرة" (على سبيل المثال، حيث يكون كل عامل $\ge 256$ بت).
ليس حلاً سحرياً: تفكيك CRT لا يقلل من عدد الجولات المطلوبة للصمود؛ بل يغير آلية الاستخراج فقط.
العمل المستقبلي: تترك الورقة بناء توقيع أعمى يعتمد على إثبات المعرفة هذا، والاختزال الوثيق لعدم قابليته للتزوير لمشكلة حلقة النهاية (endomorphism ring problem)، كعمل مستقبلي.

باخت br، تقدم الورقة بروتوكولاً دقيقاً رياضياً ومتحققاً آلياً يحل "مشكلة إعادة التشغيل" لبروتوكولات إثبات المعرفة القائمة على CSIDH، مما يوفر مساراً لتوقيعات عمياء آمنة في نموذج QROM، ولكن على حساب أحجام توقيع أكبر وأمن كلاسيكي أقل لمجموعات المعاملات الحالية.

أبحاث مشابهة