⚛️ quantum physics

A Simple and Efficient One-Shot Signature Scheme

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

المؤلفون الأصليون: Andrew Huang, Vinod Vaikuntanathan

نُشر 2026-07-28

📖 5 دقيقة قراءة🧠 قراءة متعمّقة

CC BY 4.0

المؤلفون الأصليون: Andrew Huang, Vinod Vaikuntanathan

البحث الأصلي مرخَّص بموجب CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ هذا شرح مولَّده بالذكاء الاصطناعي للبحث أدناه. لم يكتبه المؤلفون ولم يصادقوا عليه. وللتحقق من الدقة التقنية، يرجى الرجوع إلى البحث الأصلي. اقرأ إخلاء المسؤولية الكامل

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

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

التذكرة ذاتية التدمير

يتناول البحث مشكلة في التشفير الكمي تُعرف باسم "التوقيعات لمرة واحدة" (OSS). لفهم هذا الإنجاز، تخيل أنك جاسوس يحاول إرسال رسالة سرية. في النسخة القديمة الضخمة من لعبة الجاسوس هذه، كان "التوقيع" (الإثبات على أنك أنت من أرسل الرسالة) يشبه حقيبة ظهر ضخمة وثقيلة. إذا أردت توقيع ملاحظة قصيرة، كان عليك حمل حقيبة ظهر تحتوي على $\Theta(\lambda^4)$ من الكيوبتات (المكافئ الكمي للبتات). وإذا أردت توقيع رسالة أطول، كانت حقيبة الظهر تصبح أكبر، وكانت عملية التوقيع بطيئة ومعقدة، وغالباً ما تتطلب من الجاسوس القيام برقصة معقدة من القياسات الكمية لإتمام المهمة.

يقول مؤلفا الورقة: "يمكننا تقديم الأفضل". لقد صمما نظاماً جديداً ومبسطاً حيث تكون "حقيبة الظهر" أصغر بكثير. فبدلاً من حمولة حقيبة ضخمة تبلغ $\Theta(\lambda^4)$ من الكيوبتات، يحتاج نظامهم الجديد فقط إلى حقيبة تبلغ $\Theta(\lambda^2)$ من الكيوبتات. هذا تقليل هائل في الحجم. علاوة على ذلك، فإن التوقيعات التي ينتجونها أصغر أيضاً، حيث تقلصت من $\Theta(\lambda^3)$ بت إلى $\Theta(\lambda^2)$ بت.

كيف فعلوا ذلك: خدعة "الصورة"

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

لكن هوانغ وفايكونتاناثان قلبا الآية. فبدلاً من البحث عن الإبرة في القش، قررا البحث عن القش في الإبرة. في بنائهما الجديد، يتم العثيد على "التوقيع" مباشرة في "صورة" الدالة. لقد استخدما خوارزمية بحث كمي ذكية (بحث غروفر - Grover's search) لإيجاد المسار الصحيح عبر البيانات. هذا النهج يشبه امتلاك خريطة تقودك مباشرة إلى الكنز، بدلاً من الحفر عشوائياً. ولأنهم يبحثون في المكان الصحيح، فإن العملية "صحيحة تماماً"؛ وهذا يعني أن كل مرة تحاول فيها توقيع رسالة، يضمن النظام نجاح العملية. لا توجد فرصة للفشل، ولا توجد لحظات من نوع "عذراً، التذكرة لم تعمل".

لماذا هذا مهم: النار الكمية

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

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

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

الخلاصة

لقد أثبت المؤلفان أنه من الممكن إنشاء نظام توقيع لمرة واحدة يكون:

فعالاً: يستخدم ذاكرة كمية أقل بكثير ( $\Theta(\lambda^2)$ كيوبت) وينتج توقيعات أصغر ( $\Theta(\lambda^2)$ بت) مقارنة بالأفضل سابقاً ( $\Theta(\lambda^4)$ و $\Theta(\lambda^3)$ ).
بسيطاً: يتجنب الدوائر الكمية المعقدة متعددة الخطوات التي جعلت الطريقة القديمة بطيئة وصعبة الفهم.
مثالياً: يعمل في كل مرة، مع صفر احتمال للفشل.
آمناً: يمنع المخترقين من ضغط البيانات للغش في النظام، مما يتيح إنشاء "النار الكمية" وغيرها من أدوات الأمن المتقدمة.

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

ملخص تقني: مخطط توقيع بسيط وفعال لمرة واحدة (One-Shot Signature Scheme)

بيان المشكلة

تُعد التوقيعات لمرة واحدة (OSS) من البدائيات التشفيرية الكمومية الفريدة التي تسمح للمستخدم بإنشاء مفتاح تحقق عام ($pk $) وحالة توقيع كمومية سرية ($ |sk\rangle$). تتيح حالة التوقيع إنتاج توقيع صالح لرسالة واحدة فقط من اختيار المستخدم؛ وعند التوقيع، "تدمر" الحالة نفسها، مما يمنع توليد توقيع ثانٍ. وبينما تنطوي الـ OSS على بدائيات قوية مثل النقود الكمومية (Quantum Money)، والبرق الكمومي (Quantum Lightning)، والنار الكمومية (Quantum Fire)، إلا أن بناء هذه البدائيات بكفاءة ظل تحديًا كبيرًا.

قدم الاختراق الأخير الذي حققه شمويل وزاندري (SZ) [SZ25] أول بناء لـ OSS. ومع ذلك، يعاني مخططهم من عدم كفاءة كبيرة:

التوقيع بتسلسل البتات (Bit-by-bit): يتطلب بناء SZ بطبيعته توقيع الرسائل بتًا تلو الآخر. لتوقيع رسالة بطول $\lambda$ بت، يتطلب المخطط تكرارًا متوازيًا، مما يؤدي إلى تضخم خطي في أحجام المفاتيح والتوقيعات.
التضخيم المعقد: لتحقيق أمن قوي، يعتمد SZ على اختزال "دال'أنول وسبونر" (DS) [DS22]، والذي يستخدم دوائر إعادة التدوير الكمومي المعقدة أو تحويل القيمة المفردة الكمومي (QSVT) (تحديدًا خوارزميات الإسقاط المتناوب/نمط ماريوت-واترو). وهذا يضيف عبئًا إضافيًا قدره $\Theta(\lambda)$ على حجم مفتاح التوقيع.
صحة غير مثالية: يحتوي مخطط SZ على خطأ في الصحة (Correctness Error) ضئيل، مما يعني أن خوارزمية التوقيع قد تفشل في إنتاج توقيع صالح.
تكاليف الموارد: في نموذج الأوراكل (Oracle Model)، ينتج عن مخطط SZ مفاتيح توقيع بحجم $\Theta(\lambda^4)$ كيوبت وتوقيعات بحجم $\Theta(\lambda^3)$ بت. وفي النموذج العادي (Plain Model)، تكون هذه المعلمات أكبر من ذلك.

علاوة على ذلك، حاولت عمل لاحق من قبل تشاكان، غويال، وشمويل (CGS) [C¸GS25] استخدام OSS لبناء "نار كمومية ذات مفتاح عام"، لكنها اعتمدت على خاصية عدم القابلية للانضغاط (Incompressibility) التي لا يستوفيها مخطط SZ.

المنهجية

يقترح هذا العمل بناءً مباشرًا جديدًا للتوقيعات لمرة واحدة يتجنب الاختزالات المعقدة والتكرارات المتوازية المطلوبة في المقاربات السابقة. وتتمثل المنهجية الجوهرية في تغيير جذري في كيفية توليد التوقيع:

1. البناء المباشر عبر بحث غروفر (Grover Search)

بدلاً من نهج SZ، الذي يبحث عن سابقة صورة (Preimage) لدالة هاش تبدأ ببت محدد (مما يتطلب تضخيماً معقداً للتعامل مع مشكلة "الربط بالجمع" - sum-binding)، يبحث هذا العمل عن توقيع في صورة دالة.

الإعداد: يستخدم المخطط تبديلاً عشوائيًا $\Pi$ وعائلة من الفضاءات الجزئية المعرفة بواسطة المصفوفات $\mathbf{A}_y$ والمتجهات $\mathbf{b}_y$ . حالة التوقيع $|sk\rangle$ هي تراكب منتظم فوق فضاء أفيني (Coset) محدد بهذه المعلمات.
عملية التوقيع: لتوقيع بت $b$ ، لا تبحث الخوارزمية عن سابقة صورة تبدأ بـ $b$ . بدلاً من ذلك، تستخدم خوارزمية بحث غروفر لتحويل حالة التراكب الأولية إلى حالة تكون فيها متجهات الـ coset تمتلك بادئة (Prefix) محددة $b$ في صورتها تحت دالة مساعدة $\mathcal{P}$ .
استخدام الأوراكل: تطبق خوارزمية التوقيع بشكل تكراري نوعين من أوراكل الانعكاس:
1. أوراكل طور (Phase Oracle) يحدد الحالات التي تتطابق فيها بادئة الصورة مع بت الرسالة.
2. أوراكل مزدوج $\mathcal{D}$ يعكس عبر المزدوج (Dual) للفضاء الجزئي.
  من خلال تكرار هذه العملية $\ell$ مرة (حيث $\ell$ هو طول الرسالة)، تقوم الخوارزمية بتدوير الحالة إلى تراكب للتوقيعات الصالحة للرسالة بأكملها. ويؤدي قياس هذه الحالة إلى الحصول على توقيع صالح.

2. ضمان الصحة المثالية

يعالج المؤلفون مسألة الصحة غير المثالية من خلال التصميم الدقيق لأخذ عينات المصفوفة $\mathbf{A}_y$ . فهم يضمنون أن العمود الأول من $\mathbf{A}_y$ غير صفري، مما يضمن أنه لأي مفتاح عام $y$ ، يحتوي الـ coset على متجهات تبدأ بكل من 0 و 1. هذا الضمان الهيكلي يضمن نجاح بحث غروفر دائمًا، محققًا صحة مثالية (احتمالية 1).

3. التعامل مع الرسائل ذات الطول متعدد الحدود

بدلاً من تكرار مخطط البت الواحد $\lambda$ مرة (مما يسبب تضخمًا بمقدار $\lambda$ )، يقوم المخطط بتوقيع الرسالة كاملة بطول $\lambda$ بت في دفعة واحدة. يتم تكييف بحث غروفر لتوقيع الرسالة بتًا بت داخل تنفيذ واحد، مما يضغط التوقيعات $\lambda$ في توقيع واحد بحجم $\Theta(\lambda^2)$ . بالنسبة للأطوال متعددة الحدود التعسفية، يتم تطبيق تحويل "الهاش والتوقيع" (Hash-and-Sign) القياسي.

4. عدم القابلية للانضغاط والنار الكمومية

يحدد البحث خللاً في ادعاء CGS [C¸GS25] بأن مخطط SZ يستوفي "خاصية عدم قابلية انضغاط التوقيع القوية". يفشل مخطط SZ في هذه الخاصية لأن خوارزمية التوقيع تتطلب الوصول إلى كل من الأوراكل الأمامي والعكسي ( $\mathcal{P}$ و $\mathcal{P}^{-1}$ )، مما يسمح للمهاجم بتوليد توقيعات لمفاتيح خارج قائمة مضغوطة.
يقوم البناء الجديد بتعديل المخطط بحيث يتطلب التوقيع فقط الأوراكل المزدوج $\mathcal{D}$ ، بينما يستخدم التحقق أوراكلًا منفصلاً $\mathcal{D}_0$ . هذا الفصل يتيح إثبات عدم قابلية انضغاط التوقيع القوية، مما يستعيد صلاحية تطبيقات "النار الكمومية" التي اقترحها CGS.

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

تحسينات الكفاءة

يحقق البحث تخفيضات كبيرة في تعقيد الموارد مقارنة ببناء SZ:

حجم مفتاح التوقيع: انخفض من $\Theta(\lambda^4)$ كيوبت إلى $\Theta(\lambda^2)$ كيوبت.
حجم التوقيع: انخفض من $\Theta(\lambda^3)$ بت إلى $\Theta(\lambda^2)$ بت.
حجم المفتاح العام: انخفض من $\Theta(\lambda^3)$ بت (نموذج الأوراكل) و $\Theta(\lambda^5)$ بت (النموذج العادي) إلى $\Theta(\lambda^2)$ بت (نموذج الأوراكل) و $\Theta(\lambda^4)$ بت (النموذج العادي).
وقت التشغيل: تتطلب خوارزمية التوقيع عدد استعلامات أوراكل أقل بكثير، متجنبة العبء الإضافي $\Theta(\lambda)$ المرتبط بدارات QSVT/إعادة التدوير.

الأمن والصحة

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

النتائج النظرية

يصيغ البحث هذه التحسينات في مبرهنتين رئيسيتين:

المبرهنة 1.1: تثبت وجود مخططات OSS فعالة للرسائل طويلة متعددة الحدود بصحة مثالية في كل من نموذج الأوراكل الكلاسيكي (بشكل غير مشروط) والنموذج العادي (بافتراض تعمية التمييز ما بعد الكمي والـ LWE).
المبرهنة 1.2: توضح أن مخطط OSS الجديد غير القابل للانضغاط يتيح بناء مخططات "النار الكمومية ذات المفتاح العام" و"النار المفتاحية" (Key-fire) بصحة مثالية، مما يصحح الأخطاء في عمل CGS [C¸GS25].

الأهمية

يدعي البحث تقديم بديل "بسيط ومباشر وفعال" لأحدث مخططات التوقيع لمرة واحدة. ومن خلال تجاوز الاختزالات المعقدة (DS [DS22]) واستراتيجيات التكرار المتوازي المستخدمة في الأعمال السابقة، يحقق المؤلفون تحسنًا تربيعيًا في أحجام المفاتيح والتوقيعات.

تتجلى أهمية هذا العمل في جانبين:

الكفاءة العملية: يجعل التوقيعات الكمومية أكثر جدوى من الناحية العملية عبر تقليل متطلبات الكيوبت والبت من المقاييس الرباعية/التكعيبية إلى المقاييس التربيعية.
التصحيح التأسيسي: يصحح فجوة حرجة في الأدبيات المتعلقة بعدم قابلية انضغاط الـ OSS. ومن خلال إصلاح خاصية عدم القابلية للانضغاط، يثبت هذا البحث صحة بناء "النار الكمومية" والبدائيات ذات الصلة، والتي كان يُزعم سابقًا إمكانية بنائها ولكنها اعتمدت على افتراض خاطئ حول مخطط SZ.

يشير المؤلفون إلى أنه بينما قاموا بتحسين المعلمات بشكل كبير، فإن أي تحسينات أخرى لـ $\Theta(\lambda)$ في نموذج الأوراكل قد تتطلب تقنيات جديدة تمامًا، حيث تكمن العقبة الحالية في تحليل حالة "الخلو من المزدوج" (Dual-free case). وبالمثل، يظل تحسين معلمات النموذج العادي مسألة مفتوحة.