A Compact Post-quantum Strong Designated Verifier Signature Scheme from Isogenies
تقترح هذه الورقة مخطط توقيع جديد مدمج، ذو مُتحقق محدد قوي وما بعد كمي، يعتمد على إجراءات المجموعات (التبادلية) التشفيرية والآيسوجيني، مما يضمن أن المُتحقق المحدد هو الوحيد الذي يمكنه تأكيد صحة التوقيع.
المؤلفون الأصليون:Farzin Renan, Wendi Gao, Jason T. LeGrow
في العالم الرقمي، عادة ما تكون الثقة شأناً عاماً. فعندما توقع مستنداً عبر الإنترنت، يعمل التوقيع الرقمي كختم يمكن لأي شخص يمتلك الأدوات المناسبة التحقق منه. هذه الشفافية هي العمود الفقري للأمن الحديث، مما يضمن أن الرسالة جاءت حقاً من مرسلها ولم يتم التلاعب بها. ومع ذلك، هناك حالات يكون فيها هذا الطابع العام عيباً وليس ميزة. تخيل محادثة خاصة بين شخصين حيث يريد أحدهما إثبات هويته للآخر، ولكن يجب عليه التأكد من عدم قدرة أي طرف ثالث على الاقتناع أبداً بأن الرسالة جاءت منه. إذا استطاع المستلم إثبات المصدر لقاضٍ أو صديق، فإن خصوصية التبادل ستنتهك. هذا هو تحدي توقيعات "المُحقِّق المُعيَّن": إنشاء إثبات لا يمكن إنكاره للمستلم المقصود، ولكنه غير مقنع تماماً لأي شخص آخر.
تزدزد الصعوبة عمقاً عندما نأخذ المستقبل في الاعتبار. تعتمد طرق التشفير التي تحمي بياناتنا حالياً على مسائل رياضية صعبة بالنسبة للحواسيب اليوم، ولكن يمكن حلها بسهولة بواسطة آلات كمومية قوية. وبينما يتسابق العلماء لبناء أنظمة يمكنها الصمود أمام هذه التهديدات المستقبلية، فإنهم يتجهون إلى فرع من الرياضيات يتعلق بأشكال المنحنيات والطرق التي يمكن من خلالها تحويل بعضها البعض. هذه التحويلات، المعروفة باسم "الإيزوجيني" (isogenies)، تقدم أساساً جديداً للأمن يُعتقد أنه آمن ضد الهجمات الكمومية. والهدف هو بناء نظام لا ينجو في العصر الكمومي فحسب، بل يحافظ أيضاً على الخصوصية الدقيقة للمحادثات المحددة.
لقد قدم فريق من الباحثين الآن طريقة جديدة لإنشاء هذه التوقيعات الخاصة والآمنة كمومياً. أطلقوا على نظامهم اسم CSI-SDVS، وهو مخطط مبني على خصائص الإيزوجيني فوق المنحنيات فائقة التفرد التبادلية (commutative supersingular isogenies). الفكرة الجوهرية هي استخدام العلاقة الرياضية الفريدة بين المنحنيات الناقصية لإنشاء توقيع لا يمكن التحقق منه إلا من قبل المستلم المقصود. في هذا النظام، يمتلك المرسل والمستلم مفتاحاً سرياً ومفتاحاً عاماً مقابلاً له. عندما يريد المرسل توقيع رسالة، فإنه يستخدم مفتاحه السري والمفتاح العام للمستلم لتوليد رمز فريد. يمكن للمستلم بعد ذلك استخدام مفتاحه السري الخاص للتحقق مما إذا كان الرمز صالحاً. تكمن عبقرية التصميم في قدرته على المحاكاة؛ إذ يمكن للمستلم أيضاً استخدام مفتاحه السري لتوليد توقيع يبدو تماماً مثل توقيع المرسل. ولأن المستلم يمكنه إنشاء تزييف مثالي، فإنه لا يستطيع إثبات أن توقيعاً معيناً جاء من المرسل بدلاً من كونه من إنتاجه هو نفسه. هذه الخاصية، المعروفة باسم "عدم القابلية للنقل" (non-transferability)، تضمن بقاء المحادثة خاصة حتى لو حاول المستلم مشاركة الدليل.
أثبت الباحثون أن مخططهم الجديد ليس آمناً ضد الحواسيب الكمومية فحسب، بل هو أيضاً عالي الكفاءة. في المحاولات السابقة لبناء أنظمة مماثلة، كانت المفاتح الرقمية والتوقيعات غالباً ضخمة، وتتطلب مئات الكيلوبايتات من البيانات للتخزين أو النقل. جعل هذا الأمر هذه الأنظمة غير عملية للعديد من التطبيقات الواقعية. ومع ذلك، فإن التصميم الجديد مدمج بشكل ملحوظ. باستخدام مجموعة محددة من المعلمات تُعرف باسم CSIDH-512، حقق الباحثون نظاماً حيث يبلغ طول المفاتيح السرية 256 بت، والمفاتيح العامة 512 بت، والتوقيعات نفسها تبلغ أيضاً 512 بت فقط. ولوضع ذلك في الاعتبار، قد يكون حجم التوقيع الرقمي القياسي في الأنظمة القديمة بحجم ملف نصي صغير، بينما هذا التوقيع الجديد هو تقريباً بحجم سطر واحد من النص. هذا الاختزال الدراماتيكي في الحجم يجعل هذه التكنولوجيا قابلة للاستخدام في الأجهزة ذات الذاكرة وعرض النطاق الترددي المحدود.
أثبت الفريق أن نظامهم يستوفي جميع المعايير الأمنية الصارمة المطلوبة لهذا النوع من التشفير. فقد أظهروا أنه لا يمكن للمهاجم تزوير توقيع دون المفاتيح السرية، وأثبتوا أن هوية الموقع تظل مخفية عن أي شخص آخر غير المُحقِّق المُعيَّن. تعتمد هذه البراهين على افتراض أن حل مسائل رياضية معينة تتعلق بإجراءات المجموعات (group actions) لهذه المنحنيات هو أمر مستحيل حاسوبياً، حتى بالنسبة لحاسوب كمومي. كما استكشف الباحثون نموذجاً رياضياً محدداً لإظهار أن أمن نظامهم يمكن ربطه بمسألة مختلفة قليلاً، ولكنها صعبة بنفس القدر. هذا النهج مزدوج الطبقات يعزز الثقة في متانة النظام.
من خلال الجمع بين خصوصية التحقق المُعيَّن وكفاءة التشفير القائم على الإيزوجيني، يقدم هذا العمل حلاً عملياً للتواصل الآمن والخاص في عالم ما بعد الكم. إنه ينقل المجال من الاحتمالات النظرية إلى أدوات ملموسة وقابلة للاستخدام. لقد أظهر الباحثون أنه من الممكن الحصول على توقيع قوي بما يكفي ليثق به المستلم، وضعيف بما يكفي ليتم إنكاره من قبل الآخرين، كل ذلك مع الحفاظ على البيانات صغيرة بما يكفي لاستخدامها في أي مكان. ويمثل هذا التوازن بين الخصوصية والأمن والكفاءة خطوة مهمة نحو إعداد بنيتنا التحتية الرقمية لمواجهة تحديات المستقبل.
ملخص تقني: مخطط توقيع للمتحقق المحدد القوي من عصر ما بعد الكم يتميز بكونه مدمجاً ومبنياً على الإيزوجيني (Isogenies)
بيان المشكلة
توفر التوقيعات الرقمية تقليدياً خاصية عدم الإنكار، مما يعني أن أي طرف لديه إمكانية الوصول إلى المفتاح العام للموقع يمكنه التحقق من صحة توقيعه. وبينما يعد ذلك مفيداً في العديد من التطبيقات، إلا أن هذه الخاصية غير مرغوب فيها في السيناريوهات التي تتطلب اتصالات "خارج السجل" (off-the-record)، حيث ترغب الموقعة (أليس) في توثيق رسالة لمستلم محدد (بوب) دون تمكين بوب من إثبات أن الرسالة صادرة عن أليس لطرف ثالث.
ولمعالجة ذلك، تم تقديم التوقيعات للمتحقق المحدد القوية (SDVS). يضمن مخطط SDVS أن المتحقق المحدد فقط هو من يمكنه التحقق من صحة التوقيع. ومن الأهمية بمكان أن يحقق هذا النوع من عدم القابلية للنقل (non-transferability): حيث يمكن للمتحقق المحدد محاكاة توقيعات لا يمكن تمييزها حسابياً عن التوقيعات الحقيقية، مما يمنعه من إقناع طرف ثالث بصحة التوقيع. علاوة على ذلك، يجب أن تحقق مخططات SDVS خصوصية هوية الموقع (PSI)، مما يضمن أنه في حال وجود توقيع صالح وعدة مفاتيح عامة مرشحة، لا يمكن لطرف ثالث تحديد المفتاح الذي استُخدم للتوقيع.
توجد مخططات SDVS في التشفير الكلاسيكي (المبنية على الأزواج الثنائية Bilinear Pairings أو توقيعات شنوير Schnorr)، لكنها عرضة للهجمات الكمومية عبر خوارزمية شور (Shor's algorithm). وغالباً ما تعاني المقترحات الحالية لما بعد الكم والمبنية على الأكواد أو الشبكات (Lattices) من أحجام مفاتيح وتوقيعات كبيرة (على سبيل المثال، تعقيد O(λ2)) أو ثبت فشلها في تحقيق خصائص عدم القابلية للنقل. كما واجهت المقترحات المستندة إلى الإيزوجيني (Isogeny) مؤخراً كسوراً أمنية (مثل SIDH) أو اعتمدت على فرضيات قد لا تكون متينة بالقدر المطلوب.
المنهجية
يقترح المؤلفون CSI-SDVS، وهو مخطط SDVS جديد يعتمد على فعل المجموعة الخاص بـ الديفي-هيلمان للإيزوجيني فوق السوبر-سنجيولار التبادلي (CSIDH). يستفيد البناء من الهيكل الجبري لفئة المثالي (Ideal Class Group) الذي يعمل على مجموعة المنحنيات الإهليلجية السوبر-سنجيولار فوق حقل منتهٍ Fp.
المكونات الأساسية
إعداد فعل المجموعة: يعمل المخطط ضمن فعل مجموعة فعال (G,X,∗)، حيث G هي فئة المثالية لرتبة في حقل تربيعي تخيلي، و X هي مجموعة المنحنيات الإهليلجية السوبر-سنجيولار. هذا الفعل حر وتعددي (transitive).
توليد المفاتيح:
يقوم الموقع والمتحقق بتوليد مفاتيح سرية (skS,skV) كأعداد صحيحة عشوائية في ZN (حيث N هو عدد الفئة).
يتم توليد المفاتيح العامة عن طريق تطبيق فعل المجموعة على منحنى أساسي E: pkS=[gskS]∗E و pkV=[gskV]∗E.
التوقيع والمحاكاة:
التوقيع: لتوقيع رسالة m، يختار الموقع عدداً صحيحياً عشوائياً z∈ZN، ويحسب Y=[gz+skS]∗pkV، ويحدد التوقيع σ=(h,z) حيث h=H(Y∣∣m).
المحاكاة: يمكن للمتحقق، بامتلاكه skV، محاكاة توقيع عبر اختيار z عشوائي، وحساب Y=[gz+skV]∗pkS، وتحديد σ=(h,z) مع h=H(Y∣∣m).
الصحة: نظراً لتبادلية فعل المجموعة، فإن [gz+skS]∗pkV=[gz+skS+skV]∗E=[gz+skV]∗pkS. وبالتالي، فإن القيمة Y التي يحسبها الموقع والمحاكي متطابقة، مما يضمن أن كلاهما ينتج توقيعات صالحة لنفس مدخلات الهاش.
التحقق: يتحقق المتحقق مما إذا كان h=H([gz+skV]∗pkS∣∣m).
المساهمات الرئيسية
توقيع SDVS مدمج لما بعد الكم: يقدم البحث CSI-SDVS، وهو مخطط SDVS فعال يتميز بتعقيد O(λ) للمفاتيح والتوقيعات. باستخدام معاملات CSIDH-512، يحقق المخطط:
المفتاح السري: 256 بت.
المفتاح العام: 512 بت.
التوقيع: 512 بت. يمثل هذا تحسيناً كبيراً مقارنة بمخططات SDVS السابقة المبنية على الشبكات والتي غالباً ما تكون أحجامها O(λ2)، والمخططات المبنية على الإيزوجيني ذات المفاتيح العامة الأكبر.
البراهن الأمنية في نموذج الهاش العشوائي (ROM) ونموذج فعل المجموعة الجبري (AGAM):
عدم القابلية للنقل (NT): مثبتة بشكل غير مشروط، حيث أن توزيعات التوقيعات الحقيقية والمحاكية متطابقة.
عدم القابلية للتزوير القوي (SUF-CMA) وخصوصية هوية الموقع (PSI): مثبتة أمنياً في نموذج الهاش العشوائي (ROM) تحت فرضية الديفي-هيلمان لقرار فعل المجموعة (GA-DDH).
الاختزالات الوثيقة (Tight Reductions): أثبت المؤلفون أيضاً أنه في نموذج فعل المجموعة الجبري (AGAM)، تختزل أمن الـ SUF-CMA والـ PSI لـ CSI-SDVS بشكل وثيق إلى مسألة فعل المجموعة العكسية (GAIP)، وهي مسألة حسابية وليست قرارية.
التحليل الأمني: أظهر البحث أن المخطط يحقق جميع تعريفات أمن SDVS القياسية (NT, SUF-CMA, PSI) دون الاعتماد على بروتوكول SIDH المكسور، بل باستخدام فعل مجموعة CSIDH الذي يُعتقد حالياً أنه آمن.
النتائج
يقدم البحث براهن أمن رسمية توضح أن:
المخطط غير قابل للنقل بشكل غير مشروط.
تحت فرضية GA-DDH في نموذج ROM، يكون المخطط غير قابل للتزوير بقوة ويوفر خصوصية هوية الموقع.
تحت فرضية GAIP في نموذجي AGAM و ROM، يحقق المخطط اختزالات وثيقة لكل من أمن SUF-CMA و PSI.
الأداء: يقارن الجدول 1 في البحث بين CSI-SDVS والأعمال السابقة (Sun et al. [26] و Khuc et al. [12]). يوفر CSI-SDVS أصغر مفتاح عام (512 بت) وأصغر توقيع (512 بت) بين مخططات ما بعد الكم التي تمت مقارنتها، مع الحفاظ على حجم مفتاح سري يبلغ 256 بت.
الأهمية
يضع المؤلفون CSI-SDVS كحل عملي وآمن لتوقيعات المتحقق المحدد لما بعد الكم. تكمن الأهمية في:
الكفاءة: يحقق معاملات مدمجة مناسبة للبيئات محدودة الموارد، مما يعالج قيود الحجم في مقترحات الشبكات والإيزوجيني السابقة.
المتانة: من خلال بناء الأمن على GAIP (فرضية حسابية) في نموذج AGAM، يتجنب المخطط الاعتماد على الفرضيات القرارية التي قد تكون أضعف أو أقل وضوحاً في سياق فعل المجموعة.
الاكتمال: يقدم العمل تحليلاً أمنياً كاملاً يغطي الركائز الثلاث لـ SDVS (عدم القابلية للنقل، عدم القابلية للتزوير، وخصوصية الموقع) في بيئة ما بعد الكم، مما يسد الفجوة التي تركتها المخططات السابقة التي إما فشلت في تحقيق عدم القابلية للنقل أو عانت من عدم الكفاءة.
يخلص البحث إلى أن CSI-SDVS يقدم توازناً متوازناً بين الأمن والكفاءة، مما يجعله مرشحاً قابلاً للتطبيق للتطبيقات التي تتطلب توثيقاً مقاوماً للكم وغير قابل للنقل.