ملخص تقني: حول التكافؤ الكمي بين $\text{S|LWE}\rangle$ و $\text{ISIS}$

1. بيان المشكلة والسياق

تبحث هذه الورقة في العلاقة الحسابية بين مسألتين أساسيتين في التشفير القائم على الشبكات (Lattice-based cryptography): مسألة الحل المتباين للقيم الصحيحة القصيرة (ISIS) ومسألة البحث في LWE الكمي ($\text{S|LWE}\rangle$).

• $\text{ISIS}$: معطى مصفوفة $A \in \mathbb{Z}_q^{n \times m}$ ومتجه هدف $y \in \mathbb{Z}_q^n$، ابحث عن متجه قصير $x$ في مجموعة محددة $T$ بحيث يكون $Ax = y \pmod q$.
• $\text{S|LWE}\rangle$: معطى حالة كمية $|\psi_s\rangle = \sum_{e} f(e) |A^T s + e\rangle$، حيث $s$ هو متجه سري و $f$ هي دالة السعة، استعد السري $s$. تمثل هذه المسألة مشكلة LWE مع أخطاء في التراكب الكمي (quantum superposition).

قدمت الأعمال السابقة من قبل تشين وليو وزاندري [CLZ22] مسألة $\text{S|LWE}\rangle$ لبناء خوارما خوارزميات كمية لـ $\text{ISIS}$. وبينما كانت هناك اختزالات محددة (على سبيل المثال، من $\text{ISIS}$ إلى $\text{S|LWE}\rangle$ تحت فرضيات مقيدة، أو عبر مسائل ترميز وسيطة)، إلا أن التكافؤ العام ومدى متانة هذه الاختزالات في ظل وجود أخطاء خوارزمية ظل غير واضح. وتحديداً، طُرح سؤالان مفتوحان:

1. هل يوجد اختزال عام تماماً من $\text{ISIS}$ إلى $\text{S|LWE}\rangle$ يكون متيناً تجاه الأخطاء في حلّال $\text{S|LWE}\rangle$؟
2. هل يمكن بناء خوارزميات لـ $\text{S|LWE}\rangle$ من خوارزميات لـ $\text{ISIS}$، مما يعني شكلاً من أشكال التكافؤ؟

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

يضع المؤلفون إطار عمل للاختزال ثنائي الاتجاه بين $\text{ISIS}$ و $\text{S|LWE}\rangle$، مع تقديم مسألة وسيطة تسمى $\text{IC|LWE}\rangle$ (Inhomogeneous Construct-LWE) لتسهيل الاتجاه العكسي.

2.1 الاختزال الأمامي: $\text{ISIS} \to \text{S|LWE}\rangle$

تقدم الورقة أول اختزال عام تماماً من $\text{ISIS}$ إلى $\text{S|LWE}\rangle$.

• تحسين عن [CT25]: تطلبت الاختزالات السابقة افتراضات محددة حول حلّال $\text{S|LWE}\rangle$ (مثل استيفاء الشروط التي تستوفيها الخوارزميات الكلاسيكية ولكن ليس بالضرورة الكمية منها). يزيل هذا العمل تلك القيود، مما يجعل الاختزال صالحاً لأي خوارزمية كمية تحل $\text{S|LWE}\rangle$، حتى لو كانت تحتوي على أخطاء غير مهملة.
• تحليل الخطأ: يقوم المؤلفون بإجراء تحليل أدق للأخطاء. فبدلاً من مجرد إضافة حد خطأ يعتمد على احتمال النجاح، يقومون بدمج بنية متجهات الخطأ في الحد النهائي لاحتمال النجاح.
• النتيجة: إذا قامت خوارزمية كمية فعالة بحل $\text{S|LWE}\rangle(A, f)$ باحتمال $p$ وكان دعم تحويل فورييه لـ $f$ محتوياً داخل مجموعة الحل $T$ (حتى خطأ صغير $\eta$)، فإنه يمكن بناء خوارزمية فعالة لـ $\text{ISIS}(A, T)$. يتم تحديد احتمال النجاح بـ $p(1-\eta) - 2\sqrt{p(1-p)\eta}$.

2.2 الاختزال العكسي: $\text{S|LWE}\rangle \to \text{ISIS}$

الاتجاه العكسي أكثر تعقيداً ويتم تحقيقه من خلال اختزال مشروط يتضمن المسألة الوسيطة $\text{IC|LWE}\rangle$.

• تعريف $\text{IC|LWE}\rangle$: معطى متجه $y$، قم بإنشاء الحالة الوحدوية $|y\rangle|0\rangle \to |y\rangle|W_y\rangle$، حيث $|W_y\rangle$ هي تراكب فوق الحلول لـ $Ax=y$ موزونة بتحويل فورييه لدالة السعة.
• الخطوة 1: $\text{S|LWE}\rangle \to \text{IC|LWE}\rangle$: يثبت المؤلفون أن وجود خوارزمية فعالة لـ $\text{IC|LWE}\rangle$ يستلزم وجود خوارزمية فعالة لـ $\text{S|LWE}\rangle$. هذا الاختزال متين تجاه الأخطاء في حلّال $\text{IC|LWE}\rangle$ ولا يتطلب خصائص محددة للخوارزمية.
• الخطوة 2: $\text{IC|LWE}\rangle \to \text{ISIS}$ (مشروط): لاسترداد $\text{IC|LWE}\rangle$ إلى $\text{ISIS}$، قدم المؤلفون مفهوم الخوارزميات ذات الدعم الكامل والقابلة لاستعادة العشوائية (full-support randomness-recoverable algorithms). تُوصف خوارزمية $\text{ISIS}$ بأنها "قابلة لاستعادة العشوائية" إذا كان يمكن استعادة شريط العشوائية الداخلي المستخدم لتوليد الحل من الحل نفسه. وتكون "ذات دعم كامل" إذا كان توزيع المخرجات موحداً على جميع الحلول الصالحة.
• مبرهنة: إذا وُجدت خوارزمية كلاسيكية فعالة لـ $\text{ISIS}$ تكون كلتا الصفتين (الدعم الكامل واستعادة العشوائية) متوفرة فيها، فإنه توجد خوارزمية كمية فعالة لـ $\text{IC|LWE}\rangle$ (وبالتالي $\text{S|LWE}\rangle$).

2.3 التجسيد واستعادة النتائج الحالية

لإثبات عملية الاختزال العكسي، يقوم المؤلفون بتجسيد هذا الإطار باستخدام نسخة معدلة من خوارزمية كلاسيكية معروفة لـ $\text{ISIS}$ (مقتبسة من عمل ريجيف و [CLZ22]).

• التعديل: قاموا بتعديل الخوارزمية الكلاسيكية لضمان استيفائها لشروط "استعادة العشوائية" و"الدعم الكامل" الصارمة.
• المعلمات: يعمل هذا التجسيد تحديداً عندما يكون المعامل $q$ قوة صغيرة للعدد 2 ($q=2^l$).
• النتيجة: من خلال وضع حلّال $\text{ISIS}$ المعدل هذا في سلسلة الاختزال الخاصة بهم، يستعيدون نتائج باي وآخرون [BJK+25]، الذين قدموا خوارما كمية لـ $\text{S|LWE}\rangle$ (المصاغة كمسألة EDCP) تعمل في وقت دون أسي لـ $q=2^l$.
• المقارنة: يشير المؤلفون إلى أن نهجهم أبسط هيكلياً من [BJK+25]، حيث يعتمد على تحويل فورييه كمي (QFT) عالمي واحد وتطبيق متماسك لخوارزمية $\text{ISIS}$، بدلاً من الاقتران المتكرر ونخل (sieving) حالات كمية متعددة.

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

1. الاختزال الأمامي العام: تم إثبات اختزال متين ومتسامح مع الأخطاء من $\text{ISIS}$ إلى $\text{S|LWE}\rangle$، وهو صالح لأي حلّال $\text{S|LWE}\rangle$ كمي.
2. الاختزال العكسي المشروط: تم إثبات اختزال من $\text{ISIS}$ إلى $\text{S|LWE}\rangle$، وهو مشروط بوجود حلّال $\text{ISIS}$ ذي دعم كامل وقابل لاستعادة العشوائية.
3. التكافؤ في حالات محددة: بالنسبة للحالة التي يكون فيها $q$ قوة للعدد 2، توضح الورقة أن صعوبة $\text{S|LWE}\rangle$ مرتبطة ارتباطاً وثيقاً بصعوبة $\text{ISIS}$، حيث يمكن تحويل الخوارزميات الموجودة لأحدهما إلى الآخر.
4. المسألة الوسيطة: أظهر تقديم مسألة $\text{IC|LWE}\rangle$ أنه جسر مفاهيمي حاسم، مما يوضح العلاقة بين مسألة الشبكة غير المتجانسة ومسألة بناء الحالة الكمية.

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

تدعي الورقة توضيح "مشهد الاختزالات" بين $\text{S|LWE}\rangle$ و $\text{ISIS}$.

• ارتباط قوي: تثبت أن المسألتين مرتبطتان بقوة؛ وتحديداً، فإن حل إحداهما (تحت الشروط المعرفة) يسمح بحل الأخرى.
• عوائق التكافؤ الكامل: يشير المؤلفون بتواضع إلى أن التكافؤ الكامل لم يُثبت بعد لجميع الحالات. يعتمد الاختزال العكسي على وجود خوارزميات $\text{ISIS}$ "قابلة لاستعادة العشوائية"، وهي صفة صارمة ولم تُثبت حالياً إلا لأنظمة معلمات محددة (مثل $q=2^l$).
• اختزال غير فاقد (Lossless Reduction): على عكس سلاسل الاختزال السابقة (مثل $\text{S|LWE}\rangle \to \text{LWE} \to \text{SIS} \to \text{ISIS}$) التي تكون فاقدة للمعلومات وأحادية الاتجاه، فإن الاختزالات المقدمة هنا هي "غير فاقدة" بمعنى أن المصفوفة $A$ تظل دون تغيير، وفي أنظمة محددة، يمكن تركيب الاختزالات الأمامية والعكسية لاستعادة المسألة الأصلية دون تدهور في المعلمات.
• الاتجاهات المستقبلية: يقترح المؤلفون أن توسيع هذه الاختزالات لتشمل نظرية الترميز (خارج نطاق الشبكات) قد يعالج الأسئلة المفتوحة المتعلقة بالتداخل الكمي المرمّز (Decoded Quantum Interferometry). كما يفترضون أن إيجاد خوارزميات جديدة لـ $\text{ISIS}$ قد يؤدي مباشرة إلى خوارزميات كمية جديدة لـ $\text{S|LWE}\rangle$ عبر إطار عملهم.

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