क्वांटम रैंडम ओरेकल मॉडल में अनक्लोनेबल नॉन-इंटरएक्टिव जीरो नॉलेज

लिंक की तालिका

सार एवं परिचय

तकनीकी सिंहावलोकन

प्रारंभिक

सीआरएस मॉडल में अनक्लोनेबल नॉन-इंटरएक्टिव जीरो-नॉलेज

क्वांटम रैमडन ओरेकल मॉडल में अनक्लोनेबल NIZK

ज्ञान के अप्राप्य हस्ताक्षर

संदर्भ

क्वांटम रैंडम ओरेकल मॉडल में 5 अनक्लोनेबल NIZK

5.1 एक संशोधित सिग्मा प्रोटोकॉल

हम थोड़ा संशोधित सिग्मा प्रोटोकॉल पेश करके शुरुआत करेंगे। आने वाले अनुभागों में, हमारे निर्माण में इस संशोधित प्रोटोकॉल में फिएट-शमीर को लागू करना शामिल होगा।

सबूत। पूर्ण पूर्णता यह सीधे Π की पूर्ण पूर्णता से उत्पन्न होता है।

और संबद्ध λ ∈ N वाला कोई भी x संतोषजनक है

हमारे पास है

हम Ext 3 को Π.Ext और कुछ A तक ओरेकल-एक्सेस के साथ इस प्रकार परिभाषित करते हैं:

इनपुट: एक्स, एस.

(1) AΠ से (x, α, s) दिया गया है: α को Π.Ext पर भेजें, Π.Ext से β प्राप्त करें, और β को AΠ पर भेजें।

(2) AΠ से γ प्राप्त करने पर: γ को Π.Ext पर भेजें।

(3) Π.Ext के परिणाम को w के रूप में आउटपुट करें।

हम मापदंडों के निम्नलिखित सेट को परिभाषित करते हैं: c = cΠ, p(·) = pΠ(·), negl0 (·) = negl0,Π(·) और negl1 (·) = negl1,Π(·).

मान लीजिए बहुपद-आकार का क्वांटम सर्किट A = (A 0, A 1) और (x, S) इस प्रकार दिया गया है कि

अब हम AΠ = (A0,Π, A1,Π) को A तक ओरेकल-एक्सेस के साथ परिभाषित करते हैं। A0,Π S के साथ हार्डवायर्ड है, इनपुट x लेता है, A0 को (x, S) भेजता है, ((x, α, s) प्राप्त करता है ), |sti) A0 से, और आउटपुट (α, |sti)। A1,Π को S के साथ हार्डवायर किया गया है, इनपुट (x, |sti, β) लेता है, A1 को ((x, S), |sti, β) भेजता है, A1 से γ प्राप्त करता है, आउटपुट γ देता है। हमारे प्रमाण की संरचना और हमारे सत्यापनकर्ता की परिभाषा से, इसका मतलब यह है

जो समीकरण (15) में बाधा को संतुष्ट करता है। इसका मतलब यह है कि जब इसे एक्सट की हमारी परिभाषा के साथ जोड़ा जाता है, तो यह हमारे पास होता है

इस प्रकार यह दर्शाता है कि हमारा प्रोटोकॉल ज्ञान प्रोटोकॉल का प्रमाण है।

क्वांटम सिम्युलेटर के साथ कम्प्यूटेशनल ईमानदार-सत्यापनकर्ता शून्य-ज्ञान । मान लीजिए Π.Sim Π के लिए कम्प्यूटेशनल ईमानदार-सत्यापनकर्ता शून्य-ज्ञान क्वांटम सिम्युलेटर है। हम सिम को Π.Sim तक ओरेकल एक्सेस के साथ इस प्रकार परिभाषित करते हैं:

इनपुट: एक्स, एस.

(1) गणना करें (α, β, γ) ← Π.Sim(1λ , x)

(2) एस से नमूना।

(3) आउटपुट ((x, α, s), β, γ)।

मान लीजिए कि एक बहुपद p(·), एक बहुपद-आकार का क्वांटम सर्किट D, λ ∈ N, और ((x, S), w) ∈ R इस प्रकार दिया गया है कि

हम Π के शून्य-ज्ञान गुण में कमी को इस प्रकार परिभाषित करते हैं:

कमी: Π के शून्य-ज्ञान को डी तक ओरेकल पहुंच दी गई।

हार्डवायर्ड के साथ: एक्स, एस।

(1) चुनौती देने वाले से (वास्तविक या नकली) (α, β, γ) प्राप्त करें।

(2) एस से नमूना।

(3) D को ((x, α, s), β, γ) भेजें। D से b प्राप्त करें।

(4) आउटपुट बी.

जब चुनौती देने वाला Π के लिए एक वास्तविक (या सिम्युलेटेड) प्रमाण भेजता है, तो कमी एक ऐसा प्रमाण उत्पन्न करती है जो वास्तविक (सम्मान अनुरूपित) प्रमाण के समान होता है। इस प्रकार, यह कमी डी के विशिष्ट लाभ को बरकरार रखती है। यह Π के शून्य-ज्ञान गुण के विरुद्ध विरोधाभास तक पहुँचता है। इसलिए, हमारा प्रोटोकॉल शून्य-ज्ञान होना चाहिए।

ईमानदार नीतिज्ञ P.Com,

जो एक विरोधाभास है. इसलिए हमारे प्रोटोकॉल में अप्रत्याशित प्रतिबद्धताएँ होनी चाहिए।

परिणाम 5.2. प्रमेय 5.1 में परिभाषित पोस्ट-क्वांटम सिग्मा प्रोटोकॉल पर लागू फिएट-शमीर अनुमान QROM (परिभाषा 3.11) में एक शास्त्रीय पोस्ट-क्वांटम NIZKPoK Π′ उत्पन्न करता है।

सबूत । यह प्रमेय 5.1 और प्रमेय 3.12 का अनुसरण करता है।

5.2 अनक्लोनेबिलिटी परिभाषाएँ

क्वांटम रैंडम ऑरेकल मॉडल में अनक्लोनेबल NIZK को CRS मॉडल के अनुरूप परिभाषित किया गया है - हम नीचे पूर्णता के लिए QRO मॉडल में इन परिभाषाओं को दोहराते हैं।

परिभाषा 5.3. (कठिन उदाहरणों के लिए अप्राप्य सुरक्षा)। एक प्रमाण (पी,वी) एक क्वांटम यादृच्छिक ओरेकल ओ के संबंध में अप्राप्य सुरक्षा को संतुष्ट करता है यदि प्रत्येक भाषा एल के लिए संबंधित संबंध आरएल के साथ, प्रत्येक बहुपद आकार के क्वांटम सर्किट परिवार के लिए {सीλ}λ∈N, और प्रत्येक कठिन वितरण के लिए {एक्सλ ,Wλ}λ∈N ओवर आरएल, एक नगण्य फलन negl1 (·) मौजूद है जैसे कि प्रत्येक λ ∈ N के लिए,

परिभाषा 5.4 ((k−1)-to-k-अनक्लोनेबल एक्सट्रैक्टेबल NIZK in QROM)। सुरक्षा पैरामीटर λ ∈ N और संबंधित भाषा L के साथ NP संबंध R दिया गया है। मान लीजिए Π = (P,V) इस प्रकार दिया गया है कि P और V पॉली(λ)-आकार के क्वांटम एल्गोरिदम हैं। हमारे पास यह है कि किसी भी (x, ω) ∈ R के लिए, P को इनपुट के रूप में एक उदाहरण और गवाह जोड़ी (x, ω) प्राप्त होता है और आउटपुट π मिलता है, और V को इनपुट के रूप में एक उदाहरण x और प्रमाण π प्राप्त होता है और {0 में एक मान आउटपुट होता है। 1}.

Π एक यादृच्छिक ओरेकल O के संबंध में भाषा L के लिए एक गैर-इंटरैक्टिव (k - 1)-टू-k-अनक्लोनेबल NIZKPoK प्रोटोकॉल है, यदि निम्नलिखित मान्य हो:

• Π क्वांटम रैंडम ऑरेकल मॉडल (परिभाषा 3.11) में भाषा एल के लिए एक NIZKPoK प्रोटोकॉल है।

• (k−1)-to-k-एक्सट्रैक्शन के साथ अनक्लोनेबल: एक ओरेकल-सहायता प्राप्त बहुपद-आकार क्वांटम सर्किट E मौजूद है, जैसे कि प्रत्येक बहुपद-आकार क्वांटम सर्किट A के लिए, k के प्रत्येक टुपल के लिए - 1 उदाहरण-साक्षी जोड़े ( x1, ω1), . . . ,(xk−1, ωk−1) ∈ R, प्रत्येक x के लिए जहां हम परिभाषित करते हैं

जैसे कि एक बहुपद p(·) है जहाँ

तो फिर एक बहुपद q (·) भी है जैसे

पिछले अनुभाग के समान, हमारे पास निम्नलिखित प्रमेयिका है।

लेम्मा 5.5. मान लीजिए Π = (सेटअप, पी,वी) एक गैर-इंटरएक्टिव 1-टू-2-अनक्लोनेबल शून्य-ज्ञान क्वांटम प्रोटोकॉल है (परिभाषा 5.4)। फिर, Π परिभाषा 5.3 को संतुष्ट करता है।

लेम्मा 5.5 के प्रमाण के लिए, हम परिशिष्ट ए का संदर्भ लेते हैं।

5.3 अनक्लोनेबल NIZK का तात्पर्य QROM में सार्वजनिक-कुंजी क्वांटम मनी से है

प्रमेय 5.6. मान लीजिए O एक क्वांटम यादृच्छिक दैवज्ञ है। मान लीजिए (X ,W) एक भाषा L ∈ NP पर एक कठिन वितरण है। मान लीजिए Π = (पी,वी) क्यूआरओ मॉडल (परिभाषा 5.4) में एल के लिए 1-टू-2 अनक्लोनेबल गैर-इंटरैक्टिव पूरी तरह से पूर्ण, कम्प्यूटेशनल रूप से शून्य-ज्ञान प्रोटोकॉल है।

फिर (पी,वी) का तात्पर्य क्यूआरओ मॉडल (परिभाषा 3.15) में एक सार्वजनिक-कुंजी क्वांटम मनी मिनी-स्कीम से है जैसा चित्र 4 में वर्णित है।

सबूत । बिल्कुल सही . यह सीधे Π की पूर्ण पूर्णता से अनुसरण करता है। अक्षम्यता. मान लीजिए p(·) एक बहुपद है और A एक क्वांटम बहुपद-समय विरोधी है, जैसे कि λ ∈ N + की अनंत संख्या के लिए,

हम एक कमी का निर्माण करते हैं जो अनक्लोनेबिलिटी परिभाषा (परिभाषा 5.3) को तोड़ती है जिसे हम दिखाते हैं (परिशिष्ट ए में) हमारी परिभाषा (परिभाषा 5.4) में निहित है। चुनौती देने वाला, यादृच्छिक ओरेकल ओ तक पहुंच के साथ, एक कठिन उदाहरण-साक्षी जोड़ी (एक्स, डब्ल्यू) ← (एक्स, वाई) और एक प्रमाण π ← पीओ (एक्स, डब्ल्यू) का नमूना लेता है। फिर चुनौती देने वाला कटौती के लिए (x, π) को आगे बढ़ाता है, जिसके पास O तक ओरेकल पहुंच भी होती है। फिर कटौती सेट हो जाती है |$i = π और s = x। कमी प्रतिद्वंद्वी ए को (|$i, s) भेजती है जो वापस लौटता है (|$0, s0, |$1, s1)। फिर कटौती पार्स करती है और i ∈ {0, 1} के लिए πi = |$ii सेट करती है। फिर कमी π0 और π1 को चुनौती देने वाले को वापस भेजती है।

5.4 निर्माण एवं विश्लेषण

लेम्मा 5.7. मान लीजिए λ, k ∈ N और एक सार्वजनिक-कुंजी क्वांटम मनी मिनी-स्कीम ( NoteGen,Ver ) दिया गया है। मान लीजिए अंक q1, . . . , qk को निम्नलिखित संरचना के साथ दिया जाना चाहिए: एक बिंदु q में NoteGen (1λ) के अनुसार नमूना किया गया एक क्रमांक s होता है।

अंक q1, . . . , qk अत्यधिक संभावना के साथ अलग होना चाहिए।

सबूत । प्रत्येक बिंदु में क्वांटम मनी जेनरेशन एल्गोरिदम, NoteGen (1λ) के अनुसार नमूना किया गया एक सीरियल नंबर होता है। क्वांटम मनी (परिभाषा 3.13) की क्रम संख्या की अप्रत्याशितता के कारण, सभी k ईमानदारी से उत्पन्न क्रम संख्या अत्यधिक संभावना के साथ अलग होनी चाहिए। इसलिए, ये k बिंदु अत्यधिक संभावना के साथ भिन्न होंगे।

अब हम चित्र 5 में अपना निर्माण प्रस्तुत करते हैं और इस खंड के मुख्य प्रमेय को सिद्ध करते हैं।

प्रमेय 5.8. मान लीजिए k(·) एक बहुपद है। मान लीजिए कि एनपी का संबंधित भाषा एल के साथ संबंध आर दिया गया है।

मान लीजिए ( NoteGen, Ver ) एक सार्वजनिक-कुंजी क्वांटम मनी मिनी-स्कीम (परिभाषा 3.13) है और Π = (पी,वी) एक पोस्ट-क्वांटम सिग्मा प्रोटोकॉल (परिभाषा 3.4) है।

(पी,वी) जैसा कि चित्र 5 में परिभाषित किया गया है, एक गैर-संवादात्मक ज्ञान ध्वनि होगी, कम्प्यूटेशनल रूप से शून्य-ज्ञान, और (के - 1) -क्वांटम रैंडम ऑरेकल मॉडल में एल के लिए निष्कर्षण प्रोटोकॉल के साथ-टू-के-अनक्लोनेबल (परिभाषा 3.11) ).

सबूत। मान लीजिए कि पैरामीटर और प्रिमिटिव प्रमेय कथन में दिए गए हैं। हमारा तर्क है कि पूर्णता चित्र 5 में प्रोटोकॉल निर्माण से होती है, और हम नीचे शेष गुणों को साबित करते हैं।

हमारे पास है

मान लीजिए कि बहुपद-आकार वाले क्वांटम सर्किट A और x को इस प्रकार दिया गया है

मान लीजिए कि एएफ एस को कुछ ए और ओ तक ओरेकल-एक्सेस के साथ परिभाषित किया गया है:

इनपुट: एक्स, एस.

(1) A से एक प्रश्न (x, α, s) दिया गया है: O को (x, α, s) भेजें, O से β प्राप्त करें, और A को β भेजें।

(2) ए से π = (|$i, s, α, β, γ) प्राप्त करने पर: आउटपुट πF S = ((x, α, s), β, γ)।

हमारे प्रमाण की संरचना और हमारे सत्यापनकर्ता की परिभाषा से, इसका मतलब यह है

जो समीकरण (16) में बाधा को संतुष्ट करता है। इसका मतलब यह है कि जब इसे एक्सट और एस की हमारी परिभाषा के साथ जोड़ा जाता है, तो यह हमारे पास होता है

इस प्रकार यह दर्शाता है कि हमारा प्रोटोकॉल ज्ञान प्रोटोकॉल का प्रमाण है।

शून्य-ज्ञान. मान लीजिए कि SimF S, परिणाम 5.2 में Π′ के लिए सिम्युलेटर है (जहाँ Π प्रमेय 5.1 को त्वरित करता है)। मान लीजिए RF S, R के संबंध में Π′ का संबंध है। हम सिम को सिमएफ एस तक ओरेकल-एक्सेस और कुछ यादृच्छिक ओरेकल ओ तक प्रोग्राम एक्सेस के साथ परिभाषित करते हैं:

इनपुट: x (इसे प्राप्त होने वाले किसी भी गवाह को अनदेखा करता है)।

मान लीजिए कि एक दैवज्ञ-सहायता प्राप्त विभेदक D जो केवल प्रश्न (x, w) ∈ R बना सकता है, और एक बहुपद p(·) इस प्रकार दिया गया है कि

हम Π′ के शून्य-ज्ञान गुण में कमी को इस प्रकार परिभाषित करते हैं:

कमी: Π′ के शून्य-ज्ञान को डी तक ओरेकल एक्सेस और ओ तक प्रोग्राम एक्सेस दिया गया।

D से प्रत्येक (x, w) के लिए:

डी का दृश्य चित्र 5 या सिम में हमारे प्रोटोकॉल से मेल खाता है। इस प्रकार, हमारी कमी का Π′ के शून्य-ज्ञान गुण को तोड़ने में समान लाभ होना चाहिए। हम एक विरोधाभास पर पहुंच गए हैं, इसलिए हमारा प्रोटोकॉल शून्य-ज्ञान होना चाहिए।

अप्राप्य निष्कर्षण क्षमता। मान लीजिए कि Ext एक्सट्रैक्टर का क्वांटम सर्किट है जिसे हमने पहले परिभाषित किया था (हमारे प्रमाण में कि चित्र 5 ज्ञान का प्रमाण है)। मान लीजिए कि सिम सिम्युलेटर का क्वांटम सर्किट है जिसे हमने पहले परिभाषित किया था (हमारे प्रमाण में कि चित्र 5 एक शून्य-ज्ञान प्रोटोकॉल है)। हम कुछ ए तक ओरेकल-एक्सेस के साथ एक एक्सट्रैक्टर ई को इस प्रकार परिभाषित करते हैं:

इसके साथ हार्डवेयर्ड: I ⊆ [k - 1], J ⊆ [k], x1, के कुछ विकल्प। . . , xk−1 ∈ R, x.

(1) नमूने ℓ ∈ जे समान रूप से यादृच्छिक रूप से।

(2) एक अनुकरणीय और निकालने योग्य यादृच्छिक ओरेकल ओ को इंस्टेंट करता है। ए के साथ बातचीत के दौरान ओ पर एक्सट चलाता है (जिसमें रिवाइंडिंग शामिल हो सकती है, इस स्थिति में हम ए को रिवाइंड करेंगे और निम्नलिखित चरणों को दोहराएंगे)। आवश्यकता है कि ए द्वारा ℓवें प्रूफ आउटपुट के संबंध में एक्सट्रेक्ट निकाला जाए।

(3) ι ∈ [k - 1] के लिए πι ← Sim(xι) की गणना करें, जहां हम सभी बिंदुओं को संग्रहीत करते हैं, सिम एक सूची पी में प्रोग्राम करेगा।

(4) ए को {πι}ι∈[k−1] भेजें।

(5) ए से प्रत्येक प्रश्न के लिए, यदि प्रश्न पी में है, तो पी से उत्तर के साथ उत्तर दें। अन्यथा, प्रश्न को ओ को अग्रेषित करें और उत्तर ए को वापस भेजें। मान लें कि ओब इस संशोधित यादृच्छिक दैवज्ञ को दर्शाता है।

(7) एक्सट के परिणाम को डब्ल्यू के रूप में आउटपुट करता है।

समीकरण (24) को देखते हुए, हम निम्नलिखित दो मामलों में से एक में हो सकते हैं: या तो ए दो स्वीकार्य प्रमाण उत्पन्न करता है जिनकी क्रम संख्या ईमानदारी से उत्पन्न प्रमाण के समान होती है, या ए नहीं। हम इन दोनों परिदृश्यों पर अलग-अलग विचार करते हैं और दिखाते हैं कि प्रत्येक एक विरोधाभास पर पहुंचता है।

परिदृश्य एक

कहें कि ए दो स्वीकार्य प्रमाण उत्पन्न करता है जिनकी क्रम संख्या ईमानदारी से उत्पन्न प्रमाण के समान होती है। समीकरण (24) से बंधे संघ को लागू करने से, हमें पता चलता है कि यह घटना कम से कम 1/2p(λ) संभावना के साथ घटित हो सकती है। प्रतीकात्मक रूप से,

परिदृश्य दो

वैकल्पिक रूप से, कहें कि ए दो स्वीकार्य प्रमाण उत्पन्न नहीं करता है जिनकी क्रम संख्या ईमानदारी से उत्पन्न प्रमाण के समान होती है। कबूतर-छेद सिद्धांत के अनुसार, इसका मतलब यह है कि ए एक सीरियल नंबर के साथ एक स्वीकार्य प्रमाण उत्पन्न करता है जो उसे प्राप्त हुए लोगों में से नहीं है। समीकरण (24) से बंधे संघ को लागू करने से, हमें पता चलता है कि यह घटना कम से कम 1/2p(λ) संभावना के साथ घटित हो सकती है। संक्षेप में, हमारे पास वह है

एक औसत तर्क के माध्यम से, हम सूचकांक j ∈ J को ठीक कर सकते हैं जो हमें 1/(2kp(λ)) के लाभ के साथ वही घटना देता है। अब हम एक हाइब्रिड पर स्विच करेंगे जहां हम सूचकांक I पर ए को सिम्युलेटेड प्रमाण प्रदान करते हैं।

दावा 5.9. ऐसा एक बहुपद q (·) मौजूद है

हम बाद में दावे 5.9 का प्रमाण देखेंगे। अभी के लिए, यह मानते हुए कि यह दावा सही है, हम एक ऐसे प्रतिद्वंद्वी को परिभाषित कर सकते हैं जिससे Ext x के लिए एक वैध गवाह निकाल सकता है।

दावा 5.10. एक बहुपद q ′ (·) ऐसा मौजूद है

हम जल्द ही दावे 5.10 का प्रमाण देखेंगे। इस बीच, यदि यह दावा सच है, तो हमारा समीकरण (19) से सीधा विरोधाभास होगा। इस प्रकार, केवल दो दावे साबित होने बाकी हैं: दावा 5.9 और दावा 5.10। हम पहले वाले दावे को साबित करके शुरुआत करते हैं।

दावे का प्रमाण 5.9. हमें सबसे पहले यह तर्क देने की आवश्यकता है कि हमारी रणनीति अच्छी तरह से परिभाषित है, कि हम इन k बिंदुओं को स्वतंत्र रूप से प्रोग्राम करने में सक्षम होंगे। फिर हम एक-एक करके नकली प्रमाणों पर स्विच करने की अप्रभेद्यता पर बहस कर सकते हैं। हम तर्क देंगे कि हमारा सिम्युलेटर अपेक्षित बहुपद समय में चलेगा। लेम्मा 5.7 के अनुसार, हमारा सिम्युलेटर जिन k बिंदुओं को प्रोग्राम करेगा, वे अत्यधिक संभावना के साथ अलग होंगे। इसके अलावा, चूंकि हमने मान लिया है कि हमारे क्वांटम रैंडम ऑरेकल को परिभाषा 3.10 के कई अलग-अलग बिंदुओं पर प्रोग्राम किया जा सकता है, हमारा सिम्युलेटर अच्छी तरह से परिभाषित है।

अब हम हाइब्रिड तर्क के माध्यम से ईमानदारी से तैयार किए गए सबूतों से नकली सबूतों की अप्रभेद्यता पर बहस करते हैं। विरोधाभास के लिए मान लीजिए कि समीकरण (21) और समीकरण (22) के बीच संभाव्यता अंतर कुछ बहुपद पी '(·) के लिए 1/पी' (λ) था। हम प्रत्येक i ∈ [k - 1] के लिए लगातार संकरों की एक श्रृंखला का निर्माण करते हैं, जहां हम i वें प्रमाण को उत्पन्न प्रोवर से सिम्युलेटेड में बदलते हैं। इस हाइब्रिड तर्क के अनुसार, कुछ स्थिति होनी चाहिए ℓ ∈ [k − 1] जहां ℓवें प्रमाण को स्विच करने पर कम से कम 1/(kp′ (λ)) का संभाव्यता अंतर होता है। अब हम एक कमी को औपचारिक रूप देते हैं जो इन दो सेटिंग्स के बीच अंतर कर सकती है:

हम पहले तर्क देते हैं कि ए को जो कमी प्रदान की गई है वह दृश्य खेलों में से एक से मेल खाता है: जहां ℓ वें तक के सभी प्रमाण सिम्युलेटेड हैं या जहां ℓ वें तक और इसमें शामिल सभी प्रमाण सिम्युलेटेड हैं। लेम्मा 5.7 के अनुसार, चुनौती देने वाले द्वारा गणना या प्रोग्राम किया गया बिंदु उन बिंदुओं से अलग होगा जो कटौती कार्यक्रम करते हैं। इस प्रकार, कमी को 5 ओरेकल को संशोधित करने की अनुमति है जिसके साथ ए इंटरफ़ेस करता है (चरण (4) देखें)। संक्षेप में, ए को उस दैवज्ञ तक पहुंच प्रदान की जाएगी जो उसे प्राप्त होने वाले सभी प्रमाणों के अनुरूप है।

यह देखते हुए कि ए के पास एक दृश्य है जो किसी भी गेम में उसके अपेक्षित दृश्य से सीधे मेल खाता है, तो कमी का लाभ ए के लाभ के समान है जो कम से कम 1/(kp′ (λ)) है। यह हमारे प्रोटोकॉल की शून्य-ज्ञान संपत्ति के साथ एक विरोधाभास है। इस प्रकार, हमारा मूल दावा सत्य होना चाहिए।

अब, हम बाद वाले दावे को साबित करना जारी रखते हैं।

दावे का प्रमाण 5.10. यह देखते हुए कि दावा 5.9 सही है, इसका तात्पर्य यह है

पहले हमें यह तर्क देना चाहिए कि ए का दृष्टिकोण खेल के समान है जो समीकरण (24) और समीकरण (25) दोनों में दिखाई देता है। दैवज्ञ जिसके साथ ए इंटरफेस करता है (चरण (4) देखें) उसे प्राप्त होने वाले सभी प्रमाणों के अनुरूप होगा।

समीकरण (25) के माध्यम से हम इस निष्कर्ष पर पहुंचते हैं कि

ज्ञान के प्रमाण की परिभाषा से (परिभाषा 3.11) जिसमें कुछ पैरामीटर बहुपद p * (·) और नगण्य फलन negl0 (·) और negl1 (·) हैं, हमारे पास है कि कुछ बहुपद q '(·) मौजूद हैं जैसे कि

जो हमारे दावे का प्रमाण पूरा करता है।

अपने दावों के प्रमाणों को पूरा करके, हमने अपने प्रमेय कथन के प्रमाण का निष्कर्ष निकाला है।

परिणाम 5.11. यह मानते हुए कि इंजेक्टिव वन-वे फ़ंक्शंस मौजूद हैं, और पोस्ट-क्वांटम iO मौजूद है, एक गैर-संवादात्मक ज्ञान ध्वनि, कम्प्यूटेशनल रूप से शून्य-ज्ञान मौजूद है, और (k - 1) - क्वांटम रैंडम ऑरेकल में एनपी के लिए निष्कर्षण प्रोटोकॉल के साथ-टू-कुनक्लोनेबल। मॉडल (परिभाषा 5.4).

सबूत। यह प्रमेय 3.14 और प्रमेय 5.8 से अनुसरण करता है।

इस प्रकार हमने दिखाया है कि चित्र 5 ROM मॉडल में एक अनक्लोनेबल NIZK PoK है जैसा कि हमारी अनक्लोनेबिलिटी परिभाषा, परिभाषा 5.4 के अनुसार परिभाषित किया गया है।