Certified Randomness without Structure Against Shallow-Query Adversaries
تثبت هذه الورقة البحثية دون شروط أمن بروتوكول ياماكاوا-زاندري للعشوائية القابلة للتحقق ضد الخصوم الكميين ذوي الاستعلامات الضحلة، مما يؤسس للعشوائية المعتمدة دون الاعتماد على فرضية آرونسون-أمبين غير المثبتة.
المؤلفون الأصليون:Dakshita Khurana, Bhaskar Roberts, Avishay Tal
تُعد العشوائية المحرك الخفي للأمن الحديث، والشرارة غير المتوقعة التي تمنع كسر الأقفال الرقمية وسرقة الأسرار. في العالم الكلاسيكي، تُعتبر العشوائية الحقيقية رفاهية؛ فالأجهزة الحاسوبية هي آلات حتمية تتبع قواعد صارمة، مما يعني أن أي رقم تولده هو، من حيث المبدأ، قابل للتنبؤ به إذا عرفت نقطة البداية. أما ميكانيكا الكم فتقدم مساراً مختلفاً؛ ولأن عملية قياس نظام كمي هي بطبيعتها احتمالية، يمكن لجهاز كمي أن ينتج مخرجات لا يمكن التنبؤ بها بشكل جوهري، حتى لمراقب يمتلك معرفة كاملة بإعدادات الجهاز. لكن هذا يخلق مشكلة ثقة: كيف يمكن لمراقب كلاسيكي، لا يستطيع رؤية الحالة الكمية، أن يتأكد من أن الجهاز يستخدم بالفعل هذه العشوائية الكمية وليس مجرد تظاهر بذلك؟ يحتاج المراقب إلى وسيلة للمصادقة على أن المخرج عشوائي حقاً، وليس إجابة محددة مسبقاً متنكرة في زي الصدفة.
لسنوات، حاول الباحثون حل هذه المعضلة بالاعتماد على افتراضات رياضية معقدة حول مدى صعوبة حل مسائل معينة، أو من خلال اشتراط فصل الأجهزة الكمية فيزيائياً لمنعها من محاكاة السلوك المتوقع. وقد قدم اختراق حديث لـ "ياماوكا وزاندري" نهجاً جديداً باستخدام "الأوراكل العشوائي" (random oracle)، وهو أداة نظرية تعمل مثل صندوق أسود عشوائي تماماً. لقد صمما بروتوكولاً يجب على خلاله على المُثبِت الكمي (quantum prover) إيجاد نمط محدد مخفي داخل هذا الصندوق الأسود. وأظهرا أن الحاسوب الكمي يمكنه القيام بذلك بسهولة، بينما لا يستطيع الحاسوب الكلاسيكي ذلك. ومن الأهمية بمكان أنهما اشتبها في أن أي حاسوب كمي ينجح في هذه المهمة لا بد أن يكون ينتج مخرجاً عشوائياً حقاً، بدلاً من مجرد تخمين محظوظ. ومع ذلك، فإن برهنهما على أن المخرج كان عشوائياً اعتمد على فرضية عميقة وغير مثبتة حول بنية التسارع الكمي. وإذا كانت تلك الفرضية خاطئة، فإن ضمان العشوائية سيتلاشى.
تأتي ورقة بحثية جديدة من إعداد "داكشيتا خورانا"، و"بهاسار روبرتس"، و"أفيشاي تال" لإزالة حالة عدم اليقين تلك لفئة معينة من المهاجمين. فقد أثبت المؤلفون أن بروتوكول "ياماوكا-زاندري" يضمن عشوائية قابلة للمصادقة دون الحاجة إلى أي افتراضات غير مثبتة، بشرط أن يكون المهاجم محدوداً في عدد المرات التي يمكنه فيها سؤال الصندوق الأسود عن المعلومات في تسلسل ما. وتحديداً، أظهروا أنه إذا كان المهاجم مقيداً بعدد قليل جداً من جولات الأسئلة المتتالية — تقريباً لوغاريتم معامل الأمان — فإنه لا يمكنه خداع النظام. وحتى لو كان المهاجم قوياً بشكل لا نهائي من حيث سرعة الحوسبة، فإنه لا يمكنه إجبار النظام على إخراج إجابة يمكن التنبؤ بها إذا كان مقيداً بهذا العمق الضحل من التفاعل.
حقق الباحثون ذلك من خلال تحليل كيفية تفاعل المهاجم مع الأوراكل العشوائي. فقد استحدثوا مفهوم "وزن الاستعلام" (query weight)، الذي يقيس مقدار الاهتمام الذي يوليه المهاجم لأجزاء معينة من الصندوق الأسود. وأثبتوا أنه لكي يخرج المهاجم إجابة صحي، يجب أن يكون قد ركز قدراً كبيراً من هذا الاهتمام على كل جزء تقريباً من الإجابة التي سيقدمها في النهاية. بعبارة أخرى، لا يمكنه مجرد التخمين، بل يجب أن يكون قد فحص الإجابة بدقة. ثم أثبت المؤلفون أن المهاجم الذي يمتلك فقط عدداً قلي قليلاً من جولات الأسئلة المتتالية لا يمكنه ببساطة جمع قدر كافٍ من الاهتمام على إجابة صحيحة واحدة ليجعل ذلك يحدث. إن العدد المحدود من الجولات يجبر المهاجم على تشتيت اهتمامه لدرجة تجعله عاجزاً عن تحديد حل واحد يمكن التنبؤ به.
هذه النتيجة مهمة لأنها تثبت أمن البروتوكول من المبادئ الأولى، بدلاً من الاعتماد على تخمين واسع النطاق حول كيفية عمل الحواسيب الكمية. يوضح المؤلفون أن العشوائية ليست مصادفة ناتجة عن خوارزميتهم الخاصة، بل هي سمة ضرورية للمشكلة نفسها، طالما لا يُسمح للمهاجم بطرح الكثير من الأسئلة على التوالي. وبينما ينطبق برهانهم حالياً على المهاجمين ذوي الجولات المتتالية المحدودة جداً، فإنه يوفر أساساً صلباً وغير مشروط للعشوائية القابلة للمصادقة في نموذج الأوراكل العشوائي الكمي. إنه يؤكد أنه بالنسبة لهؤلاء المهاجمين المقيدين، فإن المُثبِت الكمي يقوم حقاً برمي النرد، ويمكن للمتحقق الكلاسيكي الوثوق بالنتيجة.
ملخص تقني: العشوائية الموثقة بدون بنية ضد الخصوم ذوي الاستعلامات الضحلة
بيان المشكلة تتناول الورقة البحثية التحدي المتمثل في توليد عشوائية موثقة في نموذج الأوراكل الكمي (QROM). وبينما توفر ميكانيكا الكم احتمالية متأصلة، يجب أن يكون بمقدور الموثق الكلاسيكي أن يثق في أن المبرهن الكمي يستغل هذه العشوائية حقاً بدلاً من إخراج إجابة منحازة أو محددة مسبقاً.
اقترح بروتوكول حديث من قبل ياماكاوا وزاندري (YZ24) إثباتاً لـ "الكمية" (quantumness)، حيث يجد المبرهن رمزاً برمجياً (codeword) x من كود قابل للاسترداد بالقائمة C بحيث يكون Hi(xi)=0 لجميع الإحداثيات i، حيث H هو أوراكل عشوائي. وتتمثل الميزة الرئيسية لخوارزمية YZ الصادقة في أن مخرجاتها عشوائية بطبيعتها (عينة موحدة من الرموز البرمجية الصالحة). افترض YZ أن أي مبرهن ناجح يجب أن يعين من توزيع ذي إنتروبيا عالية، مما يحول البروتوكول إلى مصدر لعشوائية موثقة.
سابقاً، أثبت YZ هذه الفرضية فقط تحت ظل فرضية آرونسون-أمباين (AA)، وهي فرضية بنيوية تفترض أن التسريع الكمي يتطلب بنية كامنة في نطاق المدخلات. ولا تزال فرضية AA غير مثبتة بشكل عام. وتسأل الورقة: هل يمكن إثبات ضمان العشوائية الموثقة لبروتوكول YZ بشكل غير مشروط، دون الاعتماد على فرضية آرونسون-أمباين؟
المنهجية والنهج التقني تقدم المؤلفة إثباتاً أمنياً غير مشروط ضد فئة محددة من الخصوم: أولئك الذين يقومون بـ o(logλ) من جولات الاستعلام التكيفية على الأوراكل العشوائي (رغم أنه يمكنهم إجراء العديد من الاستعلامات المتوازية داخل كل جولة). تعتمد استراتيجية الإثبات على تحليل "وزن الاستعلام" وحجة عدّ تتضمن إعادة برمجة الأوراكل.
وزن الاستعلام ولمتليّة التبديل (Swapping Lemma): الأداة التحليلية المركزية هي وزن الاستعلام، المعرف بأنه الاحتمال التراكمي لأن يسجل استعلام الخصم الكمي رمزاً محدداً (i,xi) عبر طبقات الاستعلام. يستخدم المؤلفون متلية التبديل (Swapping Lemma)، التي تحدد التغير في الحالة الكمية للخصم عند إعادة برمجة الأوراكل على مجموعة من المدخلات، كدالة في إجمالي وزن الاستعلام على تلك المدخلات. إذا أعطى الخصم وزناً صغيراً لمجموعة من المدخلات، فإن إعادة برمجة تلك المدخلات لا تؤثر إلا قليلاً على توزيع مخرجات الخصم.
الخطوة 1: الخصوم ذوو الإنتروبيا المنخفضة يجب أن "يستعلموا بكثافة" عن إجابتهم: تثبت المؤلفة أنه إذا أخرج الخصم رمزاً برمجياً صحيحاً x باحتمالية عالية، فيجب عليه تخصيص وزن استعلام غير مهمل لجميع رموز x.
الحجة: إذا أخرج الخصم x باحتمالية عالية ولكنه أعطى وزناً صغيراً للعديد من رموزه، يمكن للمؤلفة بناء مجموعة من "الأوراكل السيئة" عن طريق قلب قيم الهاش لتلك الرموز ذات الوزن المنخفض من 0 إلى 1. وبناءً على متلية التبديل، يظل سلوك الخصم دون تغيير إلى حد كبير في حالات الأوراكل السيئة هذه، مما يعني أنه سيظل يخرج −x رغم أن x لم يعد حلاً صالحاً. وتظهر حجة العدّ أن عدد هذه "الأوراكل السيئة" يفوق بكثير عدد "الأوراكل الجيدة"، مما يؤدي إلى تناقض ما لم يستعلم الخصم بكثافة عن الإجابة.
الخطوة 2: الخصوم ذوو العمق المنخفض لا يمكنهم الاستعلام بكثافة عن إجابة صحيحة: المساهمة الجوهرية هي إظهار أن الخصم ذو العمق التكيفي المحدود (D=o(logλ)) لا يمكنه تركيز كافٍ من وزن الاستعلام على رمز برمحي صحيح محدد قبل تعلم ما يكفي عن الأوراكل.
حجة التمهيد (Bootstrapping Argument): على عكس حالة الاستعلام الواحد حيث تكون الأوزان ثابتة، تسمح الاستعلامات التكيفية للأوزان بأن تعتمد على استجابات الأوراكل السابقة. تقدم المؤلفة تسلسلاً من العتبات المتناميةt0<t1<⋯<tD. ويحددن طبقة حرجة q∗ حيث يجمع الخصم لأول مرة وزناً جوهرياً على (1−ζ)n من رموز الرمز البرمحي.
استراتيجية إعادة البرمجة: قبل طبقة q∗ مباشرة، لم يصل الخصم بعد إلى العتبة في ζn من الرموز على الأقل. تقوم المؤلفة بإعادة برمجة هذه الرموز ذات الوزن المنخفض. وباستخدام علاقة التكرار الخاصة بالعتبات، يثبتن أن الاضطراب الناتج عن إعادة البرمجة صغير بما يكفي بحيث يظل الخصم "يستعلم بكثافة" عن الرمز البرمحي تحت الأوراكل الجديد، رغم أن الرمز أصبح غير صالح.
العدّ: من خلال الجمع بين قابلية الاسترداد بالقائمة للكود (والتي تحد من عدد الرموز البرمجية المتسقة مع أي مجموعة من القوائم) مع عدم تقاطع مجموعات الأوراكل السيئة الناتجة عن أزواج جيدة مختلفة، يثبتن أن احتمال نجاح خصم في الاستعلام بكثافة عن رمز برمحي صحيح هو احتمال مهمل.
المساهمات والنتائج الرئيسية
الأمن غير المشروط: تثبت الورقة خاصية الإنتروبيا الدنيا الموثقة لبروتوكول ياماكاوا-زاندري بشكل غير مشروط، مما يزيل الاعتماد على فرضية آرونسون-أمباين غير المثبتة.
النظرية 1.1 (بشكل غير رسمي): يحقق البروتوكول إنتروبيا دنيا موثقة (D,h∞) لأي عمق استعلام D(λ)=o(logλ) وإنتروبيا دنيا h∞(λ)=o(λc/2). وهذا يعني أن أي خصم يقوم بـ o(logλ) من جولات الاستعلام التكيفية ويتسبب في قبول الموثق باحتمالية ملحوظة، يجب أن يكون يختار من توزيع يمتلك Ω(λc/2) بت من الإنتروبيا الدنيا.
القصور التقني: الإثبات محدود حالياً بـ o(logλ) من الجولات التكيفية. وتشير المؤلفة إلى أن تقنية التمهيد للعتبات تتطلب عتبات تنمو بشكل أسي مزدوج مع عدد الجولات؛ وما وراء O(logλ)، تتجاوز العتبات الحدود اللازمة لحجة العدّ.
الأهمية تثبت هذه الورقة أن عشوائية بروتوكول ياماكاوا-زاندري ليست مجرد نتاج لخوارزميتهم المحددة، بل هي سمة ضرورية لأي استراتيجية ناجحة ضد الخصوم ذوي الاستعلامات الضحلة. يوفر هذا أساساً أقوى للعشوائية الموثقة في نموذج QROM، بالاعتماد فقط على صعوبة مشكلة البحث الأساسية والخصائص البنيوية للأكواد القابلة للاسترداد بالقائمة، بدلاً من الاعتماد على فرضيات واسعة وغير مثبتة حول طبيعة التسريع الكمي. تعمل هذه الدراسة على تضييق الفجوة بين ما هو معروف عن تعقيد الاستعلام الكمي وأمن البروتوكولات التشفيرية العملية، وتحديداً للخصوم ذوي العمق التكيفي المحدود.