Post-Quantum Sanitizable Signatures from McEliece-Based Chameleon Hashing

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

تسمح التوقيعات القابلة للتنقية (Sanitizable signatures) للموقع بتفويض الحق في تعديل أجزاء محددة من مستند موقع إلى "منقٍّ" (sanitizer) معين دون إبطال التوقيع، مع الحفاظ على بقية المستند غير قابل للتغيير. وهذا أمر بالغ الأهمية لتطبيقات مثل حجب معرفات المرضى في السجلات الطبية أو تحديث تواريخ انتهاء الصلاحية في الشهادات.

ومع ذلك، تعتمد مخططات التوقيع القابلة للتنقية الموجودة حالياً على بدائيات تشفير كلاسيكية (RSA، اللوغاريتمات المنفصلة، الأزواج - Pairings) والتي تكون عرضة لهجوم "خوارزمية شور" (Shor's algorithm) على الحواسيب الكمومية. وبينما توجد حلول حديثة تعتمد على الشبكات (Lattice-based) لمرحلة ما بعد الكم، إلا أنها تعاني من:

• الاعتماد على نموذج الأوراكل العشوائي (ROM) لضمان مقاومة التصادم.
• الافتقار إلى الشفافية الكاملة (القدرة على جعل التوقيعات المنقاة متطابقة إحصائياً مع التوقيعات الأصلية).
• الاعتماد على فرضيات صلابة أحدث وأقل نضجاً (Module-LWE).

تعالج الورقة البحثية الفجوة في التوقيعات القابلة للتنقية المعتمدة على الأكواد (Code-based) في مرحلة ما بعد الكم، وتحديداً تهدف إلى بناء مخطط يتميز بالشفافية، وعدم القابلية للتغيير، والاعتماد على نظام McEliece العريق.

2. المنهجية

يقترح المؤلفون بناءً مبتكراً يعتمد على نظام McEliece التشفيري وأكواد غوبا (Goppa codes). الابتكار الجوهري هو دالة هاش "كاميليون" (Chameleon hash function) مشتقة من فك تشفير المتلازمة (Syndrome decoding).

أ. بناء هاش "كاميليون"

تُعرف دالة الهاش كما يلي:
$$H_{pk}(m, r) = (G(m) \oplus r) \cdot H_{pub}^T$$
حيث أن:

• $m$: كتلة الرسالة.
• $r$: متجه العشوائية بوزن هامينج $t$.
• $G(m)$: دالة هاش تُنمذج كـ أوراكل عشوائي (Random Oracle) (مثل SHA-3).
• $H_{pub}$: مصفوفة التحقق من التكافؤ العامة لكود "غوبا" ثنائي.

خيارات التصميم الرئيسية:

1. المعالجة المسبقة للأوراكل العشوائي: بدون $G(m)$، ستكون دالة الهاش خطية ($H(x,r) = (x \oplus r)H^T$)، مما يجعلها عرضة بسهولة لهجمات التصادم. من خلال هاش الرسالة أولاً، يتطلب إيجاد تصادم عكس الأوراكل العشوائي، وهو أمر غير ممكن حسابياً.
2. آلية الباب الخلفي (Trapdoor): يمتلك المنقّي المفتاح السري (معاملات كود غوبا، مصفوفة الخلط $S'$، والتبديل $P$). لإيجاد تصادم لرسالة جديدة $m'$، يقوم المنقّي بحساب متلازمة مستهدفة واستخدام فك تشفير باترسون (Patterson decoding) لإيجاد عشوائية $r'$ صالحة بحيث يكون $H(m, r) = H(m', r')$. هذه العملية فعالة ($O(n \cdot t)$).

ب. مخطط التوقيع القابل للتنقية

يقوم المخطط بربط هاش "كاميليون" عبر كتل الرسائل:

1. توليد المفاتيح: إنشاء زوجين مستقلين من مفاتيح McEliece: أحدهما للكتل غير القابلة للتغيير ($H_{non}$) والآخر للكتل القابلة للتنقية ($H_{san}$).
2. التوقيع: ينشئ الموقع سلسلة هاش. للكتل غير القابلة للتغيير، يستخدم $H_{non}$؛ وللبتل القابلة للتنقية، يستخدم $H_{san}$. يتم توقيع الملخص النهائي باستخدام توقيع قياسي لما بعد الكم (مثل Dilithium2).
3. التنقية: يقوم المنقّي بتعديل الكتل القابلة للتنقية. باستخدام الباب الخلفي لـ $H_{san}$، يجد عشوائيات $r'$ جديدة للحفاظ على سلامة سلسلة الهاش. يظل التوقيع النهائي صالحاً لأن الملخص النهائي ($h_L$) وقناع القابلية ($admissibility\ mask$) قد تم الحفاظ عليهما.

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

1. أول توقيع قابل للتنقية في مرحلة ما بعد الكم يعتمد على الأكواد: هذا هو أول بناء لتوقيع قابل للتنقية شفاف وفي مرحلة ما بعد الكم يعتمد على فرضيات الأكواد (فك تشفير المتلازمة).
2. الشفافية الكاملة عبر قيود الوزن:
   • يثبت المؤلفون أنه إذا قام الموقع باختيار العشوائيات بوزن دقيق يساوي $t$، فإن توزيع التوقيعات الجديدة سيكون مطابقاً لتوزيع التوقيعات المنقاة (حيث ينتج فك تشفير باترسون طبيعياً متجهات بوزن $t$).
   • يحقق هذا شفافية كاملة ($\delta = 0$)، مما يعني عدم وجود ميزة إحصائية أو حسابية للمراقب للتمييز بين الموقع والمنقّي.
   • بدون هذا القيد، تكون المسافة الإحصائية ضئيلة ولكنها غير صفرية ($\delta \approx 0.0187$ للمعاملات القياسية).
3. إثباتات أمنية صارمة:
   • عدم القابلية للتزوير الوجودي (EUF-CMA): تم إثباته في نموذج الأوراكل العشوائي (ROM)، مع رد المسألة إلى صعوبة مسألة فك تشفير المتلازمة (SD).
   • عدم القابلية للتغيير: ثبت أنه حتى لا يمكن للمنقّي تغيير الكتل غير القابلة للتغيير دون امتلاك الباب الخلفي المقابل (الذي لا يملكه).
4. التنفيذ والمقاييس: تم تنفيذ نموذج أولي بلغة بايثون باستخدام معاملات NIST الفئة 1 (Classic-McEliece: $n=3488, k=2720, t=64$).

4. النتائج والأداء

تقدم الورقة بيانات تجريبية وتحليلاً نظرياً للمخطط:

• مستوى الأمان: يحقق حوالي 128-بت من أمان ما بعد الكم (NIST Category 1).
• أحجام المفاتيح:
  • المفتاح العام: ~655.3 كيلوبايت (تهيمن عليه مصفوفتان للتحقق من التكافؤ). وهو أصغر من البديل المعتمد على الشبكات (~850 كيلوبايت).
  • حجم التوقيع: ~6.75 كيلوبايت لـ 10 كتل (يتوسع خطياً مع عدد الكتل بسبب متجهات العشوائية).
• الأداء:
  • التنقية: وقت فك تشفير باترسون النظري هو ~8 مللي ثانية لكل كتلة معدلة. (ملاحظة: استخدم النموذج الأولي بلغة بايثون بحثاً عشوائياً كان أبطأ/أقل موثوقية؛ التقدير النظري يفترض استخدام فك تشفير باترسون حقيقي).
  • التوقيع/التحقق: توسع خطي مع عدد الكتل.
• المقارنة:
  • مقابل المعتمد على الشبكات (Clermont et al.): مفاتيح عامة أصغر، شفافية أقوى (كاملة مقابل ضعيفة)، ويعتمد على فرضية صلبة عمرها 45 عاماً (فك تشفير المتلازمة) مقابل فرضية عمرها 15 عاماً (Module-LWE).
  • مقابل الكلاسيكي (RSA): مفاتيح وتوقيعات أكبر ولكن يوفر مقاومة كمومية.

5. الأهمية والقيود

الأهمية:

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

القيود:

• نموذج الأوراكل العشوائي (ROM): تعتمد مقاومة التصادم في هاش "كاميليون" على نموذج ROM. لا يوجد هاش "كاميليون" معتمد على الأكود يحقق ذلك في النموذج القياسي (Standard Model).
• حجم المفتاح: رغم أنه أصغر من البدائل المعتمدة على الشبكات، إلا أن 655 كيلوبايت لا تزال كبيرة مقارنة بمفاتيح RSA/ECC الكلاسيكية، مما قد يحد من استخدامه في أجهزة إنترنت الأشياء ذات النطاق الترددي المحدود.
• خلو التعرض (Exposure-Freeness): المخطط ليس "خالياً من التعرض". قد تؤدي عمليات التنقية المتكررة لنفس الكتلة نظرياً إلى تسريب معلومات حول الباب الخلفي.
• إخفاء السياسة (Policy Hiding): قناع القابلية (الكتل التي يمكن تعديلها) هو معلوم للعلن.

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