ملخص تقني: حاسوب كمي كامل تحت مقود كلاسيكي

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

السؤال المركزي الذي تعالجه هذه الدراسة هو ما إذا كان بإمكان عميل كلاسيكي بحت، لا يمتلك أي أجهزة كمية، استخدام خادم كمي واحد غير موثوق به وربما يكون خبيثاً كما لو كان حاسوبه الكمي الموثوق. بينما أظهرت الاختراقات السابقة، مثل بروتوكول Mahadev [Mah18b]، أن العميل الكلاسيكي يمكنه التحقق من مسائل القرار الكمية (BQP/QMA)، إلا أنها لم تمتد لتشمل القدرات الأوسع المطلوبة للكريبتوغرافيا الكمية والبروتوكولات التفاعلية. وتحديداً، يحتاج العميل الكلاسيكي إلى:

1. أخذ عينات (Sampling) من التوزيعات الكمية (SampBQP) بدلاً من مجرد اتخاذ قرارات بشأن البتات.
2. تحضير وإرسال حالات كمية تعسفية إلى طرف كمي (تحضير الحالة عن بُعد - RSP).
3. معالجة الحالات الكمية التي يوفرها الآخرون والاحتفاظ بالذاكرة الكمية عبر جولات متعددة من التفاعل دون أن يتعرف الخادم على الحالة أو يتلاعب بها.

واجهت النهج الحالية لهذه المشكلات قيوداً كبيرة:

• التحقق من أخذ العينات: حققت الأعمال السابقة [CLLW22] التحقق الكلاسيكي من أخذ العينات ولكن مع خطأ في السلامة (soundness error) بمقدار عكسي متعدد الحدود ($1/\text{poly}(T)$)، وهو أمر غير كافٍ للتطبيقات الكريبتوغرافية التي تتطلب خطأً ضئيلاً (negligible error).
• تحضير الحالة عن بُعد (RSP): كانت بروتوكولات RSP الحالية [GV19, GMP23] مقتصرة على عائلات مقيدة من الحالات وعانت من أخطاء أمنية مماثلة بمقدار عكسي متعدد الحدود، مما حال دون استخدامها في الألعاب الكريبتوغرافية القابلة للتفنيد التي تتطلب خسارة ضئيلة.
• الحفاظ على الحالة: هناك عقبة أساسية وهي أن التحقق من الحوسبة الكمية غالباً ما يؤدي إلى تدمير الحالة (عبر القياس). ولدعم البروتوكولات متعددة الجولات، يجب أن يكون العميل قادراً على اختبار حالة الخادم دون انهيارها، لضمان بقاء الخادم مرتبطاً بنفس الحالة المتطورة طوال التفاعل.

2. المنهجية والبناء الأساسي

يبني المؤلفون بروتوكول حساب ثنائي الطرف (2PC) عام الغرض، وآمن ضد الخصوم الخبيثين، بين عميل كلاسيكي وخادم كمي. يفترض البروتوكول فقط الصعوبة ما بعد الكمية لمسألة "التعلم مع الأخطاء" (LWE). البناء معياري، ويعتمد على ثلاث ركائز تقنية:

أ. حساب ثنائي الطرف (2PC) حافظ للمدخلات للدوال الكلاسيكية

الأساس هو بروتوكول 2PC حيث يدخل الطرف الكلاسيكي دالة $f$ (تحديداً كثيرات حدود متعددة الخطية من الدرجة الثابتة فوق $\mathbb{F}_2$) ويدخل الطرف الكمي حالة تراكب $|\psi\rangle = \sum \alpha_v |v\rangle$.

• الوظيفة: يقوم البروتوكول بقياس $y = f(v)$ على المدخل الكمي، ويرسل $y$ إلى الطرف الكلاسيكي، ويعيد الحالة الكمية المتبقية $|\psi_y\rangle \propto \sum_{v: f(v)=y} \alpha_v |v\rangle$ إلى الطرف الكمي.
• الحفاظ على المدخلات: من الضروري ألا تنهار حالة الطرف الكمي بما يتجاوز قياس $f(v)$. يحقق البروتوكول ذلك باستخدام دوال "الكل بلا مخلب" ذات الفخاخ المزعجة (NTCF) مع خاصية البت الصلب التكيفي.
• آلية الأمن: لإخفاء الدالة $f$ عن الخادم الكمي مع السماح للخادم بإثبات أنه قام بالحساب الصحيح للقياس، يستخدم البروتوكول حجة معرفة حافظة للشاهد (witness-preserving argument of knowledge) لـ NP. يتم إخفاء مفتاح فك التشفيد الخاص بالعميل الكلاسيكي داخل الدالة $f$. ولمنع الخادم من تعلم المفتاح من الحالة المتبقية، يستخدم المؤلفون ترميزاً عشوائياً زائداً لمدخلات الدالة والمدخلات الكمية، مما يضمن أن الأعمدة الفردية لمصفوفة الدالة محجوبة ببتات عشوائية ما لم يتم قياس الصف بأكم، (وهو ما تم أخذه في الاعتبار بالفعل في الوظيفة المثالية).
• المحاكاة: يحقق البروتوكول $\epsilon$-محاكاة، مما يعني أنه لأي $\epsilon = 1/\text{poly}(\lambda)$، يوجد محاكي يعمل في وقت متعدد الحدود في $1/\epsilon$ لا يمكن تمييزه عن التنفيذ الحقيقي. يعتمد هذا على تقنيات "الاستخراج غير المتمايز" [LMS22, KKR26]، حيث يتم كشف الشاهد مؤقتاً ثم إعادته.

ب. الالتزامات الكلاسيكية للحالات الكمية مع الارتباط المستمر

لمعالجة مشكلة "الاختبار المدمر"، قدم المؤلفون مخطط التزام جديد للحالات الكمية.

• الارتباط المثالي: في العالم المثالي، يجب على الخصم الالتزام بحالة كمية محددة جيداً $|\psi\rangle$. يمكن للمحاكي استخراج هذه الحالة.
• الارتباط المستمر: يظل المخطط مرتبطاً حتى بعد استعلامات متعددة لـ أوراكل فك التشفيد. إذا اجتاز الخصم اختباراً (قياساً)، فإنه يظل مرتبطاً بالحالة المتبقية "ما بعد القياس".
• البناء: يتم بناء هذا من خلال الربط بين الالتزامات والتوثيق الوظيفي [BBV24]. يقوم العميل بتحضير حالة موثقة عن بُعد (تحديداً حالة coset) تحت مفتاحه الخاص. تسمة فك التشفيد الخطية لمخطط التوثيق تسمح بدمجه مع الـ 2PC الحافظ للمدخلات. يساعد العميل الخادم في تحضير الحالة ولاحقاً يساعد في استعادة الحالة بعد القياسات، مما يضمن عدم قدرة الخادم على استبدال الحالة بعد اجتياز الاختبار.

ج. حساب ثنائي الطرف (2PC) حافظ للحالة للدوال الكمية العامة

بالجمع بين ما سبق، يبني المؤلفون بروتوكولاً للدوال الكمية العامة.

• حالات التاريخ (History States): يستخدم البروتوكول حالات تاريخ Feynman-Kitaev لترميز الحوسبة بأكملها.
• التحقق غير المدمر: يقوم العميل بتشغيل "اختبارات لطيفة" متكررة على حالة التاريخ الملتزم بها باستخدام الـ 2PC الحافظ للمدخلات للتحقق من عمليات الفتح الصالحة (التحقق من هاميلتونيان حالة التاريخ).
• الخصوصية: لإخفاء وصف الدائرة $U$ عن الخادم، يستخدم العميل التشفير المتماثل الكمي الكامل (QFHE). يقوم الخادم بتقييم الدائرة المشفرة بشكل متماثل. تضمن خصوصية الدائرة أن المخرجات مستقلة عن وصف الدائرة المشفرة.
• الذاكرة المستمرة: من خلال توثيق مخرجات حالة واحدة من الحوسبة وتغذيتها كمدخل للحوسبة التالية (باستخدام مفتاح جديد لكل جولة)، يمكن للعميل الحفاظ على ذاكرة كمية خاصة على الخادم عبر العديد من الحوسبات المتتالية.

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

تثبت الورقة النظرية الرئيسية التالية وتبعاتها:

النظرية 1 (غير رسمية): بافتراض الصعوبة ما بعد الكمية لـ LWE، يوجد بروتوكول تفاعلي للحوسبة الكمية الآمنة للدوائر الكمية الحقيقية بين عميل كلاسيكي وخادم كمي. يحقق البروتوكول الأمن القائم على المحاكاة مع الإجهاض (abort) باستخدام محاكي $\epsilon$. زمن تشغيل البروتوكول والأطراف النزيهة مستقل عن $\epsilon$.

تحل هذه النتيجة مشكلتين مفتوحتين رئيسيتين:

1. التحقق الكلاسيكي من أخذ العينات الكمية (SampBQP):

   • النتيجة: يمكن للعميل التحقق من توزيع مخرجات دائرة كمية محددة بـ خطأ سلامة حسابي ضئيل (negligible).
   • الأهمية: كانت البروتوكولات السابقة تعاني من خطأ عكسي متعدد الحدود. تتيح هذه النتيجة التطبيقات الكريبتوغرافية حيث يجب أن يكون الخطأ ضئيلاً وليس فقط عكسياً متعدد الحدود.

2. تحضير الحالة عن بُعد (RSP) للحالات التعسفية:

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

3. الإلغاء الكلاسيكي للشهادات الكمية:

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

4. تطبيقات إضافية

توضح الورقة تعدد استخدامات الـ 2PC عبر تجميعها في عدة أدوات كريبتوغرافية أخرى، والتي تحقق جميعها خسارة أمنية ضئيلة:

• التشفير غير القابل للاستنساخ عبر قناة كلاسيكية: يمكن لمشفر كلاسيكي إرسال نصوص مشفرة غير قابلة للاستنساخ.
• المال الكمي ذو المفتاح العام مع بنك كلاسيكي: يمكن لبنك كلاسيكي صك عملات ورقية كمية باستخدام فرضيات صعوبة متعددة الحدود فقط (LWE) والتعمية غير القابلة للتمييز (indistinguishability obfuscation)، مما يلغي الحاجة إلى فرضيات صعوبة شبه أسية مطلوبة في بناءات البنوك الكلاسيكية السابقة.
• تحسين الاستخراج لـ QMA: حجة معرفة كلاسيكية لـ QMA مع خطأ نسخة واحدة صفر وخطأ استخراج مضاف $\epsilon$ (حيث يمكن ضبط $\epsilon$ بواسطة زمن تشغيل المستخرج).
• إثباتات عدم التسلل: يمكن للخادم إثبات أنه لم يحتفظ متسلل بنسخة مفيدة من مفتاح فك التشفيد لمدقق كلاسيكي.
• التعمية الكمية (Quantum Obfuscation): يمكن لطرف كلاسيكي توزيع تعمية كمية عبر بروتوكول تفاعلي كلاسيكي.

5. الأهمية والادعاءات

يزعم المؤلفون أن هذا العمل يوفر "حاسوباً كمياً افتراضياً" تحت مقود كلاسيكي، مما يسمح لطرف كلاسيكي بحت بالعمل كطرف كمي في مجموعة متنوعة من البروتوكولات التفاعلية. تكمن الأهمية في:

• سد الفجوة: الانتقال لما وراء مسائل القرار إلى التلاعب الكامل بالحالة الكمية، وأخذ العينات، والاحتفاظ بالذاكرة.
• الصلاحية الكريبتوغرافية: من خلال تحقيق خطأ أمني ضئيل (بدلاً من عكسي متعدد الحدود)، تجعل هذه النتائج هذه الأدوات مناسبة لتعريفات الأمن الكريبتوغرافي القياسية (الألعاب القابلة للتفنيد).
• العمومية: البناء عام، ويدعم حالات يمكن تحضيرها بكفاءة وأي دوائر كمية (مقتصرة على البوابات الحقيقية، وهو افتراض قياسي وغير مقيد).
• أداة تأسيسية: يرى المؤلفون أن بروتوكول 2PC الأساسي هو أداة مفيدة على نطاق واسع لبناءات الكريبتوغرافيا الكمية المستقبلية، مما يقلل فعلياً من متطلبات الاتصال الكمي للعديد من البروتوكولات الكمية.

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