🔢 mathematics

The SQInstructor: a guide to SQIsign and the Deuring Correspondence with level structures

تقدم هذه الورقة إطاراً عاماً لمخطط التوقيع SQIsign من خلال دمج هياكل المستويات في تحدي الأيزوجيني، مما يؤدي إلى تقابل ديورينج صريح جديد للمنحنيات الإهليلجية فائقة الشذوذ وحلول لمعادلات النظم المقيدة.

المؤلفون الأصليون: Giacomo Borin, Luca De Feo, Guido Maria Lido, Sina Schaeffler

نُشر 2026-03-11

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

CC BY 4.0

المؤلفون الأصليون: Giacomo Borin, Luca De Feo, Guido Maria Lido, Sina Schaeffler

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

تخيل أنك تحاول إثبات ملكيتك لخريطة كنز سرية دون أن تظهر الخريطة نفسها أبداً. في عالم التشفير، يسمى هذا التوقيع الرقمي. أنت تريد توقيع رسالة لتثبت أنها منك حقاً، لكنك لا تريد الكشف عن مفتاحك الخاص.

لفترة طويلة، كانت أفضل طريقة للقيام بذلك في عالم "ما بعد الكم" (حيث يمكن لأجهزة الكمبيوتر الكمومية المستقبلية كسر الشفرات الحالية) هي طريقة تسمى SQIsign. إنها تشبه لعبة عالية المخاطر من نوع "ابحث عن المسار" على خريطة سحرية مكونة من المنحنيات الإهليلجية (أشكال رياضية غريبة تشبه شكل الدونات).

الورقة البحثية التي قدمتها تقدم نسخة مطورة جديدة من هذه اللعبة تسمى SQInstructor. إليك تفصيل لما فعلوه، باستخدام تشبيهات بسيية.

1. اللعبة القديمة: SQIsign (عملية "الاختفاء")

في لعبة SQIsign الأصلية، يعطيك "المُتحقق" (الشخص الذي يفحص توقيعك) تحدياً: "جد مساراً من النقطة أ إلى النقطة ب يؤدي إلى تدمير معلم محدد على الخريطة تماماً."

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

2. اللعبة الجديدة: SQInstructor (مهمة "إعادة التمركز")

أدرك مؤلفو هذه الورقة: "لماذا يجب علينا تدمير المعلم؟ لماذا لا نقوم بنقله فقط؟"

لقد قدموا مفهوم بنى المستويات (Level Structures). فكر في بنية المستوى ليس كنقطة واحدة، بل كـ ترتيب خاص للأثاث في غرفة.

الطريقة القديمة: "دمر الكرسي."
الطريقة الجديدة (SQInstructor): "خذ الكرسي وانقله إلى مكان جديد محدد في الغرفة."

في لعبة SQInstructor:

الإعداد: لديك غرفة بداية (مفتاحك العام) مع ترتيب أثاث محدد (بنية المستوى).
التحدي: يقول المُتحقق: "أريدك أن تنقل ترتيب الأثاث هذا إلى غرفة أخرى (منحنى التحدي) وترتبه تماماً وفق هذا النمط الجديد."
الاستجابة: ترسم مساراً ينقل الأثاث من الغرفة القديمة إلى الغرفة الجديدة، مع ضمان استقرار الأثاث في التكوين المطلوب بدقة.

3. لماذا يعد هذا أمراً هاماً؟ (تشبيه "المترجم")

يعتمد سحر هذا النظام على شيء يسمى ارتباط ديورينج (Deuring Correspondence). تخيل أن لديك لغتين:

اللغة أ (المنحنيات): صعبة التحدث، بطيئة الترجمة، ولكنها آمنة جداً.
اللغة ب (الكواتيرنيون/الرباعيات): سهلة التحدث، سريعة الترجمة، لكن لا يمكنك كتابة الإجابة النهائية بهذه اللغة.

ارتباط ديورينج هو مترجم عالمي.

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

لقد أظهروا أنه يمكنك الآن حل "ألعاب نقل الأثاث" هذه بكفاءة، حتى عندما يكون ترتيب الأثرا م معقداً للغاية.

4. طريقتان للعب (1D مقابل 2D)

تستكشف الورقة طريقتين لتنفيذ هذه اللعبة الجديدة:

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

5. النتيجة: توقيع أفضل

باستخدام هذا الإطار الجديد، ابتكر المؤلفون SQInstructor.

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

ملخص

فكر في SQIsign كصانع أقفال ماهر يمكنه فتح القفل عن طريق كسر مسمار معين.
أما SQInstructor فهو صانع أقفال ماهر يمكنه فتح نفس القفل عن طريق إعادة ترتيب المسامير إلى نمط محدد.

تثبت الورقة أن إعادة ترتيب المسامير آمنة تماماً، وربه أكثر تنوعاً، وقد وجدوا التعليمات الرياضية الدقيقة (الخوارزميات) للقيام بذلك بسرعة. وهذا يمنح علماء التشفير أداة جديدة وقوية لبناء توقيعات رقمية جاهزة للمستقبل.

إليك ملخص تقني مفصل لورقة "SQInstructor: دليل لـ SQIsign وتناظر ديورينج مع هياكل المستوى (level structures)".

1. بيان المشكلة

تتناول الورقة الحاجة إلى تعميم مخطط التوقيع SQIsign، وهو مرشح رائد للتشفير ما بعد الكم يعتمد على الالتواءات فائقة التفرع (supersingular isogenies). وبينما يتميز SQIsign بكونه مدمجاً وفعالاً للغاية، فإن براهين أمنه وبناءه يعتمدان بشكل كبير على قيود محددة تتعلق بتناظر ديورينج (Deuring correspondence) - أي التكافؤ بين المنحنيات الإهليلجية فائقة التفرع والترتيبات القصوى في جبر الكواتيرنيون (quaternion algebras).

حدد المؤلفون أن بروتوكول SQIsign القياسي يمكن إعادة تفسيره من خلال منظور هياكل المستوى (level structures) - وهي قواعد لمجموعات التجزئة (torsion subgroups). في البروتوكول الأصلي، تكون الاستجابة عبارة عن التواء (isogeny) "يُبيد" (annihilates) نقطة تجزئة معينة (kernel). يقترح المؤلفون إطاراً أوسع حيث تكون الاستجبة عبارة عن التواء "ينقل" (maps) هيكل مستوى من شكل إلى آخر. يهدف هذا التعميم إلى:

توفير إطار نظري موحد للتوقيعات القائمة على الالتواءات.
تمكين إنشاءات جديدة باستخدام أنواع مختلفة من هياكل المستوى (مثل: Borel، وSplit Cartan، وScalar).
تسهيل بناء بدائل تشفيرية متقدمة (مثل التوقيعات الحلقية "ring signatures" ودوال Chameleon hashes) التي يصعب إنشاؤها باستخدام SQIsign القياسي.
حل معادلات النظم المقيدة (constrained norm equations) الجديدة في جبر الكواتيرنيون المطلوبة لهذه التعميمات.

2. المنهجية

تطور الورقة إطاراً شاملاً يسمى SQInstructor، والذي يعمم تناظر ديورينج ليشمل المنحنيات الإهليلجية المزودة بهياكل مستوى.

أ. تناظر ديورينج المعمم

قام المؤلفون بتوسيع تناظر ديورينج الكلاسيكي ليشمل المنحنيات الإهليلجية فائقة التفرع ذات هيكل مستوى $\Gamma$ (حيث $\Gamma$ هي مجموعة جزئية من $GL_2(\mathbb{Z}/N\mathbb{Z})$ ).

الأساس الرياضي: عرّفوا حلقة فرعية من الالتهاءات (endomorphism ring)، ويرمز لها $\mathcal{O}(E, S)$ ، تتكون من الالتهاءات التي تحافظ على هيكل المستوى $S$ .
تناظر المثال (Ideal Correspondence): أثبتوا أن الالتواءات التي تنقل هيكل مستوى إلى آخر تقابل مثالاً يسارياً رئيسياً محلياً (locally principal left ideals) في الرتبة الفرعية $\mathcal{O}(E, S)$ .
البناء الصريح: قدموا خوارزمية صريحة (الخوارزمية 1: InStructIdeal) لحساب التمثيل المصفوفي للالتواء على نقاط التجزئة، مما يسمح بترجمة عمليات المثال (ideal operations) إلى عمليات التواء حتى بالنسبة للمستويات الكبيرة وغير الناعمة (non-smooth levels).

ب. بروتوكول SQInstructor

عرفوا بروتوكول سيجما (Sigma-protocol) عاماً (بروتوكول تعريف) بناءً على هذا التناظر:

توليد المفتاح: المفتاح السري هو مثال أيسر $I_{sk}$ في $\mathcal{O}(E_0)$ ، والذي يحدد منحنى عاماً $E_{pk}$ مع هيكل مستوى مختار $S_{pk}$ .
الالتزام (Commitment): يرسل المُثبِت (prover) منحنى $E_{com}$ مشتقاً من مثال عشوائي.
التحدي (Challenge): يرسل المُتحقق (verifier) هيكل مستوى عشوائياً $S_{com}$ على $E_{com}$ .
الاستجابة (Response): يحسب المُثبِت التواءً $\phi_{rsp}$ بحيث يكون $\phi_{rsp}(S_{pk}) = S_{com}$ .
التحقق: يتحقق المُتحقق من أن الالتواء ينقل الهياكل بشكل صحيح.

ج. الإنشاءات (Instantiations)

تستكشف الورقة نوعين محددين من إنشاءات هذا الإطار:

الإنشاء أحادي البعد (1D Instantiation): يستخدم خوارزمية KLPT (Kohel-Lauter-Petit-Tignol) المعدلة لهياكل المستوى. يتضمن ذلك حل معادلات النظم المقيدة (constrained norm equations) في جبر الكواتيرنيون $B_{p,\infty}$ لإيجاد أمثلة ذات معيار (norm) ناعم تحترم قيود هيكل المستوى.
الإنشاء ثنائي البعد (2D Instantiation): يستخدم التواءات أعلى أبعاد (تحديداً التواءات $(2,2)$ -isogenies) لحساب الاستجابة. يتجاوز هذا النهج الحاجة إلى خوارزمية KLPT ويقدم أداءً مقارباً لـ SQIsign المرشح لـ NIST.

3. المساهمات الرئيسية

تناظر ديورينج المعمم: وسع المؤلفون تناظر ديورينج بصرامة ليشمل المنحنيات فائقة التفرع ذات هياكل المستوى التعسفية (Borel، وSplit Cartan، وScalar)، وأثبتوا التناظر بين التواءات هياكل المستوى والأمثلة المحلية الرئيسية في رتب فرعية محددة.
معادلات النظم المقيدة: طوروا خوارزميات جديدة (متغيرات من SigningKLPT ، وتحديداً ScalarSigningKLPT و BorelSigningKLPT) لحل معادلات النظم داخل الرتب الفرعية المعرفة بهياكل المستوى. هذه مساهمة خوارزمية هامة للتنفيذات أحادية البعد (1D).
التحليل الأمني:
- السلامة (Soundness): تم إثبات أنها 2-special sound، وتعتمد على صعوبة مسألة حلقة الالتهاء (Endomorphism Ring Problem) (إيجاد التهاء غير قياسي).
- المعرفة الصفرية (Zero-Knowledge): تم تحليلها تحت نموذج أوراكل الالتواء (Isogeny Oracle model) (ونماذج المساعدة بالقرائن/hints)، مما يظهر أن البروتوكول يتمتع بخاصية المعرفة الصفرية حتى مع التعقيد المضاف لهياكل المستوى.
- الأمن ضد الهجمات (EUF-CMA): تم إثبات أمن مخطط التوقيع في نموذج الأوراكل العشوائي (Random Oracle Model).
التنفيذات العملية:
- تنفيذ إثبات مفهوم (proof-of-concept) للنسخة أحادية البعد (1D) باستخدام هياكل Borel.
- تنفيذ كامل للنسخة ثنائية البعد (2D)، تمت مقارنته مع كود SQIsign المرجعي.

4. النتائج

الأداء (النسخة ثنائية البعد 2D): تحقق النسخة ثنائية البعد من SQInstructor أداءً مقارباً لـ SQIsign.
- توليد المفاتيح/التوقيع: أبطأ قليلاً من SQIsign بسبب العبء الإضافي لمعالجة مصفوفات هيكل المستوى وسلاسل الالتواء الأطول قليلاً المطلوبة لتمثيل $(2,2)$ -isogeny.
- حجم التوقيع: أكبر قليلاً (على سبيل المثال، ~272 بايت مقابل 224 بايت لأمن NIST III) بسبب تضمين مصفوفة التحدي وبيانات المنحنى المساعدة.
- التحقق: أبطأ قليلاً ولكن ضمن نفس الرتبة الحسابية.
النسخة أحادية البعد (1D): تنتج النسخة أحادية البعد تواقيعات أكبر وهي أقل كفاءة من النسخة ثنائية البعد، لكنها ضرورية للتطبيقات التي تتطلب القابلية للمحاكاة (simulatability) (مثل التوقيعات الحلقية ودوال Chameleon hashes)، والتي يصعب تحقيقها مع الالتواءات ثنائية البعد.
اختيار المعلمات: توفر الورقة مجموعات معلمات ملموسة لمستويات أمن NIST (I, III, V)، مع تحديد المستوى $N$ الأمثل بناءً على التجزئة المتاحة في المنحنى الابتدائي $E_0$ .

5. الأهمية

التوحيد النظري: يوحد SQInstructor مختلف البروتوكولات القائمة على الالتواء تحت نموذج "هيكل المستوى" واحد، مما يوضح العلاقة بين SQIsign، وافتراضات شبيهة بـ SIDH، وغيرها من البدائل.
تمكين البدائل المتقدمة: من خلال توفير نسخة أحادية البعد (1D) قوية ذات سجلات قابلة للمحاكاة، تفتح الورقة الباب لبناء التوقيعات الحلقية (ring signatures) و دوال Chameleon hashes في بيئة الالتواءات، وهي أمور كانت سابقاً نظرية أو غير فعالة.
التقدم الخوارزمي: إن تطوير خوارزميات لحل معادلات النظم في الرتب الفرعية (تحديداً لهياكل Borel وScalar) يطور أحدث ما توصل إليه العلم في حسابات جبر الكواتيرنيون، والتي تعد مركزية لتشفير الالتواءات.
الاستعداد للمستقبل: يثبت الإطار أن تناظر ديورينج مرن بما يكفي لاستيعاب قيود هيكلية متنوعة، مما يشير إلى أن تشفير الالتواءات يمكن أن يتطور إلى ما وراء القيود المحددة لتصميم SQIsign الأصلي مع الحفاظ على الأمن والكفاءة.

باختاً، يعد SQInstructor خطوة هامة للأمام في تشفير الالتواءات، حيث يقدم إطاراً مرناً يحافظ على الكفاءة العالية لتقنيات الالتواء ثنائية البعد الحديثة مع استعادة القدرة على المحاكاة لتقنيات البعد الواحد (1D) من أجل التطبيقات التشفيرية المتقدمة.