A Note on the Equivalence Between Zero-knowledge and Quantum CSS Codes

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

تتناول الورقة العلاقة بين عائلتين متميزتين من أكواد تصحيح الأخطاء التي تمت دراستها تاريخياً في مجالات منفصلة:

• أكواد المعرفة الصفرية (Zero-Knowledge Codes): قدمها ديكاتور، وجولدريش، ورون، وهي أكواد كلاسيكية حيث يضمن الترميز العشوائي أن مراقبة عدد صغير من رموز الكلمة المشفرة لا تكشف أي معلومات عن الرسالة المشفرة. وهي أساسية للبروتوكولات التشفيرية مثل الحوسبة متعددة الأطراف (MPC) وبراهين المعرفة الصفرية (ZK-PCPs).
• أكواد CSS الكمومية (Quantum CSS Codes): قدمها كالدردربيرك، وشور، وستاين، وهي أزواج من الأكواد الخطية الكلاسيكية تُستخدم لتصحيح الأخطاء الكمومية. وهي ضرورية للحوسبة الكمومية ذات الخطأ المتسامح والقفزات النوعية الأخيرة في التعقيد الكمومي (مثل فرضية Quantum PCP).

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

2. المنهجية

يضع المؤلفان تكافؤاً رياضياً صارماً بين أكواد المعرفة الصفرية الخطية، الكاملة، وغير التكيفية وبين أكواد CSS الكمومية.

التحويل الجوهري

تعتمد المنهجية على تحويل ثنائي الاتجاه بين هيكلي الكود:

1. من المعرفة الصفرية (ZK) إلى CSS: بالنظر إلى كود خطي $C$ مع مصفوفة مولدة $G$ وخريطة ترميز عشوائية (حيث يتم حشو الرسالة ببتات عشوائية)، يقوم المؤلفون ببناء كود CSS $(C_X, C_Z)$:
   • يتم تعيين $C_X$ لتكون الكود $C$.
   • يتم تعريف $C_Z$ كالفضاء الجزئي العمودي على امتداد أعمدة "العشوائية" (آخر $k-k'$ عمود من $G$).
2. من CSS إلى المعرفة الصفرية (ZK): على العكس من ذلك، بالنظر إلى كود CSS $(C_X, C_Z)$، يقوم المؤلفون ببناء كود ZK عبر معاملة $C_X$ كالكود الأساسي واستخدام أساس $C_Z^\perp$ (الذي هو فضاء جزئي من $C_X$) لتعريف العشوائية في الترميز.

الرؤية التقنية الرئيسية

يثبت المؤلفون أن الخصائص المحددة لأحد أنواع الأكواد ترتبط مباشرة بالخصائص المحددة للنوع الآخر:

• خاصية ZK $\leftrightarrow$ مسافة $d_Z$: الشرط الذي يخفي فيه كود ZK المعلومات حول الرسالة عند مراقبة $t$ من الرموز يكافئ رياضياً شرط أن يكون لكود CSS مسافة دنيا $d_Z > t$ (تحديداً، لا يوجد متجه في $C_Z \setminus C_X^\perp$ وزنه $\le t$).
• القابلية لفك التشفير $\leftrightarrow$ مسافة $d_X$: القدرة على فك تشفير الرسالة من كلمة مشفرة تالفة (تصحيح الخطأ) في سياق ZK تكافئ كون كود CSS يمتلك مسافة دنيا $d_X > 2e$ (لا يوجد متجه في $C_X \setminus C_Z^\perp$ وزنه $\le 2e$).

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

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

1. مبرهنة التكافؤ الرسمي: تقدم الورقة المبرهنة 3.1 والنتيجة 3.2، اللتين تنصان وتثبتان رسمياً أن أكواد ZK الخطية الكاملة وأكواد CSS الكمومية هي هياكل متكافئة. وهذا يسمح بترجمة المعاملات (المعدل، المسافة، عتبة ZK) مباشرة بين الإطارين.
2. توصيف جديد لأكواد ZK: يقدم المؤلفون إثباتاً بديلاً ومكتفياً بذاته لتوصيف أكواد ZK (التمهيدية 3.3)، بربط خاصية ZK مباشرة بالاستقلال الخطي لتراكيب الصفوف في المصفوفة المولدة بالنسبة لتقسيمات الرسالة والعشوائية.
3. بناء أكواد ZK-LTC جيدة تقاربياً بشكل صريح: التطبيق الأكثر أهمية لهذا التكافؤ هو بناء أكواد المعرفة الصفرية المحلية القابلة للاختبار (ZK-LTCs).
   • قبل هذا العمل، لم تكن معروفة إنشاءات صريحة لأكواد ZK-LTC جيدة تقاربياً ذات عتبة ZK أكبر بكثير من تعقيد الاستعلام.
   • من خلال دمج التكافؤ مع الاختراقات الأخيرة في أكواد LTC الكمومية الجيدة تقاربياً (تحديداً عمل دينور، وليو، وفيدرمان [DLV24] وآخرين)، يستنتج المؤلفون عائلة صريحة من أكواد ZK الكلاسيكية.

4. النتائج

يؤدي تطبيق التكافؤ إلى النتيجة 4.3، التي تثبت وجود عائلة لانهائية صريحة من الأكود $C_n$ تمتلك الخصائص التالية:

• جيدة تقاربياً: تمتلك الأكود معدلاً ثابتاً ومسافة خطية ($\Omega(n)$).
• قابلة للاختبار محلياً: يمكن اختبارها بعدد استعلامات لوغاريتمي متعدد ($\text{poly}(\log n)$).
• معرفة صفرية (Zero-Knowledge): تمتلك عتبة ZK قدرها $\Omega(n)$ (خطية في طول الكتلة).
• قابلة لفك التشفير: يمكن فك تشفيرها من $\Omega(n)$ من الأخطاء.

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

5. الأهمية

• التلاقح بين المجالات: توضح الورقة أن هناك روابط هيكلية عميقة بين التشفير الكلاسيكي (أكواد ZK) ونظرية المعلومات الكمومية (أكواد CSS). وهي تشير إلى أن أدوات وإنشاءات التعقيد الكمومي يمكن أن تحل مشكلات طويلة الأمد في التشفير الكلاسيكي.
• التقدم في البدائيات التشفيرية: تعد أكواد ZK-LTC الناتجة مكونات حاسمة لبناء براهين المعرفة الصفرية القابلة للفحص محلياً (ZK-PCPs) وبراهين المدارات التفاعلية (ZK-IOPs) عالية الكفاءة. وهذه تعتبر أساسية لـ SNARKs الحديثة والحوسبة القابلة للتحقق.
• الكفاءة: يوفر الإنشاء أكواداً بمعاملات أفضل (الصراحة، عتبة ZK عالية، القابلية للاختبار المحلي) من الإنشاءات الصريحة المعروفة سابقاً، مما قد يؤدي إلى بروتوكولات تشفيرية أكثر كفاءة.
• الرؤية النظرية: يوضح التكافؤ طبيعة "إخفاء" المعلومات في الأكود، مبيناً أنها متطابقة هيكلياً مع خصائص "المسافة" المطلوبة لتصحيح الأخطاء الكمومية.