কোয়ান্টাম র্যান্ডম ওরাকল মডেলে আনক্লোনেবল নন-ইন্টারেক্টিভ জিরো নলেজ

লিঙ্কের টেবিল

বিমূর্ত এবং ভূমিকা

প্রযুক্তিগত ওভারভিউ

প্রাথমিক

CRS মডেলে আনক্লোনেবল নন-ইন্টারেক্টিভ জিরো-নলেজ

কোয়ান্টাম র‌্যামডন ওরাকল মডেলে আনক্লোনেবল NIZK

জ্ঞানের Unclonable স্বাক্ষর

তথ্যসূত্র

কোয়ান্টাম র্যান্ডম ওরাকল মডেলে 5 আনক্লোনযোগ্য NIZK

5.1 একটি পরিবর্তিত সিগমা প্রোটোকল

আমরা একটি সামান্য পরিবর্তিত সিগমা প্রোটোকল প্রবর্তন করে শুরু করব। আসন্ন বিভাগগুলিতে, আমাদের নির্মাণ এই পরিবর্তিত প্রোটোকলটিতে ফিয়াট-শামির প্রয়োগের সাথে জড়িত।

প্রমাণ। নিখুঁত সম্পূর্ণতা এটি সরাসরি Π এর নিখুঁত সম্পূর্ণতা থেকে অনুসরণ করে।

এবং সংশ্লিষ্ট λ ∈ N সন্তোষজনক সহ যেকোনো x

আমাদের আছে

আমরা Ext 3-কে Π.Ext এবং কিছু A-তে oracle-access সহ সংজ্ঞায়িত করি:

ইনপুট: x, S.

(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) এর সীমাবদ্ধতাকে সন্তুষ্ট করে। এর মানে আমাদের কাছে Ext এর সংজ্ঞার সাথে মিলিত হলে, সেটি

এইভাবে দেখানো যে আমাদের প্রোটোকল জ্ঞান প্রোটোকল একটি প্রমাণ.

কোয়ান্টাম সিমুলেটর সহ কম্পিউটেশনাল অনেস্ট-ভেরিফায়ার জিরো-নলেজ । যাক আমরা Π.Sim-এ ওরাকল অ্যাক্সেস সহ সিমকে নিম্নরূপ সংজ্ঞায়িত করি:

ইনপুট: x, S.

(1) গণনা (α, β, γ) ← Π.Sim(1λ , x)

(2) S থেকে নমুনা

(3) আউটপুট ((x, α, s), β, γ)।

একটি বহুপদী p(·), একটি বহুপদী-আকারের কোয়ান্টাম সার্কিট D, λ ∈ N, এবং ((x, S), w) ∈ R এমনভাবে দেওয়া যাক

আমরা Π-এর শূন্য-জ্ঞান সম্পত্তিতে একটি হ্রাসকে নিম্নরূপ সংজ্ঞায়িত করি:

হ্রাস: Π-এর শূন্য-জ্ঞানে ডি-তে ওরাকল অ্যাক্সেস দেওয়া হয়েছে।

এর সাথে হার্ডওয়্যারড: x, S.

(1) চ্যালেঞ্জারের কাছ থেকে (আসল বা সিমুলেটেড) (α, β, γ) গ্রহণ করুন।

(2) S থেকে নমুনা

(3) ((x, α, s), β, γ) D তে পাঠান। D থেকে b গ্রহণ করুন।

(4) আউটপুট খ.

যখন চ্যালেঞ্জার Π-এর জন্য একটি বাস্তব (বা সিমুলেটেড) প্রমাণ পাঠায়, তখন হ্রাস একটি প্রমাণ তৈরি করে যা বাস্তব (অনুকরণকৃত) প্রমাণের অনুরূপ। যেমন, এই হ্রাস D এর বিশিষ্ট সুবিধা সংরক্ষণ করে। এটি Π-এর শূন্য-জ্ঞান সম্পত্তির বিরুদ্ধে একটি দ্বন্দ্বে পৌঁছেছে। অতএব, আমাদের প্রোটোকল অবশ্যই শূন্য-জ্ঞান হতে হবে।

সৎ প্রবক্তা P.Com,

যা একটি দ্বন্দ্ব। তাই আমাদের প্রোটোকলের অবশ্যই অপ্রত্যাশিত প্রতিশ্রুতি থাকতে হবে।

ফলাফল 5.2। থিওরেম 5.1-এ সংজ্ঞায়িত পোস্ট-কোয়ান্টাম সিগমা প্রোটোকলের জন্য প্রয়োগ করা ফিয়াট-শামির হিউরিস্টিক QROM (সংজ্ঞা 3.11) এ একটি ক্লাসিক্যাল পোস্ট-কোয়ান্টাম NIZKPoK Π′ প্রদান করে।

প্রমাণ এটি উপপাদ্য 5.1 এবং উপপাদ্য 3.12 অনুসরণ করে।

5.2 Unclonability সংজ্ঞা

কোয়ান্টাম র্যান্ডম ওরাকল মডেলে আনক্লোনযোগ্য NIZKগুলি সিআরএস মডেলের সাথে সাদৃশ্যপূর্ণভাবে সংজ্ঞায়িত করা হয়েছে – আমরা নীচের সম্পূর্ণতার জন্য QRO মডেলে এই সংজ্ঞাগুলি পুনরাবৃত্তি করি।

সংজ্ঞা 5.3। (হার্ড ইনস্ট্যান্সের জন্য আনক্লোনেবল সিকিউরিটি)। একটি প্রমাণ (P,V) একটি কোয়ান্টাম র্যান্ডম ওরাকল O এর ক্ষেত্রে অক্লোনযোগ্য নিরাপত্তাকে সন্তুষ্ট করে যদি প্রতিটি ভাষার জন্য L এর সাথে সংশ্লিষ্ট সম্পর্ক RL হয়, প্রতিটি বহুপদী আকারের কোয়ান্টাম সার্কিট পরিবারের জন্য {Cλ}λ∈N, এবং প্রতিটি কঠিন বন্টনের জন্য {Xλ ,Wλ}λ∈N RL এর উপরে, একটি নগণ্য ফাংশন আছে negl1 (·) যেমন প্রতি λ ∈ N এর জন্য,

সংজ্ঞা 5.4 ((k−1)-to-k-Unclonable Extractable NIZK in QROM)। নিরাপত্তা প্যারামিটার λ ∈ N এবং NP সম্পর্ক R এর সাথে সংশ্লিষ্ট ভাষা L দেওয়া যাক। Π = (P,V) এমনভাবে দেওয়া যাক যে P এবং V হল পলি(λ)-আকারের কোয়ান্টাম অ্যালগরিদম। আমাদের কাছে আছে যে কোনো (x, ω) ∈ R, P ইনপুট এবং আউটপুট π হিসাবে একটি উদাহরণ এবং সাক্ষী জোড়া (x, ω) পায়, এবং V ইনপুট হিসাবে একটি উদাহরণ x এবং প্রমাণ π পায় এবং {0 এ একটি মান আউটপুট করে, 1}।

Π হল একটি নন-ইন্টারেক্টিভ (k − 1)-থেকে-কে-আনক্লোনেবল NIZKPoK প্রোটোকল ভাষা L এর জন্য একটি এলোমেলো ওরাকল O এর ক্ষেত্রে যদি নিম্নলিখিতগুলি থাকে:

• Π কোয়ান্টাম র্যান্ডম ওরাকল মডেলে (সংজ্ঞা 3.11) ভাষা L-এর জন্য একটি NIZKPoK প্রোটোকল।

• (k−1)-থেকে-কে-অনক্লোনেবল উইথ এক্সট্র্যাকশন: একটি ওরাকল-এডেড বহুপদী-আকারের কোয়ান্টাম সার্কিট E বিদ্যমান যাতে প্রতিটি বহুপদী-আকারের কোয়ান্টাম সার্কিট A-এর জন্য, k −1টি দৃষ্টান্ত-সাক্ষী জোড়ার প্রতি টিপলের জন্য ( x1, ω1),। . . ,(xk−1, ωk−1) ∈ R, প্রতিটি x এর জন্য যেখানে আমরা সংজ্ঞায়িত করি

যেমন একটি বহুপদী p(·) যেখানে আছে

তারপর একটি বহুপদী q (·) যেমন আছে

পূর্ববর্তী বিভাগের অনুরূপ, আমাদের নিম্নলিখিত লেমা আছে।

লেমা 5.5। Π = (সেটআপ, P,V) একটি অ-ইন্টারেক্টিভ 1-টু-2-আনক্লোনেবল জিরো-নলেজ কোয়ান্টাম প্রোটোকল (সংজ্ঞা 5.4) হতে দিন। তারপর, Π সংজ্ঞা 5.3 সন্তুষ্ট করে।

লেমা 5.5 এর প্রমাণের জন্য, আমরা পরিশিষ্ট এ উল্লেখ করি।

5.3 Unclonable NIZK QROM-এ সর্বজনীন-কী কোয়ান্টাম মানি বোঝায়

উপপাদ্য 5.6। O একটি কোয়ান্টাম র্যান্ডম ওরাকল হতে দিন। ধরুন (X ,W) একটি ভাষা L ∈ NP এর উপর একটি কঠিন বিতরণ। Π = (P,V) একটি 1-থেকে-2 আনক্লোনযোগ্য নন-ইন্টারেক্টিভ পুরোপুরি সম্পূর্ণ, কিউআরও মডেলে L-এর জন্য গণনাগতভাবে শূন্য-জ্ঞান প্রোটোকল (সংজ্ঞা 5.4) হতে দিন।

তারপর (P,V) চিত্র 4-এ বর্ণিত QRO মডেলে (সংজ্ঞা 3.15) একটি পাবলিক-কি কোয়ান্টাম মানি মিনি-স্কিম বোঝায়।

প্রমাণ নিখুঁত সঠিকতা । এটি সরাসরি Π এর নিখুঁত সম্পূর্ণতা থেকে অনুসরণ করে। অবিস্মরণীয়তা। p(·) একটি বহুপদী এবং A একটি কোয়ান্টাম বহুপদী-সময়ের প্রতিপক্ষ হতে দিন যাতে অসীম সংখ্যক λ ∈ N +,

আমরা একটি হ্রাস তৈরি করি যা অক্লোনযোগ্যতার সংজ্ঞা (সংজ্ঞা 5.3) ভেঙে দেয় যা আমরা দেখাই (পরিশিষ্ট A-তে) আমাদের সংজ্ঞা (সংজ্ঞা 5.4) দ্বারা নিহিত। চ্যালেঞ্জার, র্যান্ডম ওরাকল O-তে অ্যাক্সেস সহ, একটি হার্ড ইনস্ট্যান্স-সাক্ষী জোড়া (x, w) ← (X ,Y) এবং একটি প্রমাণ π ← PO(x, w) নমুনা করে। চ্যালেঞ্জার তারপরে (x, π) হ্রাসের দিকে এগিয়ে যায়, যার O-তে ওরাকল অ্যাক্সেসও রয়েছে। হ্রাস তারপর |$i = π এবং s = x সেট করে। হ্রাস প্রতিপক্ষ A কে (|$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(·) একটি বহুপদ। অনুরূপ ভাষা L সঙ্গে NP সম্পর্ক R দেওয়া যাক।

( NoteGen, Ver ) একটি পাবলিক-কি কোয়ান্টাম মানি মিনি-স্কিম (সংজ্ঞা 3.13) এবং Π = (P,V) একটি পোস্ট-কোয়ান্টাম সিগমা প্রোটোকল (সংজ্ঞা 3.4) হতে দিন।

(P,V) চিত্র 5-এ সংজ্ঞায়িত একটি নন-ইন্টারেক্টিভ নলেজ সাউন্ড হবে, গণনাগতভাবে শূন্য-জ্ঞান, এবং (k − 1)- থেকে-কে-অনক্লোনেবল হবে কোয়ান্টাম র্যান্ডম ওরাকল মডেলে L-এর জন্য নিষ্কাশন প্রোটোকল সহ (সংজ্ঞা 3.11) )

প্রমাণ। উপপাদ্য বিবৃতিতে দেওয়া প্যারামিটার এবং আদিম হতে দিন। আমরা যুক্তি দিয়েছি যে চিত্র 5-এ প্রোটোকল নির্মাণ থেকে সম্পূর্ণতা অনুসরণ করে এবং আমরা নীচের অবশিষ্ট বৈশিষ্ট্যগুলি প্রমাণ করি।

আমাদের আছে

বহুপদী-আকারের কোয়ান্টাম সার্কিট A এবং x এমনভাবে দেওয়া যাক

AF S-কে নিম্নরূপ কিছু A এবং O-তে ওরাকল-অ্যাক্সেস দিয়ে সংজ্ঞায়িত করা যাক:

ইনপুট: x, S.

(1) A থেকে একটি প্রশ্ন (x, α, s) দেওয়া হয়েছে: O থেকে (x, α, s) পাঠান, O থেকে β গ্রহণ করুন এবং A-তে β পাঠান।

(2) A থেকে π = (|$i, s, α, β, γ) পাওয়ার পর: আউটপুট πF S = ((x, α, s), β, γ)।

আমাদের প্রমাণের কাঠামো এবং আমাদের যাচাইকারীর সংজ্ঞা দ্বারা, এর মানে হল

যা সমীকরণের সীমাবদ্ধতাকে সন্তুষ্ট করে (16)। এর অর্থ হল আমাদের Ext এবং S এর সংজ্ঞার সাথে মিলিত হলে, যেটি

এইভাবে দেখানো যে আমাদের প্রোটোকল জ্ঞান প্রোটোকল একটি প্রমাণ.

শূন্য-জ্ঞান। করলারি 5.2-এ Π′-এর জন্য SimF S-কে সিমুলেটর হতে দিন (যেখানে Π উপপাদ্য 5.1কে নির্দেশ করে)। RF S-কে R-এর সাথে Π′-এর সম্পর্ক হতে দিন। আমরা SimF S-এ ওরাকল-অ্যাক্সেসের সাথে সিমকে সংজ্ঞায়িত করি এবং কিছু র্যান্ডম ওরাকল O-তে প্রোগ্রাম অ্যাক্সেস নিম্নরূপ:

ইনপুট: x (যে কোনো সাক্ষীকে উপেক্ষা করে যে এটি প্রাপ্ত হতে পারে)।

একটি ওরাকল-এডেড ডিস্টিংগুইশার D যা শুধুমাত্র প্রশ্ন করতে পারে (x, w) ∈ R, এবং একটি বহুপদ p(·) এমনভাবে দেওয়া উচিত

আমরা Π′-এর শূন্য-জ্ঞান সম্পত্তিতে একটি হ্রাসকে নিম্নরূপ সংজ্ঞায়িত করি:

হ্রাস: Π′-এর শূন্য-জ্ঞানে ডি-তে ওরাকল অ্যাক্সেস এবং O-তে প্রোগ্রাম অ্যাক্সেস দেওয়া হয়েছে।

D থেকে প্রতিটি (x, w) জন্য:

D-এর দৃশ্যটি চিত্র 5 বা সিমের আমাদের প্রোটোকলের সাথে মিলে যায়। যেমন, Π′ এর শূন্য-জ্ঞান সম্পত্তি ভাঙার ক্ষেত্রে আমাদের হ্রাসের একই সুবিধা থাকা উচিত। আমরা একটি দ্বন্দ্বে পৌঁছেছি, তাই আমাদের প্রোটোকল অবশ্যই শূন্য-জ্ঞান হতে হবে।

Unclonable নিষ্কাশনযোগ্যতা. Ext হল এক্সট্রাক্টরের কোয়ান্টাম সার্কিট যা আমরা আগে সংজ্ঞায়িত করেছি (আমাদের প্রমাণে যে চিত্র 5 জ্ঞানের প্রমাণ)। সিমকে সিমুলেটরের কোয়ান্টাম সার্কিট হতে দিন যা আমরা আগে সংজ্ঞায়িত করেছি (আমাদের প্রমাণে যে চিত্র 5 একটি শূন্য-জ্ঞান প্রোটোকল)। আমরা নিম্নরূপ কিছু A-তে ওরাকল-অ্যাক্সেস সহ একটি এক্সট্রাক্টর E সংজ্ঞায়িত করি:

এর সাথে হার্ডওয়্যারযুক্ত: I ⊆ [k − 1], J ⊆ [k], x1, এর কিছু পছন্দ। . . , xk−1 ∈ R, x।

(1) নমুনা ℓ ∈ J অভিন্নভাবে এলোমেলোভাবে।

(2) একটি অনুকরণযোগ্য এবং নিষ্কাশনযোগ্য র্যান্ডম ওরাকল O ইনস্ট্যান্টিয়েট করে। A এর সাথে মিথস্ক্রিয়া জুড়ে O-তে Ext চালায় (যাতে রিওয়াইন্ডিং জড়িত হতে পারে, এই ক্ষেত্রে আমরা A রিওয়াইন্ড করব এবং নিম্নলিখিত পদক্ষেপগুলি পুনরাবৃত্তি করব)। A দ্বারা ℓth প্রমাণ আউটপুট সাপেক্ষে Ext নির্যাস প্রয়োজন।

(3) গণনা করুন πι ← Sim(xι) এর জন্য ι ∈ [k − 1] যেখানে আমরা সমস্ত পয়েন্ট সঞ্চয় করি সিম একটি তালিকা P এ প্রোগ্রাম করবে।

(4) A তে {πι}ι∈[k−1] পাঠান।

(5) A থেকে প্রতিটি প্রশ্নের জন্য, যদি প্রশ্নটি P-তে থাকে, তাহলে P থেকে উত্তর দিয়ে উত্তর দিন। অন্যথায়, প্রশ্নটি O-তে ফরওয়ার্ড করুন এবং উত্তরটি A-তে ফেরত পাঠান। Ob-কে এই পরিবর্তিত র্যান্ডম ওরাকল বোঝাতে দিন।

(7) Ext এর ফলাফলকে w হিসাবে আউটপুট করে।

প্রদত্ত সমীকরণ (24), আমরা নিম্নলিখিত দুটি ক্ষেত্রের একটিতে থাকতে পারি: হয় A দুটি গ্রহণযোগ্য প্রমাণ তৈরি করে যার সততার সাথে তৈরি করা প্রমাণ হিসাবে একই ক্রমিক নম্বর রয়েছে, বা A তা করে না। আমরা এই দুটি পরিস্থিতিতে আলাদাভাবে বিবেচনা করি এবং দেখাই যে প্রতিটি একটি দ্বন্দ্বে পৌঁছেছে।

দৃশ্যকল্প এক

বলুন যে A দুটি গ্রহণযোগ্য প্রমাণ উত্পন্ন করে যার ক্রমিক নম্বর একটি সততার সাথে উত্পন্ন প্রমাণ হিসাবে একই। সমীকরণ (24) এর সাথে আবদ্ধ একটি ইউনিয়ন প্রয়োগ করে, আমরা পেয়েছি যে এই ঘটনাটি কমপক্ষে 1/2p(λ) সম্ভাব্যতার সাথে ঘটতে পারে। প্রতীকীভাবে,

দৃশ্যকল্প দুই

বিকল্পভাবে, বলুন যে A সততার সাথে উত্পন্ন প্রমাণ হিসাবে একই ক্রমিক নম্বর আছে এমন দুটি গ্রহণযোগ্য প্রমাণ তৈরি করে না। কবুতর-গর্ত নীতি দ্বারা, এর অর্থ হল A একটি ক্রমিক নম্বর সহ একটি গ্রহণযোগ্য প্রমাণ তৈরি করে যা এটি প্রাপ্তদের মধ্যে নেই। সমীকরণ (24) এর সাথে আবদ্ধ একটি ইউনিয়ন প্রয়োগ করে, আমরা পেয়েছি যে এই ঘটনাটি কমপক্ষে 1/2p(λ) সম্ভাব্যতার সাথে ঘটতে পারে। সংক্ষেপে, আমরা যে আছে

একটি গড় যুক্তির মাধ্যমে, আমরা সূচক j ∈ J ঠিক করতে পারি যা আমাদের 1/(2kp(λ)) এর সুবিধা সহ একই ঘটনা দেয়। আমরা এখন একটি হাইব্রিডে স্যুইচ করব যেখানে আমরা সূচক I এ সিমুলেটেড প্রমাণ সহ A প্রদান করি।

দাবি 5.9। এমন একটি বহুপদী q (·) বিদ্যমান

আমরা পরে দাবি 5.9 এর একটি প্রমাণ দেখতে পাব। আপাতত, এই দাবিটি ধরে রাখলে, আমরা একটি প্রতিপক্ষকে সংজ্ঞায়িত করতে পারি যেখান থেকে Ext x এর জন্য একটি বৈধ সাক্ষী বের করতে পারে।

দাবি 5.10। এমন একটি বহুপদী q ′ (·) বিদ্যমান

আমরা শীঘ্রই দাবি 5.10 এর জন্য একটি প্রমাণ দেখতে পাব। এদিকে, যদি এই দাবিটি সত্য হয়, তাহলে আমাদের সমীকরণ (19) এর সাথে সরাসরি দ্বন্দ্ব থাকবে। সুতরাং, যা প্রমাণ করা বাকি আছে তা হল দুটি দাবি: দাবি 5.9 এবং দাবি 5.10৷ আমরা প্রাক্তন দাবি প্রমাণ করে শুরু করি।

দাবির প্রমাণ 5.9. আমাদের প্রথমে যুক্তি দিতে হবে যে আমাদের কৌশলটি সু-সংজ্ঞায়িত, যে আমরা স্বাধীনভাবে এই k পয়েন্টগুলি প্রোগ্রাম করতে সক্ষম হব। তারপরে আমরা সিমুলেটেড প্রমাণগুলিতে একের পর এক স্যুইচ করার স্বতন্ত্রতা নিয়ে যুক্তি দিতে পারি। আমরা তর্ক করব যে আমাদের সিমুলেটর প্রত্যাশিত বহুপদী সময়ে চলবে। Lemma 5.7 দ্বারা, k পয়েন্টগুলি যা আমাদের সিমুলেটর প্রোগ্রাম করবে অপ্রতিরোধ্য সম্ভাবনার সাথে স্বতন্ত্র হবে। উপরন্তু, যেহেতু আমরা ধরে নিয়েছি যে আমাদের কোয়ান্টাম র্যান্ডম ওরাকল একাধিক স্বতন্ত্র বিন্দুতে প্রোগ্রাম করা যেতে পারে সংজ্ঞা 3.10, আমাদের সিমুলেটরটি ভালভাবে সংজ্ঞায়িত।

আমরা এখন একটি হাইব্রিড আর্গুমেন্টের মাধ্যমে সততার সাথে উত্পন্ন প্রমাণগুলি থেকে সিমুলেটেড প্রমাণগুলির স্বতন্ত্রতা নিয়ে তর্ক করি। দ্বন্দ্বের খাতিরে ধরুন যে সমীকরণ (21) এবং সমীকরণ (22) এর মধ্যে সম্ভাব্যতার পার্থক্য কিছু বহুপদ p′ (·) এর জন্য 1/p′ (λ) ছিল। আমরা প্রতিটি i ∈ [k − 1] এর জন্য পরপর হাইব্রিডের একটি সিরিজ তৈরি করি যেখানে আমরা i th প্রমাণটিকে প্রোভার জেনারেটেড থেকে সিমুলেটেডে পরিবর্তন করি। এই হাইব্রিড যুক্তি দ্বারা, কিছু অবস্থান ℓ ∈ [k − 1] থাকতে হবে যেখানে ℓ তম প্রমাণটি পরিবর্তন করলে কমপক্ষে 1/(kp′ (λ)) এর সম্ভাব্যতার পার্থক্য রয়েছে। আমরা এখন একটি হ্রাসকে আনুষ্ঠানিক করি যা এই দুটি সেটিংসের মধ্যে পার্থক্য করতে পারে:

আমরা প্রথমে যুক্তি দিই যে হ্রাস A কে যে দৃষ্টিভঙ্গি প্রদান করে তা একটি গেমের সাথে মেলে: যেখানে ℓ তম পর্যন্ত সমস্ত প্রমাণ সিমুলেট করা হয় বা যেখানে ℓ তম পর্যন্ত এবং সহ সমস্ত প্রমাণ সিমুলেট করা হয়৷ Lemma 5.7 দ্বারা, চ্যালেঞ্জার দ্বারা গণনা করা বা প্রোগ্রাম করা পয়েন্টগুলি হ্রাস প্রোগ্রামগুলির পয়েন্টগুলি থেকে আলাদা হবে। যেমন, হ্রাসকে 5 ওরাকল পরিবর্তন করার অনুমতি দেওয়া হয়েছে যা A এর সাথে ইন্টারফেস করে (পদক্ষেপ (4) দেখুন)। সংক্ষেপে, A কে একটি ওরাকলের অ্যাক্সেস প্রদান করা হবে যা এটি প্রাপ্ত সমস্ত প্রমাণের সাথে সামঞ্জস্যপূর্ণ।

প্রদত্ত যে A এর একটি দৃশ্য রয়েছে যা সরাসরি উভয় খেলায় তার প্রত্যাশিত দৃশ্যের সাথে মিলে যায়, তাহলে হ্রাসের সুবিধাটি A-এর সুবিধার সমান যা কমপক্ষে 1/(kp′ (λ))। এটি আমাদের প্রোটোকলের শূন্য-জ্ঞান সম্পত্তির সাথে একটি দ্বন্দ্ব। সুতরাং, আমাদের মূল দাবি সত্য হতে হবে.

এখন, আমরা শেষোক্ত দাবিটি প্রমাণ করতে চালিয়ে যাচ্ছি।

দাবির প্রমাণ 5.10। যে দাবি 5.9 ঝুলিতে দেওয়া, এটি বোঝায় যে

প্রথমে আমাদের যুক্তি দিতে হবে যে A-এর দৃষ্টিভঙ্গি সমীকরণ (24) এবং সমীকরণ (25) উভয় ক্ষেত্রেই উপস্থিত গেমের সাথে অভিন্ন। ওরাকল যেটির সাথে A ইন্টারফেস করে (ধাপ (4) দেখুন) এটি প্রাপ্ত সমস্ত প্রমাণের সাথে সামঞ্জস্যপূর্ণ হবে।

সমীকরণ (25) এর মাধ্যমে, আমরা এই উপসংহারে পৌঁছাই

জ্ঞানের প্রমাণের সংজ্ঞা (সংজ্ঞা 3.11) যার কিছু পরামিতি রয়েছে বহুপদী p ∗ (·) এবং নগণ্য ফাংশন negl0 (·) এবং negl1 (·), আমাদের আছে যে কিছু বহুপদী q ′ (·) আছে যেমন

যা আমাদের দাবির প্রমাণ সম্পূর্ণ করে।

আমাদের দাবির প্রমাণ সম্পূর্ণ করার মাধ্যমে, আমরা আমাদের উপপাদ্য বক্তব্যের প্রমাণ শেষ করেছি।

ফলাফল 5.11। ইনজেক্টিভ ওয়ান-ওয়ে ফাংশন বিদ্যমান, এবং পোস্ট-কোয়ান্টাম iO বিদ্যমান, অনুমান করে, কোয়ান্টাম র্যান্ডম ওরাকলে NP-এর জন্য নিষ্কাশন প্রোটোকল সহ একটি অ-ইন্টারেক্টিভ নলেজ সাউন্ড, গণনাগতভাবে শূন্য-জ্ঞান, এবং (k − 1)-টু-কুনক্লোনেবল রয়েছে। মডেল (সংজ্ঞা 5.4)।

প্রমাণ। এটি উপপাদ্য 3.14 এবং উপপাদ্য 5.8 থেকে অনুসরণ করে।

আমরা এইভাবে দেখিয়েছি যে চিত্র 5 হল রম মডেলের একটি আনক্লোনযোগ্য NIZK PoK যা আমাদের আনক্লোনবিলিটি সংজ্ঞা, সংজ্ঞা 5.4 অনুযায়ী সংজ্ঞায়িত করা হয়েছে।