Simon's Algorithm for the Even-Mansour Cipher on Quantum Hardware

إليك ملخص تقني مفصل لورقة بحثية بعنوان "خوارزمية سايمون لتشفير إيفن-مانسور على الأجهزة الكمومية".

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

تتناول الورقة البحثية الجدوى العملية لتنفيذ هجمات تحليل التشفير الكمومي على التشفيرات المتماثلة باستخدام أجهزة NISQ (الكمومية متوسطة الحجم ذات الضجيج) الحالية. وتستهدف تحديداً تشفير إيفن-مانسور (Even-Mansour)، وهو بناء تشفير كتل (block cipher) أدنى يعتمد على تبديل عام ومفتاحين سريين.

بينما يعد الإطار النظري لكسر تشفير إيفن-مانسور باستخدام خوارماية سايمون (Simon's Algorithm) راسخاً (حيث توفر تسارعاً أسياً مقارنة بالهجمات الكلاسيكية من خلال إيجاد دور مخفي)، إلا أن التنفيذ العملي ظل محدوداً. وتشمل التحديات الجوهرية ما يلي:

• قيود الأجهزة: تعاني أجهزة NISQ من الضجيج، وفقدان الترابط (decoherence)، واتصال محدود بين الكيوبتات، مما يجعل تنفيذ الدوائر العميقة (المطلوبة للتبديلات المعقدة) أمراً صعباً.
• اختناقات تركيب الدوائر: إن تحويل التبديلات التشفيرية الكلاسيكية (S-boxes) إلى دوائر كمومية قابلة للعكس ومحسنة هو عملية مكلفة حاسوبياً. وغالباً ما تفشل الأدوات الموجودة في التوسع لتشمل أطوال مفاتيح أكبر بسبب قيود الذاكرة.
• تنفيذ الأوراكل (Oracle): يتطلب الهجوم تنفيذ دالة التشفير كأوراكل كمومي، وهو ما يتطلب تركيب التبديلات غير الخطية في بوابات كمومية.

2. المنهجية

قام المؤلفون بتنفيذ هجوم إثبات مفهوم على معالج ibm_miami من شركة IBM. تضمنت المنهجية ثلاث مراحل رئيسية:

أ. البناء التشفيري

• التشفير: مخطط إيفن-مانسور $EM_{k_1, k_2}(x) = P(x \oplus k_1) \oplus k_2$، حيث $P$ هو تبديل عام و $k_1, k_2$ هما مفتاحان سريان.
• التبديل ($P$): بالنسبة لـ $N=3$ و $N=4$، صمم المؤلفون خرائط تقابلية مستوحاة من صندوق S الخاص بـ AES. تم تعريف هذه الخرائط كعملية قلب في الحقل المحدود $F_{2^N}$ متبوعة بتحويل أفيني (affine transformation).
• ناقل الهجوم: يحدد الهجوم دالة $f(x) = EM(x) \oplus P(x)$. تمتلك هذه الدالة دوراً مخفياً هو $k_1$. تُستخدم خوارزمية سايمون لإيجاء $k_1$، وبعد ذلك يتم استرداد $k_2$ كلاسيكياً أو عبر استعلام كمومي بسيط.

ب. تركيب الدائرة الكمومية (DORCIS)

• سلسلة الأدوات: استخدم المؤلفون أداة DORCIS (التركيب العميق المحسن لصناديق الاستبدال) لتركيب جداول التبديل الكلاسيكية في دوائر كمومية قابلة للعكس.
• التحسين: تقوم أداة DORCIS بتفكيك التبديلات إلى بوابات أولية (Pauli-X، Toffoli/CCNOT، SWAP) وتقليل عمق الدائرة.
• حد التوسع: نجحت الأداة في توليد دوائر لـ $N=3$ و $N=4$، لكنها فشلت عند $N=5$ بسبب اختناق في الذاكرة على وحدة معالجة مركزية عالية الأداء (ذاكرة وصول عشوائي بسعة 3.9 تيبايت)، مما منع توليد دوائر لنماذج أكبر.

ج. التنفيذ على الأجهزة وتخفيف الأخطاء

لتنفيذ الهجوم على معالج ibm_miami المليء بالضجيج، استخدم الفريق استراتيجيات تخفيف محددة:

• تخطيط الكيوبتات (Qubit Mapping): قاموا يدوياً برسم خرائط الكيوبتات المنطقية إلى رسوم بيانية فرعية محددة للكيوبتات الفيزيائية ($[0, 1, 2, 12, 11, 10]$ لـ $N=3$ و $[0, 1, 2, 3, 13, 12, 11, 10]$ لـ $N=4$) للاستفادة من طوبولوجيا الشبكة وتجنب عبء التوجيه التلقائي.
• إلغاء الاقتران الديناميكي (Dynamical Decoupling - DD): تم تطبيق تسلسلات متناظرة من الوحدات (مثل نبضات X المتبادلة) على الكيوبتات الخاملة لتثبيط ضجيج البيئة منخفض التردد والتداخل (crosstalk).
• تجعيد باولي (Pauli Twirling): تم إدراج أزواج مؤثرات باولي متكافئة منطقياً بشكل عشوائي قبل وبعد البوابات لتحويل الأخطاء المتماسكة إلى أخطاء باولي عشوائية، مما يمنع التشوهات الطورية المنهجية التي قد تحجب التصادمات الهيكلية للخوارزمية.

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

1. أول عرض عملي: هذا هو إثبات مفهوم ناجح يوضح استعادة المفتاح السري لتشفير إيفن-مانسور على أجهزة كمومية فعلية ($N=3$ و $N=4$).
2. التحقق من تخفيف الأخطاء: تؤكد الورقة أن الجمع بين إلغاء الاقتران الديناميكي وتجعيد باولي يسمح لخوارزمية سايمون بالعمل بفعالية رغم أعماق الدائرة الكبيرة والضجيج المتأصل في أجهزة NISQ.
3. تحديد الاختناقات الكلاسيكية: تسلط الدراسة الضوء على أن العامل المحدد لتوسيع هذه الهجمات هو حالياً المعالجة المسبقة الكلاسيكية (تركيب الدائرة) وليس الأجهزة الكمومية نفسها. فقد فشلت أداة DORCIS عند $N=5$ بسبب قيود الذاكرة.
4. البيانات التجريبية: يقدم المؤلفون توزيعات إحصائية مفصلة لنتائج القياس، مما يظهر أن النتائج التجريبية تتوافق مع التوقعات النظرية عند أخذ الضجيج في الاعتبار.

4. النتائج

• حالة 3-بت ($N=3$):
  • تم بنجاح استعادة المفتاح السري $k_1 = (0, 1, 0)$ و $k_2 = (1, 1, 0)$.
  • كان عمق الدائرة 23 (عمق T بلغ 3).
  • بعد 5 تجارب مستقلة (105 محاولة لكل منها)، كان توزيع القياس يتركز بوضوح عند المتجهات المتعامدة مع الدور الحقيقي، مما سمح باستعادة المفتاح عبر الجبر الخطي بنجاح.
• حالة 4-بت ($N=4$):
  • تم بنجاح استعادة $k_1 = (0, 1, 0, 1)$ و $k_2 = (1, 1, 0, 1)$.
  • زاد عمق الدائرة إلى 54 (عمق T بلغ 7).
  • رغم زيادة العمق والضجيج، ظل توزيع النتائج متميزاً بما يكفي لحل نظام المعادلات الخطية للمفتاح.
• تحليل الخطأ:
  • قام المؤلفون بنمذجة الضجيج كقناة إزالة استقطاب (depolarizing channel). وقدروا معامل الضجيج $p \approx 0.434$ بناءً على معدلات خطأ البوابات وإجمالي عدد النبضات.
  • تطابقت البيانات التجريبية مع التوزيع النظري المشوب بالضجيج، مما أكد أن الانحرافات كانت بسبب ضجيج الأجهزة وليس فشل الخوارزمية.
• فشل التوسع: لم تستطع أداة DORIS توليد دائرة لـ $N=5$، مما يشير إلى أن أدوات التركيب الكلاسيكية الحالية ليست قابلة للتوسع بعد لأطوال المفاتيح الأكبر.

5. الأهمية

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