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

किसी भी यादृच्छिकृत एल्गोरिदम की क्वांटम वन-टाइम सुरक्षा

बुनियादी जानकारी

  • पेपर ID: 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

सारांश

मशीन लर्निंग मॉडल के तीव्र विकास और मूल्यवान प्रशिक्षण डेटा पर निर्भरता ने स्थानीय रूप से प्रोग्राम चलाने की सुविधा और उपयोगकर्ताओं को प्रोग्राम विवरण उजागर करने के जोखिम के बीच मौलिक विरोधाभास को पुनः जागृत किया है। साथ ही, क्वांटम अवस्था की मौलिक विशेषताएं डेटा और प्रोग्राम सुरक्षा के लिए नए समाधान प्रदान करती हैं, जिन्हें न्यूनतम क्वांटम संसाधनों की आवश्यकता होती है और ये कम्प्यूटेशनल रनटाइम से परे लाभ प्रदान करते हैं। यह कार्य क्वांटम वन-टाइम टोकन के माध्यम से ऐसे समाधान का प्रदर्शन करता है।

क्वांटम वन-टाइम टोकन एक क्वांटम अवस्था है जो किसी विशेष प्रोग्राम को बिल्कुल एक बार मूल्यांकित किए जाने की अनुमति देती है। वन-टाइम सुरक्षा यह गारंटी देती है कि टोकन का उपयोग प्रोग्राम को कई बार मूल्यांकित करने के लिए नहीं किया जा सकता। लेखकों ने किसी भी यादृच्छिकृत शास्त्रीय प्रोग्राम (जिसमें जनरेटिव AI मॉडल शामिल हैं) के लिए क्वांटम वन-टाइम टोकन बनाने की एक योजना प्रस्तावित की है, और ब्लैक-बॉक्स मॉडल में यह साबित किया है कि यह योजना एक दिलचस्प वन-टाइम सुरक्षा परिभाषा को संतुष्ट करती है, बशर्ते कि शास्त्रीय एल्गोरिदम का आउटपुट पर्याप्त रूप से उच्च न्यूनतम एन्ट्रॉपी रखता हो।

अनुसंधान पृष्ठभूमि और प्रेरणा

समस्या परिभाषा

सॉफ्टवेयर व्यावसायीकरण एक मूल दुविधा का सामना करता है: स्वामित्व को त्यागे बिना सॉफ्टवेयर कैसे वितरित करें? पारंपरिक समाधान में अंतर्निहित उपयोगिता और एक्सक्लूसिविटी के बीच व्यापार-बंद हैं:

  1. प्रोग्राम ऑब्फ्यूस्केशन योजना: सॉफ्टवेयर के ऑब्फ्यूस्केटेड संस्करण को वितरित करें, लेकिन पायरेसी जोखिम मौजूद है और उपयोगकर्ता असीमित बार चला सकते हैं
  2. सर्वर क्वेरी योजना: सॉफ्टवेयर को सर्वर पर रखें और उपयोगकर्ता क्वेरी का जवाब दें, लेकिन यह उपयोगिता को कम करता है और निरंतर संचार की आवश्यकता होती है

समस्या की महत्ता

जनरेटिव AI के युग में, यह समस्या अधिक गंभीर हो गई है क्योंकि:

  • सॉफ्टवेयर अत्यंत मूल्यवान हो सकता है
  • यह निजी जानकारी लीक कर सकता है
  • प्रति-क्वेरी भुगतान मॉडल तेजी से सामान्य हो रहे हैं

मौजूदा विधियों की सीमाएं

शास्त्रीय जानकारी हमेशा कॉपी की जा सकती है, एक बार सॉफ्टवेयर वितरित हो जाने के बाद, उपयोगकर्ता इसे मनमाने ढंग से कई बार क्वेरी या कॉपी कर सकते हैं। यह सीमा पारंपरिक योजनाओं को उच्च उपयोगिता और मजबूत एक्सक्लूसिविटी दोनों को एक साथ प्राप्त करने में असमर्थ बनाती है।

क्वांटम समाधान के लाभ

क्वांटम जानकारी की अ-क्लोनिंग संपत्ति मौजूदा समाधानों में सुधार की संभावना प्रदान करती है:

  • क्वांटम कॉपी सुरक्षा: योजना (1) में सुधार, प्रोग्राम को कॉपी होने से रोकें लेकिन असीमित बार चलाने की अनुमति दें
  • क्वांटम वन-टाइम प्रोग्राम: योजना (2) में सुधार, प्रति-क्वेरी भुगतान मॉडल में ऑनलाइन संचार की आवश्यकता को समाप्त करें

मुख्य योगदान

  1. पहली सामान्य क्वांटम टोकनकरण प्रोग्राम योजना: क्वांटम जानकारी का उपयोग करके किसी भी यादृच्छिकृत एल्गोरिदम की सुरक्षा के लिए पहली सामान्य योजना प्रस्तावित की गई है, जो विशिष्ट क्रिप्टोग्राफिक कार्यों तक सीमित नहीं है
  2. प्रोग्राम जटिलता से स्वतंत्र क्वांटम संसाधन आवश्यकता: क्वांटम टोकन का आकार और जटिलता पूरी तरह से संरक्षित प्रोग्राम से स्वतंत्र है
  3. सैद्धांतिक सुरक्षा प्रमाण: ब्लैक-बॉक्स मॉडल में साबित किया गया है कि योजना वन-टाइम सुरक्षा परिभाषा को संतुष्ट करती है
  4. व्यावहारिक विचार: योजना काफी सरल है, NISQ या प्रारंभिक दोष-सहिष्णु क्वांटम कंप्यूटिंग युग में कार्यान्वयन की आशा है

विधि विवरण

कार्य परिभाषा

किसी भी यादृच्छिकृत एल्गोरिदम f: X × R → Y की सुरक्षा के लिए क्वांटम वन-टाइम टोकन बनाएं, जैसे कि:

  • टोकन प्रोग्राम को बिल्कुल एक बार मूल्यांकित किए जाने की अनुमति देता है
  • वन-टाइम सुरक्षा गारंटी प्रदान करता है
  • प्रोग्राम को क्वांटम कंप्यूटर पर सुसंगत कार्यान्वयन की आवश्यकता नहीं है

मुख्य निर्माण (Construction 2)

क्रिप्टोग्राफिक आदिम

योजना तीन क्रिप्टोग्राफिक आदिमों पर निर्भर करती है:

  1. (AuthKeyGen, AuthTokenGen, Sign, Verify): क्वांटम वन-टाइम प्रमाणीकरण योजना
  2. Obf: शास्त्रीय प्रोग्राम ऑब्फ्यूस्केटर
  3. H: हैश फंक्शन (यादृच्छिक ओरेकल के रूप में मॉडल किया गया)

टोकन संरचना

प्रोग्राम टोकन में दो भाग होते हैं:

  • |ψ⟩: f पर निर्भर नहीं करने वाली अ-क्लोनिंग क्वांटम अवस्था
  • Obf(P): f पर निर्भर करने वाली ऑब्फ्यूस्केटेड शास्त्रीय सर्किट P

एल्गोरिदम प्रवाह

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) की गणना करें और आउटपुट करें

क्वांटम वन-टाइम प्रमाणीकरण योजना

परिभाषा (Definition 1)

क्वांटम वन-टाइम प्रमाणीकरण योजना को संतुष्ट करना चाहिए:

  • सही होना: वैध हस्ताक्षर सत्यापन से गुजर सकते हैं
  • वन-टाइम अजेयता: कोई भी बहुपद समय विरोधी दो अलग-अलग वैध हस्ताक्षर जोड़े उत्पन्न नहीं कर सकता

विशिष्ट निर्माण (Construction 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(λ) है, और क्वांटम वन-टाइम प्रमाणीकरण योजना सुरक्षित है, तो Construction 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. शास्त्रीय संचार प्रतिस्थापन: दूरस्थ अवस्था तैयारी प्रोटोकॉल के माध्यम से क्वांटम संचार को शास्त्रीय संचार से बदला जा सकता है

लागू परिदृश्य

  • जनरेटिव AI मॉडल सुरक्षा
  • प्रति-क्वेरी भुगतान सॉफ्टवेयर सेवाएं
  • संवेदनशील प्रोग्राम जिन्हें ऑफलाइन निष्पादन की आवश्यकता है

संबंधित कार्य

ऐतिहासिक विकास

  • 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. अनुप्रयोग संभावना: वर्तमान लोकप्रिय जनरेटिव AI सुरक्षा आवश्यकताओं पर सीधे लागू होता है

कमियां

  1. आदर्शीकृत धारणाएं: ब्लैक-बॉक्स मॉडल और यादृच्छिक ओरेकल मॉडल पर निर्भर करता है
  2. एन्ट्रॉपी स्थिति सीमा: उच्च न्यूनतम एन्ट्रॉपी आवश्यकता व्यावहारिक अनुप्रयोग सीमा को सीमित कर सकती है
  3. कार्यान्वयन जटिलता: हालांकि सैद्धांतिक रूप से सुरुचिपूर्ण, व्यावहारिक कार्यान्वयन अभी भी इंजीनियरिंग चुनौतियों का सामना करता है
  4. सुरक्षा परिभाषा: लेखक स्वीकार करते हैं कि यह वन-टाइम सुरक्षा की अंतिम परिभाषा नहीं है

प्रभाव

  1. शैक्षणिक मूल्य: क्वांटम क्रिप्टोग्राफी में प्रोग्राम सुरक्षा समस्या के लिए नया सैद्धांतिक ढांचा प्रदान करता है
  2. व्यावहारिक संभावना: मूल्यवान AI मॉडल की सुरक्षा के लिए संभावित क्वांटम समाधान प्रदान करता है
  3. तकनीकी प्रगति: अ-क्लोनिंग क्रिप्टोग्राफी के विकास को आगे बढ़ाता है
  4. प्रेरणा महत्व: क्वांटम कंप्यूटिंग के निकट-अवधि के व्यावहारिक अनुप्रयोग के लिए नई सोच प्रदान करता है

लागू परिदृश्य

  • बौद्धिक संपत्ति सुरक्षा की आवश्यकता वाली AI सेवा प्रदाता
  • उपयोग-आधारित सॉफ्टवेयर लाइसेंसिंग मॉडल
  • संवेदनशील एल्गोरिदम सुरक्षा के लिए अत्यधिक सुरक्षा आवश्यकता
  • क्वांटम लाभ प्रदर्शन के लिए उम्मीदवार अनुप्रयोग

संदर्भ

यह पेपर क्वांटम क्रिप्टोग्राफी, अ-क्लोनिंग क्रिप्टोग्राफी और क्वांटम कंप्यूटिंग जटिलता सिद्धांत के महत्वपूर्ण कार्यों का हवाला देता है, विशेष रूप से:

  • Aar09 Aaronson का क्वांटम कॉपी सुरक्षा पर अग्रणी कार्य
  • BS23 Ben-David और Sattath का क्वांटम डिजिटल हस्ताक्षर पर कार्य
  • CLLZ21 छिपी हुई कोसेट और अ-क्लोनिंग क्रिप्टोग्राफी पर निर्माण
  • Zha19 Zhandry का संपीड़न ओरेकल तकनीक पर कार्य

यह पेपर सैद्धांतिक क्वांटम क्रिप्टोग्राफी के क्षेत्र में महत्वपूर्ण योगदान देता है, सॉफ्टवेयर वितरण में उपयोगिता और सुरक्षा के विरोधाभास को संतुलित करने के लिए एक सुरुचिपूर्ण समाधान प्रदान करता है। हालांकि व्यावहारिकता की चुनौतियां अभी भी मौजूद हैं, लेकिन यह क्रिप्टोग्राफी अनुप्रयोगों में क्वांटम कंप्यूटिंग के निकट-अवधि के कार्यान्वयन के लिए एक आशाजनक दिशा प्रदान करता है।