2025-11-14T17:16:11.719199

Quantum One-Time Protection of any Randomized Algorithm

Gunn, Movassagh
The meteoric rise in power and popularity of machine learning models dependent on valuable training data has reignited a basic tension between the power of running a program locally and the risk of exposing details of that program to the user. At the same time, fundamental properties of quantum states offer new solutions to data and program security that can require strikingly few quantum resources to exploit, and offer advantages outside of mere computational run time. In this work, we demonstrate such a solution with quantum one-time tokens. A quantum one-time token is a quantum state that permits a certain program to be evaluated exactly once. One-time security guarantees, roughly, that the token cannot be used to evaluate the program more than once. We propose a scheme for building quantum one-time tokens for any randomized classical program, which include generative AI models. We prove that the scheme satisfies an interesting definition of one-time security as long as outputs of the classical algorithm have high enough min-entropy, in a black box model. Importantly, the classical program being protected does not need to be implemented coherently on a quantum computer. In fact, the size and complexity of the quantum one-time token is independent of the program being protected, and additional quantum resources serve only to increase the security of the protocol. Due to this flexibility in adjusting the security, we believe that our proposal is parsimonious enough to serve as a promising candidate for a near-term useful demonstration of quantum computing in either the NISQ or early fault tolerant regime.
academic

الحماية الكمية لمرة واحدة لأي خوارزمية عشوائية

المعلومات الأساسية

  • معرّف الورقة البحثية: 2411.03305
  • العنوان: Quantum One-Time Protection of any Randomized Algorithm
  • المؤلفون: Sam Gunn, Ramis Movassagh (Google Quantum AI)
  • التصنيف: quant-ph cs.CR
  • تاريخ النشر: 3 يناير 2025 (arXiv v2)
  • رابط الورقة: https://arxiv.org/abs/2411.03305v2

الملخص

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

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

الخلفية البحثية والدافع

تعريف المشكلة

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

  1. مخططات إخفاء البرامج: توزيع نسخة مخفاة من البرنامج، لكن توجد مخاطر القرصنة ويمكن للمستخدمين تشغيله عدداً غير محدود من المرات
  2. مخططات استعلام الخادم: الاحتفاظ بالبرنامج على الخادم للرد على استعلامات المستخدمين، لكن هذا يقلل من القابلية للاستخدام ويتطلب اتصالاً مستمراً

أهمية المشكلة

تصبح هذه المشكلة أكثر حدة في عصر الذكاء الاصطناعي التوليدي، لأن:

  • قد يكون البرنامج ذا قيمة عالية جداً
  • قد يكشف معلومات خاصة
  • تصبح نماذج الدفع حسب الاستعلام أكثر انتشاراً

قيود الطرق الموجودة

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

مزايا الحل الكمي

توفر عدم قابلية النسخ للمعلومات الكمية إمكانية تحسين الحلول الموجودة:

  • الحماية الكمية من النسخ: تحسين المخطط (1)، منع نسخ البرنامج مع السماح بتشغيل غير محدود
  • البرامج الكمية لمرة واحدة: تحسين المخطط (2)، إزالة متطلبات الاتصال عبر الإنترنت في نماذج الدفع حسب الاستعلام

المساهمات الأساسية

  1. أول مخطط عام لترميز البرامج الكمية: تقديم أول مخطط عام يستخدم المعلومات الكمية لحماية أي خوارزمية عشوائية، غير مقتصر على وظائف تشفيرية محددة
  2. متطلبات الموارد الكمية المستقلة عن تعقيد البرنامج: حجم وتعقيد الرمز الكمي مستقل تماماً عن البرنامج المحمي
  3. إثبات الأمان النظري: إثبات أن المخطط يرضي تعريف الأمان لمرة واحدة في النموذج الأسود
  4. الاعتبارات العملية: المخطط بسيط بما يكفي ليكون قابلاً للتنفيذ في عصر NISQ أو الحوسبة الكمية المتسامحة مع الأخطاء المبكرة

شرح الطريقة

تعريف المهمة

بناء رموز كمية لمرة واحدة لحماية أي خوارزمية عشوائية f: X × R → Y، بحيث:

  • يسمح الرمز بتقييم البرنامج بالضبط مرة واحدة
  • يوفر ضمان أمان لمرة واحدة
  • لا يتطلب تنفيذ البرنامج بشكل متماسك على جهاز كمي

البناء الأساسي (البناء 2)

البدائيات التشفيرية

يعتمد المخطط على ثلاثة بدائيات تشفيرية:

  1. (AuthKeyGen, AuthTokenGen, Sign, Verify): مخطط المصادقة الكمية لمرة واحدة
  2. Obf: محرك إخفاء البرامج الكلاسيكية
  3. H: دالة التجزئة (نموذج كدالة عشوائية)

هيكل الرمز

يتكون رمز البرنامج من جزأين:

  • |ψ⟩: حالة كمية غير قابلة للنسخ لا تعتمد على f
  • Obf(P): دائرة كلاسيكية مخفاة تعتمد على f

تدفق الخوارزمية

KeyGen(1^λ, f):

  1. أخذ عينة sk ← AuthKeyGen(1^λ)
  2. تعريف الدائرة الكلاسيكية P: X × {0,1}^m → Y ∪ {⊥}
    • حساب Verify(sk, (x,z))، إذا رفضت فأخرج ⊥
    • وإلا أخرج f(x; H(x,z))
  3. حساب الإخفاء P̂ = Obf(P)
  4. أخرج (sk, P̂)

TokenGen(sk):

  1. حساب رمز المصادقة الكمية لمرة واحدة |tk⟩ ← AuthTokenGen(sk)
  2. أخرج |tk⟩

TokenEval(x, |tk⟩, P̂):

  1. حساب z ← Sign(x, |tk⟩)
  2. حساب وأخرج P̂(x,z)

مخطط المصادقة الكمية لمرة واحدة

التعريف (التعريف 1)

يجب أن يرضي مخطط المصادقة الكمية لمرة واحدة:

  • الصحة: يمكن للتوقيعات الشرعية أن تمر التحقق
  • عدم القابلية للتزييف لمرة واحدة: لا يمكن لأي خصم متعدد الحدود إنشاء زوجي توقيع صحيح مختلفين

البناء المحدد (البناء 1)

بناء على حالات الفضاء الفرعي المخفي للمصادقة أحادية البت:

AuthKeyGen(1^λ): أخذ عينة من فضاء فرعي عشوائي A ⊆ F₂^λ، بحجم λ/2

AuthTokenGen(A): أخرج |A⟩ = 2^(-λ/4) ∑_{a∈A} |a⟩

Sign(x, |A⟩):

  • إذا كان x = 0: قياس في الأساس المعياري وأخرج النتيجة
  • إذا كان x = 1: قياس في أساس Hadamard وأخرج النتيجة

Verify(A, (x,z)): تحقق ما إذا كان z في الفضاء الفرعي المناسب

نقاط الابتكار التقنية

  1. موارد كمية مستقلة عن البرنامج: الحالة الكمية |ψ⟩ لا تعتمد على البرنامج المحمي، مما يسمح بحماية البرامج المعقدة بأجهزة كمية صغيرة
  2. آلية ربط العشوائية: من خلال H(x,z) تحديد العشوائية، "خلط" الإدخال والمصادقة والإخراج بشكل فعال
  3. خصائص دالة التجزئة المنهارة: الاستفادة من خاصية أن قياس الإخراج يسبب انهيار الإدخال وعلامة المصادقة

التحليل النظري

تعريفات الأمان

لعبة البرنامج الأسود لمرة واحدة G^BB-OTP

  1. يحصل الخصم على |ψ⟩ والوصول إلى أوراكل كمي لـ P̂
  2. يقدم الخصم استعلامات كمية، ويحسب المتحدي P̂ ويقيس النتيجة y
  3. إذا كان y = ⊥ تتوقف اللعبة ويفشل الخصم
  4. يقدم الخصم استعلاماً ثانياً، ويقيس المتحدي ليحصل على y'
  5. إذا كان y' ∉ {y, ⊥} يفوز الخصم

النظرية الرئيسية

النظرية 2: إذا كان لكل x ∈ X، الحد الأدنى من الإنتروبيا لـ f(x;r) بالنسبة للعشوائي r على الأقل poly(λ)، وكان مخطط المصادقة الكمية لمرة واحدة آمناً، فإن البناء 2 آمن أسود لمرة واحدة لـ f.

جوهر الإثبات: دالة التجزئة المنهارة

اللمة 1: لتكن f: {0,1}^m × {0,1}^n → Y، إذا كان لجميع x، الحد الأدنى من الإنتروبيا لـ f(x;r) بالنسبة للعشوائي r على الأقل τ، فعندما تكون H دالة عشوائية، الدالة g^H: x ↦ f(x;H(x)) منهارة، بميزة O(q³·2^(-τ)).

فكرة الإثبات

استخدام تقنية أوراكل الضغط:

  1. إثبات أن Invert_f و CPhsO يمكن تبديلهما تقريباً
  2. استخدام شرط الحد الأدنى من الإنتروبيا لتحديد احتمالية التصادم
  3. تحقيق انهيار الإدخال من خلال قياس الإخراج

التجارب والتطبيقات

متطلبات الموارد الكمية

  • إذا استخدمنا مخطط التوقيع لمرة واحدة من CLLZ21، يحتاج المستخدم فقط إلى:
    • تخزين حالة كمية بحجم ثابت
    • إجراء قياسات في الأساس المعياري وأساس Hadamard

الاعتبارات العملية

  1. الجدوى القريبة الأجل: متطلبات القدرة الكمية مستقلة عن تعقيد البرنامج
  2. قابلية الأمان للتوسع: الموارد الكمية الإضافية تُستخدم فقط لزيادة الأمان
  3. بديل الاتصال الكلاسيكي: يمكن استبدال الاتصال الكمي بالاتصال الكلاسيكي من خلال بروتوكولات إعداد الحالة عن بعد

حالات الاستخدام المناسبة

  • حماية نماذج الذكاء الاصطناعي التوليدي
  • خدمات البرامج المدفوعة حسب الاستعلام
  • البرامج الحساسة التي تتطلب تنفيذاً غير متصل

الأعمال ذات الصلة

التطور التاريخي

  • GKR08: البحث الأولي عن البرامج لمرة واحدة (بدون حوسبة كمية)
  • BGS13: تقديم مفهوم البرامج الكمية لمرة واحدة، إثبات استحالة البرامج الحتمية
  • BS23: حماية وظائف التوقيع في النموذج المعياري
  • GLR+24: عمل مستقل متوازي، توفير تعريفات أمان أقوى

مقارنة مساهمات هذه الورقة

  • أول مخطط عام لحماية أي خوارزمية عشوائية
  • إثبات أمان بسيط وذاتي الاحتواء
  • اعتبارات التصميم الموجهة نحو الاستخدام العملي

الخلاصة والمناقشة

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

  1. يمكن للرموز الكمية لمرة واحدة حماية أي برنامج كلاسيكي عشوائي
  2. يعتمد الأمان على الحد الأدنى العالي من الإنتروبيا لمخرجات البرنامج
  3. متطلبات الموارد الكمية مستقلة عن تعقيد البرنامج
  4. المخطط له جدوى تنفيذية في عصر NISQ

القيود

  1. متطلبات الإنتروبيا العالية: يجب أن يكون لمخرجات البرنامج إنتروبيا دنيا عالية بما يكفي
  2. النموذج الأسود: يتم إثبات الأمان في نموذج أسود مثالي
  3. قيود البرامج الحتمية: غير قابل للتطبيق على البرامج الحتمية (محدود بنتائج الاستحالة من BGS13)
  4. بروتوكولات اتصال كلاسيكية معقدة: على الرغم من أنه يمكن نظرياً استبدال الاتصال الكمي بالاتصال الكلاسيكي، فإن البروتوكولات معقدة للغاية

الاتجاهات المستقبلية

  1. تحليل الأمان في النموذج المعياري
  2. تقليل متطلبات إنتروبيا مخرجات البرنامج
  3. التنفيذ والاختبار على أجهزة كمية فعلية
  4. تحليل العلاقة مع عمل GLR+24

التقييم المتعمق

المزايا

  1. الابتكار النظري: أول مخطط عام كمي لحماية أي خوارزمية عشوائية
  2. التصميم العملي: فصل متطلبات الموارد الكمية عن تعقيد البرنامج، مما يعزز الجدوى العملية
  3. إثبات صارم: توفير إثبات أمان بسيط بناءً على دوال التجزئة المنهارة
  4. آفاق التطبيق: ينطبق مباشرة على احتياجات حماية نماذج الذكاء الاصطناعي الحالية الشهيرة

أوجه القصور

  1. الافتراضات المثالية: الاعتماد على النموذج الأسود ونموذج الأوراكل العشوائي
  2. قيود شرط الإنتروبيا: قد تحد متطلبات الحد الأدنى العالي من الإنتروبيا من نطاق التطبيقات العملية
  3. تعقيد التنفيذ: على الرغم من الأناقة النظرية، لا تزال التنفيذ الفعلي تواجه تحديات هندسية
  4. تعريف الأمان: يعترف المؤلفون بأن هذا ليس التعريف النهائي للأمان لمرة واحدة

القيمة التأثيرية

  1. القيمة الأكاديمية: توفير إطار نظري جديد لمشكلة حماية البرامج في التشفير الكمي
  2. الإمكانات العملية: توفير حل كمي محتمل لحماية نماذج الذكاء الاصطناعي القيمة
  3. التقدم التكنولوجي: تعزيز تطور التشفير غير القابل للنسخ
  4. الدلالة الملهمة: توفير أفكار جديدة للتطبيقات العملية القريبة الأجل للحوسبة الكمية

حالات الاستخدام المناسبة

  • موفرو خدمات الذكاء الاصطناعي الذين يحتاجون إلى حماية الملكية الفكرية
  • نماذج الترخيص البرمجي المدفوعة حسب الاستخدام
  • حماية الخوارزميات الحساسة ذات متطلبات الأمان العالية جداً
  • مرشحات تطبيقات إثبات الميزة الكمية

المراجع

تستشهد هذه الورقة بأعمال مهمة في التشفير الكمي وعدم قابلية النسخ والتشفير وتعقيد الحوسبة الكمية، خاصة:

  • Aar09 العمل الرائد لـ Aaronson حول حماية النسخ الكمي
  • BS23 عمل Ben-David و Sattath حول التوقيعات الرقمية الكمية
  • CLLZ21 البناء المتعلق بالمجموعات المخفية والتشفير غير القابل للنسخ
  • Zha19 تقنية أوراكل الضغط لـ Zhandry

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