এই পর্বে যা শিখবেন
- NP-র verifier থেকে interactive proof-এ যাওয়া, আর class IP-র নিখুঁত সংজ্ঞা
- Graph non-isomorphism-এর protocol, তার completeness আর soundness-এর প্রমাণ, আর private coin-এর ভূমিকা
- Arthur–Merlin (public coin) protocol, AM আর MA, আর graph isomorphism নিয়ে তার তাৎপর্য
- Arithmetization, sum-check protocol, IP ⊆ PSPACE-এর প্রমাণ আর IP = PSPACE-এর ধারণা
- Zero knowledge-এর simulator-সংজ্ঞা, graph isomorphism-এর zero-knowledge protocol আর তার বাস্তব প্রয়োগ
১ · প্রমাণ যখন কথোপকথন — verifier থেকে interaction
পর্ব ৫৮-এ NP-কে দেখেছেন একটি একমুখী প্রমাণের ছবিতে: prover একটি certificate লিখে দেয়, verifier polynomial সময়ে তা মিলিয়ে দেখে। Verifier কোনো প্রশ্ন করে না, মুদ্রাও ছোড়ে না। এই পর্বের প্রশ্ন: verifier যদি প্রশ্ন করতে পারে আর এলোমেলো প্রশ্ন বাছতে পারে, তাহলে কোন দাবিগুলোর প্রমাণ দেওয়া যায়?
বাজারঘরের চা-পাতার সরবরাহকারী দাবি করেন, তাঁর “প্রিমিয়াম” আর “সাধারণ” প্যাকেট আলাদা; তিনি চুমুক দিয়েই বলে দিতে পারেন কোনটি। প্যাকেট দেখতে হুবহু এক। ক্রয়-কর্মকর্তা কী করবেন? তিনি পর্দার আড়ালে মুদ্রা ছুড়ে একটি প্যাকেট বেছে চা বানান, আর জিজ্ঞাসা করেন: “এটি কোনটি?” পাতা সত্যিই আলাদা হলে সরবরাহকারী প্রতিবার ঠিক বলবেন। পাতা আসলে এক হলে তিনি শুধু আন্দাজ করতে পারেন, ঠিক হওয়ার সম্ভাবনা ১/২. দশ কাপে দশবারই ঠিক হলে আন্দাজে তা ঘটার সম্ভাবনা 2−10, হাজারে একের কম। লক্ষ করুন, “আলাদা”-র কোনো লিখিত প্রমাণ নেই, তবু কর্মকর্তা প্রায় নিশ্চিত হলেন। কৌশলটি হলো: মুদ্রা গোপন, আর প্রশ্ন করা হয় একাধিকবার।
এখানে দুটি উপাদান একসঙ্গে কাজ করছে, আর আলাদাভাবে কোনোটিই যথেষ্ট নয়। Verifier deterministic হলে interaction কোনো লাভ দেয় না: verifier-এর প্রতিটি প্রশ্ন আগে থেকেই নির্ধারিত, তাই prover পুরো কথোপকথন আগেই লিখে একটি certificate হিসেবে দিতে পারে, আর শ্রেণিটি NP-ই থাকে (অনুশীলন ২-এ এর প্রমাণ)। আবার শুধু এলোমেলোতা থাকলে, prover ছাড়া, পাওয়া যায় BPP (পর্ব ৬৯)। দুটি মিলে যে শ্রেণি পাওয়া যায়, তা অনেক বড়: পুরো PSPACE.
২ · Interactive proof system আর class IP
একটি interactive proof system-এ দুই পক্ষ থাকে। Prover P-এর গণনার কোনো সীমা নেই; সে যেকোনো function হতে পারে। Verifier V একটি probabilistic Turing machine, যার নিজের এলোমেলো bit আছে আর যে input w-এর দৈর্ঘ্যের polynomial সময়ে চলে। দুজনেই w দেখে, তারপর পালাক্রমে বার্তা পাঠায়; প্রতিটি বার্তার দৈর্ঘ্য আর মোট বার্তার সংখ্যা |w|-এর polynomial. শেষে V একাই accept বা reject বলে। (V ↔ P)(w) দিয়ে বোঝানো হয় এই কথোপকথনের ফল, যা V-এর মুদ্রার ওপর নির্ভর করে একটি এলোমেলো চলক।
Language A ∈ IP, যদি এমন একটি polynomial সময়ের probabilistic verifier V থাকে, যাতে প্রতিটি w-এর জন্য:
Completeness: w ∈ A হলে এমন একটি prover P আছে, যার সঙ্গে Pr[(V ↔ P)(w) accepts] ≥ 2/3.
Soundness: w ∉ A হলে প্রতিটি prover P̃-এর জন্য Pr[(V ↔ P̃)(w) accepts] ≤ 1/3.
দুই শর্তের অসমতা লক্ষ করার মতো। Completeness-এ “একটি সৎ prover আছে”, soundness-এ “কোনো prover-ই পারে না”, এমনকি যে prover সব জানে আর verifier-এর প্রতিটি দুর্বলতা খোঁজে, সেও না। Sound হওয়ার দায় সম্পূর্ণ verifier-এর। Prover-এর ক্ষমতা অসীম ধরা হয় যাতে soundness-এর নিশ্চয়তা সবচেয়ে শক্ত হয়; বাস্তবের cryptography-তে prover-কেও polynomial সময়ে সীমিত করা হয়, তখন তাকে বলা হয় argument (অংশ ৭)।
কয়েকটি সহজ ফল সংজ্ঞা থেকেই আসে:
- NP ⊆ IP. Prover একটি বার্তায় certificate পাঠায়, V পর্ব ৫৮-এর verifier চালায়। এখানে ভুল শূন্য: completeness 1, soundness 0.
- BPP ⊆ IP. V prover-কে উপেক্ষা করে নিজেই BPP-র algorithm চালায়।
- ধ্রুবক বদলানো যায়. Protocol-টি k বার পরপর চালিয়ে সংখ্যাগরিষ্ঠ ভোট নিলে ভুল exponential হারে কমে, পর্ব ৬৯-এর amplification-এর মতো। প্রতিটি পুনরাবৃত্তিতে V নতুন মুদ্রা ছোড়ে, আর প্রতারক prover আগের round-এর তথ্য ব্যবহার করলেও প্রতিটি round-এ তার সাফল্যের সীমা একই থাকে, তাই পর্ব ৬৯-এর হিসাব এখানেও খাটে।
সাধারণ ভুল: soundness-কে “সৎ prover মিথ্যা বলে না” পড়া। সৎ prover-এর কথা soundness-এ নেই; শর্তটি হলো, মিথ্যা দাবিতে যেকোনো কৌশলের prover-কে V বড়জোর ১/৩ সম্ভাবনায় মেনে নেয়। আরেকটি ভুল: V-এর মুদ্রা prover দেখতে পায় ধরে নেওয়া। সংজ্ঞায় V-এর মুদ্রা তার নিজের কাছে থাকে; যা পাঠায় শুধু সেটুকুই prover দেখে। এই “গোপন মুদ্রা”-র গুরুত্ব পরের অংশে স্পষ্ট হবে।
৩ · Graph non-isomorphism — certificate নেই, protocol আছে
দুটি graph G0 আর G1 isomorphic, যদি vertex-গুলোর এমন একটি নাম-বদল (permutation) π থাকে, যাতে π(G0) = G1: শুধু নাম আলাদা, গঠন এক (ডিসক্রিট ম্যাথমেটিক্স কোর্সের পর্ব ৫৮)। Graph isomorphism (GI) NP-তে, কারণ π নিজেই certificate. তার complement GNI = {⟨G0, G1⟩ : G0 আর G1 isomorphic নয়} coNP-তে, কিন্তু NP-তে আছে বলে জানা নেই: “কোনো π কাজ করে না”-র একটি ছোট, দ্রুত-যাচাইযোগ্য প্রমাণ কেউ জানে না। Degree-এর তালিকার মতো সহজ বৈশিষ্ট্য সবসময় কাজ করে না: নিচের উদাহরণে দুটি graph-এরই প্রতিটি vertex-এর degree 2.
Input: n-vertex graph G0, G1. নিচের round k বার চলে, প্রতিবার নতুন মুদ্রায়:
- V গোপনে একটি bit b ∈ {0, 1} আর {1, …, n}-এর একটি এলোমেলো permutation π বেছে H = π(Gb) পাঠায়।
- P একটি bit b′ ফেরত পাঠায়।
- b′ ≠ b হলে V সঙ্গে সঙ্গে reject করে।
সব round পেরোলে V accept করে।
GNI protocol-এর একটি round
Verifier-এর মুদ্রা b তার কাছেই থাকে; prover দেখে শুধু H.
নিচের stepper একটি round চালায়: G0 = ৬টি vertex-এর একটি চক্র (C6), G1 = দুটি আলাদা ত্রিভুজ। দুটিতেই প্রতিটি vertex-এর degree 2, কিন্তু একটিতে ত্রিভুজ আছে, অন্যটিতে নেই, তাই এরা isomorphic নয়।
1V: গোপনে মুদ্রা b2V: এলোমেলো π, H ← π(G_b)3V → P: শুধু H4P: H কার মতো? → b′5V: b′ = b হলে পাস
| b | |
| H-এর edge | |
| P |
- প্রস্তুতি. C6-এর edge 01 12 23 34 45 50; দুই ত্রিভুজের edge 01 12 20 আর 34 45 53. প্রতিটি vertex-এর degree দুটিতেই 2, তাই degree গুনে এদের আলাদা করা যায় না।
- গোপন মুদ্রা. V মুদ্রা ছুড়ে b = 1 পেল, অর্থাৎ দুই ত্রিভুজের graph. এই bit কখনো পাঠানো হবে না।
- নাম বদলে পাঠানো. π = (2, 5, 0, 3, 1, 4), মানে 0 → 2, 1 → 5, 2 → 0, এভাবে। H = π(G1)-এর edge 02 05 25 13 14 34. Prover শুধু এই edge-তালিকা দেখে।
- Prover-এর কাজ. H-এ 0, 2, 5 একটি ত্রিভুজ। C6-এর কোনো নাম-বদলে ত্রিভুজ আসতে পারে না, তাই H অবশ্যই G1-এর copy: b′ = 1. বড় graph-এ এই কাজ কঠিন হতে পারে, কিন্তু prover-এর ক্ষমতা সীমাহীন।
- মেলানো. b′ = b = 1, তাই round পাস। V এই হিসাব polynomial সময়ে করে: শুধু দুটি bit তুলনা।
- কেন কাজ করে. Graph দুটি আলাদা বলে H ঠিক একটির সঙ্গে isomorphic; সৎ prover তাই কখনো ভুল করে না। Graph দুটি একই হলে H দেখে b বোঝার উপায় থাকত না, যা উপপাদ্য ৩.২-এর মূল কথা।
Protocol ৩.১ k round-এ completeness 1 আর soundness error 2−k দেয়। তাই GNI ∈ IP.
প্রমাণ।
- Completeness: G0 ≇ G1 হলে H = π(Gb) শুধু Gb-এর isomorphic, অন্যটির নয় (isomorphism একটি equivalence relation). সৎ prover সব permutation পরীক্ষা করে b বের করে, তাই প্রতিটি round পাস: সম্ভাবনা 1. — prover-এর ক্ষমতা সীমাহীন
- একটি round-এর soundness: ধরুন G0 ≅ G1. তাহলে দুটির isomorphic copy-র সেট একই, ধরুন 𝒞. এলোমেলো π নিলে π(G0) 𝒞-এর ওপর সুষমভাবে ছড়ানো (প্রতিটি copy একই সংখ্যক π থেকে আসে, সংখ্যাটি G0-এর automorphism-এর সংখ্যা), আর π(G1)-ও একই 𝒞-এর ওপর সুষম। তাই H-এর বণ্টন b-এর ওপর নির্ভর করে না: H আর b স্বাধীন। — সুষম বণ্টন
- Prover-এর উত্তর b′ শুধু H-এর (আর তার নিজের মুদ্রার) function, তাই b′ আর b-ও স্বাধীন, আর b সুষম। ফলে যেকোনো কৌশলে Pr[b′ = b] = 1/2. — স্বাধীনতা
- k round: প্রতিটি round-এ V নতুন b আর π নেয়। আগের round-এর কথোপকথন জানলেও নতুন b সম্পর্কে কিছু জানা যায় না, তাই প্রতিটি round পেরোনোর শর্তসাপেক্ষ সম্ভাবনা 1/2, আর সব k round পেরোনোর সম্ভাবনা 2−k. k = 2 নিলেই ≤ 1/3. ∎
ধাপ ২-এর সংখ্যাটি এবং “যেকোনো কৌশল” দাবিটি পরীক্ষা করা যাক। নিচের ব্লক C6 আর দুই ত্রিভুজের জোড়ায় সৎ prover চালায়; তারপর C6 আর তারই নাম-বদলানো copy-র জোড়ায় (মিথ্যা দাবি) তিনটি প্রতারক কৌশল চালায়, যার একটি চালাক দেখতে: H-এর কতগুলো edge হুবহু G0 বা G1-এর সঙ্গে মেলে, সেটা গোনে।
# Graph non-isomorphism protocol: the verifier hides a coin b, the prover must name it.
import random
from itertools import permutations
rng = random.Random(74)
PERMS = list(permutations(range(6)))
def graph(edges): return frozenset(frozenset(e) for e in edges)
def relabel(G, p): return frozenset(frozenset(p[v] for v in e) for e in G)
C6 = graph([(0, 1), (1, 2), (2, 3), (3, 4), (4, 5), (5, 0)]) # one 6-cycle
TRI2 = graph([(0, 1), (1, 2), (2, 0), (3, 4), (4, 5), (5, 3)]) # two triangles
C6b = relabel(C6, (3, 0, 4, 1, 5, 2)) # C6, new names
def run(G0, G1, prover, rounds): # accept only if every round succeeds
for _ in range(rounds):
b = rng.randrange(2) # private coin, never sent
H = relabel((G0, G1)[b], rng.choice(PERMS))
if prover(G0, G1, H) != b: return False
return True
def honest(G0, G1, H): # all-powerful: knows the class of G0
return 0 if H in CLASS0 else 1
def always0(G0, G1, H): return 0
def coin(G0, G1, H): return rng.randrange(2)
def overlap(G0, G1, H): return 0 if len(H & G0) >= len(H & G1) else 1
T = 4000
CLASS0 = {relabel(C6, p) for p in PERMS}
print("copies of C6:", len(CLASS0), "| every vertex has degree 2 in both graphs")
ok = sum(run(C6, TRI2, honest, 1) for _ in range(T))
print(f"C6 vs two triangles (different): honest prover right {ok}/{T}")
print("C6 vs renamed C6 (same graph): cheating strategies, 1 round")
for name, P in (("always 0", always0), ("coin flip", coin), ("overlap", overlap)):
ok = sum(run(C6, C6b, P, 1) for _ in range(T))
print(f" {name:9}: accepted {ok/T:.3f}")
print("k rounds, overlap strategy: measured 2^-k")
for k in (1, 2, 3, 5, 8):
ok = sum(run(C6, C6b, overlap, k) for _ in range(T))
print(f" k = {k}: {ok/T:.4f} {2**-k:.4f}")আসল আউটপুট (ব্রাউজারের Python):
copies of C6: 60 | every vertex has degree 2 in both graphs
C6 vs two triangles (different): honest prover right 4000/4000
C6 vs renamed C6 (same graph): cheating strategies, 1 round
always 0 : accepted 0.497
coin flip: accepted 0.484
overlap : accepted 0.488
k rounds, overlap strategy: measured 2^-k
k = 1: 0.5135 0.5000
k = 2: 0.2507 0.2500
k = 3: 0.1165 0.1250
k = 5: 0.0297 0.0312
k = 8: 0.0037 0.0039
C6-এর আলাদা copy ৬০টি: ৭২০টি permutation, আর C6-এর ১২টি automorphism (৬টি ঘোরানো × ২টি উল্টানো), তাই 720/12 = 60. সৎ prover আলাদা জোড়ায় ৪,০০০ বারের প্রতিবার ঠিক: completeness 1. মিথ্যা দাবির জোড়ায় তিনটি কৌশলই প্রায় 0.5-এ আটকে আছে; “overlap” কৌশল যত চালাকই দেখাক, H-এর বণ্টন b-এর ওপর নির্ভর করে না বলে কোনো লাভ হয় না। k round-এ মাপা হার 2−k-এর কাছাকাছি, যেমন k = 8-এ প্রায় 0.004; ছোট পার্থক্যটুকু ৪,০০০ নমুনার স্বাভাবিক ওঠানামা।
প্রতারক prover-এর দৃষ্টিকোণ থেকে পুরো ব্যাপারটি দেখা যাক। নিচের stepper-এ দাবিটি মিথ্যা: G1 আসলে G0-এরই নাম-বদলানো রূপ।
1G0 ≅ G1, তবু দাবি “আলাদা”2H দেখে b-এর সম্ভাবনা3প্রতি round: আন্দাজ b′4একবার ভুল → reject
| round | |
| b ; b′ | |
| টিকে থাকার সম্ভাবনা |
- মিথ্যা দাবি. G1-এর edge 03 04 14 15 23 25, যা আসলে চক্র 0-3-2-5-1-4-0, অর্থাৎ C6. প্রতারক prover তবু বলছে graph দুটি আলাদা।
- H কিছুই বলে না. ধরুন V পাঠাল H = চক্র 0-2-4-1-3-5-0. গুনে দেখা গেছে, ৭২০টি π-এর মধ্যে ১২টি G0 থেকে এই H দেয়, আর ১২টি G1 থেকেও। তাই H দেখার পর Pr[b = 0] = 12/24 = 1/2.
- Round ১. এই সম্ভাব্য ধারায় b = 0, prover আন্দাজে বলল 0: পাস। এ পর্যন্ত টিকে থাকার সম্ভাবনা ১/২.
- Round ২. নতুন মুদ্রা b = 1, আন্দাজ 1: আবার পাস। দুটি স্বাধীন round মিলিয়ে সম্ভাবনা ১/৪.
- Round ৩. b = 0, কিন্তু আন্দাজ 1: V সঙ্গে সঙ্গে reject করে। একটি ভুলই যথেষ্ট, তাই prover-কে প্রতিটি round জিততে হয়।
- ২০ round. সব round পেরোনোর সম্ভাবনা 2−20, দশ লাখে একের কম। খরচ মাত্র ২০টি graph পাঠানো আর ২০টি bit তুলনা।
৪ · Arthur–Merlin — মুদ্রা যখন প্রকাশ্য
GNI protocol-এ সবকিছু নির্ভর করে b গোপন থাকার ওপর। প্রশ্ন জাগে: verifier-এর মুদ্রা যদি সবাই দেখে, তবু কি একই শক্তি থাকে? László Babai ১৯৮৫ সালে এমন protocol-কে খেলা হিসেবে বর্ণনা করেন: রাজা Arthur একজন polynomial সময়ের verifier, যে শুধু মুদ্রা ছুড়ে ফল জানিয়ে দেয়; জাদুকর Merlin সর্বশক্তিমান prover. এমন Arthur–Merlin protocol-এ verifier-এর প্রতিটি বার্তা শুধু তার নতুন এলোমেলো bit, আর শেষে সে পুরো কথোপকথন দেখে deterministic ভাবে সিদ্ধান্ত নেয়। একে বলা হয় public coin; GNI-এর মতো protocol, যেখানে মুদ্রা গোপন, private coin.
MA: Merlin একটি বার্তা পাঠায়, তারপর Arthur মুদ্রা ছুড়ে polynomial সময়ে যাচাই করে। এটি “এলোমেলো verifier-সহ NP”.
AM: Arthur আগে একটি এলোমেলো string পাঠায়, Merlin উত্তর দেয়, তারপর Arthur deterministic ভাবে যাচাই করে।
দুটিতেই completeness ≥ 2/3 আর soundness ≤ 1/3, IP-র মতো।
জানা সম্পর্কগুলো, প্রমাণ বাদ দিয়ে, সূত্র হিসেবে (সাল আর নাম প্রচলিত সূত্র অনুযায়ী):
- NP ∪ BPP ⊆ MA ⊆ AM ⊆ Π2p, অর্থাৎ AM পর্ব ৬৮-এর polynomial hierarchy-র দ্বিতীয় স্তরে।
- যেকোনো ধ্রুবক-সংখ্যক বার্তার Arthur–Merlin protocol দুই বার্তায় নামানো যায় (Babai, ১৯৮৫)।
- Goldwasser আর Sipser (১৯৮৬): k বার্তার private-coin protocol-কে k + 2 বার্তার public-coin protocol দিয়ে অনুকরণ করা যায়। তাই polynomial সংখ্যক বার্তায় public coin-এর শক্তি IP-র সমান, আর GNI ∈ AM.
শেষ ফলটির একটি সুন্দর পরিণতি আছে। Boppana, Håstad আর Zachos ১৯৮৭ সালে দেখান বলে পরিচিত: coNP ⊆ AM হলে polynomial hierarchy দ্বিতীয় স্তরে ধসে পড়ে (collapse). এখন GI যদি NP-complete হতো, তার complement GNI হতো coNP-complete, আর GNI ∈ AM থেকে coNP ⊆ AM আসত। তাই GI NP-complete হলে PH = Σ2p, যা বেশিরভাগ গবেষক অসম্ভাব্য মনে করেন। পর্ব ৬৩-এ GI-কে NP-intermediate-এর প্রার্থী বলার একটি বড় কারণ এটিই, আর ২০১৫ সালে Babai-এর quasi-polynomial algorithm এই ছবিকে আরও জোরালো করে।
Public-coin GNI protocol-এর ধারণা, শুধু রূপরেখা: দুটি graph আলাদা হলে “G0 বা G1-এর isomorphic graph” (তাদের automorphism-সহ গুনলে) সংখ্যায় একই হলে যতগুলো হতো তার দ্বিগুণ। Arthur একটি এলোমেলো hash function প্রকাশ্যে পাঠায়, আর Merlin সেই সেটের এমন একটি উপাদান দেখায় যার hash একটি নির্দিষ্ট মানে পড়ে; বড় সেটে এমন উপাদান পাওয়ার সম্ভাবনা লক্ষণীয়ভাবে বেশি। মুদ্রা প্রকাশ্য হলেও কাজ চলে, কারণ এখানে প্রশ্নটি “কোন graph” নয়, “সেটটি কত বড়”।
৫ · Sum-check আর IP = PSPACE
GNI coNP-তে, কিন্তু coNP-complete বলে জানা নেই। coNP-complete সমস্যা, যেমন UNSAT (“এই সূত্রের কোনো সত্য-করা মান নেই”), কি interactive proof পায়? ১৯৮৯ সালের শেষে আর ১৯৯০ সালের শুরুতে কয়েক সপ্তাহের মধ্যে উত্তর এল, এবং তা প্রত্যাশার চেয়ে অনেক বড়। মূল কৌশল দুটি।
Arithmetization. একটি Boolean সূত্রকে একটি polynomial-এ রূপান্তর, যা 0/1 মানে সূত্রের সঙ্গে মেলে: x ∧ y → x · y, ¬x → 1 − x, আর x ∨ y → x + y − x · y. যেমন
φ = (x1 ∨ x2) ∧ (¬x2 ∨ x3) ∧ (x1 ∨ ¬x3)
φ̃ = (x1 + x2 − x1x2) · (1 − x2 + x2x3) · (1 − x3 + x1x3)
প্রতিটি 0/1 মানে φ̃ = 1 ঠিক যখন φ সত্য, তাই φ-এর সত্য-করা মানের সংখ্যা #φ = Σx ∈ {0,1}3 φ̃(x). এখানে #φ = 3 (100, 101, 111). এখন φ̃-কে একটি মৌলিক p-এর field 𝔽p-এ যেকোনো মানে, যেমন x1 = 9-এও, হিসাব করা যায়। এই বাড়তি জায়গাই verifier-এর অস্ত্র।
Sum-check protocol. Prover দাবি করে Σx ∈ {0,1}n g(x) = K, যেখানে g একটি polynomial, প্রতিটি চলকে degree ≤ d. সব 2n পদ যোগ করা verifier-এর পক্ষে অসম্ভব। তাই চলকগুলো একে একে সরানো হয়:
- Round i-তে prover একটি এক-চলকের polynomial gi(X) পাঠায়, যা দাবি করে g(r1, …, ri−1, X, xi+1, …, xn)-এর বাকি চলকগুলোর সব 0/1 মানে যোগফল। (Degree ≤ d, তাই d + 1টি মান পাঠালেই চলে।)
- Verifier মেলায় gi(0) + gi(1) = বর্তমান দাবি; না মিললে reject.
- Verifier এলোমেলো ri ∈ 𝔽p বেছে পাঠায়; নতুন দাবি gi(ri).
- n round শেষে verifier নিজে একবার g(r1, …, rn) হিসাব করে শেষ দাবির সঙ্গে মেলায়।
1দাবি: Σ φ̃(x) = K2P: g_i-এর মান X = 0, 1, 2-এ3V: g_i(0) + g_i(1) = দাবি?4V: এলোমেলো r_i; দাবি ← g_i(r_i)5শেষে: φ̃(r) = দাবি?
| g(0), g(1), g(2) | |
| যোগফল মেলানো | |
| r ; নতুন দাবি |
- দাবি. Prover বলে #φ = K = 3, আর হিসাব 𝔽13-এ। φ̃-এর প্রতিটি চলকে degree ≤ 2, কারণ প্রতিটি চলক দুটি clause-এ আছে; তাই প্রতিটি gi তিনটি মান দিয়ে নির্ধারিত।
- Round ১. g1(X) = Σx2, x3 φ̃(X, x2, x3); মান 0, 3, 8, অর্থাৎ g1(X) = X2 + 2X. যাচাই: 0 + 3 = 3 = K. V বাছে r1 = 9; নতুন দাবি g1(9) = 81 + 18 = 99 ≡ 8.
- Round ২. g2(X) = Σx3 φ̃(9, X, x3); মান 12, 9, 9. যাচাই: 12 + 9 = 21 ≡ 8 ✓. r2 = 8; নতুন দাবি g2(8) ≡ 7.
- Round ৩. g3(X) = φ̃(9, 8, X); মান 8, 12, 9. যাচাই: 8 + 12 = 20 ≡ 7 ✓. r3 = 1; নতুন দাবি g3(1) = 12.
- শেষ পরীক্ষা. V নিজে হিসাব করে: 9 + 8 − 72 ≡ 10, 1 − 8 + 8 = 1, 1 − 1 + 9 = 9; গুণফল 90 ≡ 12. দাবির সঙ্গে মিলল: accept. V φ̃-কে মাত্র একবার হিসাব করেছে, ৮টি পদ যোগ করেনি।
- কেন sound. K মিথ্যা হলে প্রথম round-এ prover-কে একটি ভুল g1 পাঠাতেই হয়। Degree ≤ 2-এর দুটি আলাদা polynomial বড়জোর ২টি বিন্দুতে মেলে, তাই এলোমেলো r1-এ মিথ্যা টিকে যাওয়ার সম্ভাবনা ≤ 2/13. তিন round মিলে ≤ 3 · 2/13 = 6/13.
দাবি মিথ্যা হলে যেকোনো prover-এর সঙ্গে verifier accept করার সম্ভাবনা ≤ n · d / p, যেখানে n চলকের সংখ্যা, d প্রতিটি চলকে degree-এর সীমা, আর p field-এর আকার। সত্য দাবিতে সৎ prover-এর সঙ্গে সম্ভাবনা 1.
প্রমাণের রূপরেখা।
- Round i-এর শুরুতে দাবিটি মিথ্যা ধরুন। Prover সত্যিকারের polynomial si পাঠালে si(0) + si(1) মিথ্যা দাবির সমান হয় না, তাই সে reject হয়। অতএব সে পাঠায় gi ≠ si. — যোগফলের পরীক্ষা
- gi − si একটি অশূন্য polynomial, degree ≤ d, তাই এর মূল বড়জোর d টি। এলোমেলো ri একটি মূলে পড়ার সম্ভাবনা ≤ d/p; না পড়লে নতুন দাবি gi(ri) ≠ si(ri), অর্থাৎ পরের round-ও মিথ্যা দাবি নিয়ে শুরু হয়। — Schwartz–Zippel-এর এক-চলকের রূপ, পর্ব ৬৯
- শেষ round-এর পরেও দাবি মিথ্যা থাকলে verifier-এর নিজের হিসাব তা ধরে ফেলে। তাই accept হতে হলে কোনো এক round-এ ri-কে মূলে পড়তে হয়; union bound দিয়ে সম্ভাবনা ≤ n · d/p. ∎
এখান থেকে Lund, Fortnow, Karloff আর Nisan (১৯৯০ সালে ঘোষিত, ১৯৯২ সালে প্রকাশিত) দেখান, “#φ = K” প্রশ্নের interactive proof আছে। K = 0 বসালেই UNSAT, তাই coNP ⊆ IP: একটি সূত্রের যে কোনো সমাধান নেই, তার প্রমাণ কথোপকথনে দেওয়া যায়, যদিও ছোট certificate আছে বলে জানা নেই। নিচের ব্লক stepper-এর কথোপকথন হুবহু চালায়, তারপর একটি প্রতারক prover চালায়, যে K = 4 দাবি করে আর প্রতি round-এ এমন ভুল polynomial বানায় যা সত্যিকারের polynomial-এর সঙ্গে দুটি বিন্দুতে মেলে, যাতে ভাগ্য ভালো হলে “সত্য পথে” ফিরে আসা যায়।
# Sum-check: a prover claims #SAT(phi) = K; the verifier evaluates phi only once.
import random
from itertools import product
rng = random.Random(74)
def phi(x, p): # (x1 or x2) and (not x2 or x3) and (x1 or not x3)
OR = lambda a, b: a + b - a * b
return OR(x[0], x[1]) * OR(1 - x[1], x[2]) * OR(x[0], 1 - x[2]) % p
def honest(fixed, claim, p): # g(X) at X = 0, 1, 2; later variables summed over 0/1
k = 2 - len(fixed)
return [sum(phi(fixed + [X, *t], p) for t in product((0, 1), repeat=k)) % p
for X in (0, 1, 2)]
def at(g, r, p): # value at r of the degree-2 polynomial through g
return (g[0]*(r-1)*(r-2) - 2*g[1]*r*(r-2) + g[2]*r*(r-1)) * pow(2, -1, p) % p
def cheat(fixed, claim, p): # add h(X) = a(X-s)(X-t) so that the sum fits the lie
g = honest(fixed, claim, p); d = (claim - g[0] - g[1]) % p
if d == 0: return g # back on the true track: play honestly
while (den := (s := rng.randrange(p)) * (t := rng.randrange(p))
+ (1 - s) * (1 - t)) % p == 0: pass
a = d * pow(den, -1, p) % p
return [(g[X] + a * (X - s) * (X - t)) % p for X in (0, 1, 2)]
def run(prover, K, p, log=False):
claim, fixed = K % p, []
for i in range(3):
g = prover(fixed, claim, p)
if (g[0] + g[1]) % p != claim: return False
r = rng.randrange(p); fixed.append(r)
if log: print(f" round {i+1}: g(0..2) = {g}, sum = {claim}, r{i+1} = {r}")
claim = at(g, r, p)
if log: print(f" final: phi{tuple(fixed)} = {phi(fixed, p)}, claim = {claim}")
return phi(fixed, p) == claim
print("true count:", sum(phi(list(x), 13) for x in product((0, 1), repeat=3)))
print("honest prover, K = 3, p = 13 ->", run(honest, 3, 13, log=True))
for p, T in ((13, 20000), (2**31 - 1, 2000)):
ok = sum(run(cheat, 4, p) for _ in range(T))
print(f"cheater claims K = 4, p = {p}: accepted {ok/T:.4f}, bound 3*2/p = {6/p:.2g}")আসল আউটপুট (ব্রাউজারের Python):
true count: 3
round 1: g(0..2) = [0, 3, 8], sum = 3, r1 = 9
round 2: g(0..2) = [12, 9, 9], sum = 8, r2 = 8
round 3: g(0..2) = [8, 12, 9], sum = 7, r3 = 1
final: phi(9, 8, 1) = 12, claim = 12
honest prover, K = 3, p = 13 -> True
cheater claims K = 4, p = 13: accepted 0.3815, bound 3*2/p = 0.46
cheater claims K = 4, p = 2147483647: accepted 0.0000, bound 3*2/p = 2.8e-09
প্রথম লাইনে সব ৮টি 0/1 মান যোগ করে আসল সংখ্যা 3. সৎ কথোপকথন stepper-এর প্রতিটি সংখ্যা মেলায়: g-এর মান, প্রতিটি যোগফল, r1 = 9, r2 = 8, r3 = 1, আর শেষে φ̃(9, 8, 1) = 12. ছোট field 𝔽13-এ প্রতারক প্রায় ৩৮ শতাংশ সময় পার পেয়ে যায়, যা উপপাদ্য ৫.১-এর সীমা 6/13 ≈ 0.46-এর নিচে; সীমা প্রায় আঁটসাঁট, কারণ এই প্রতারক প্রতি round-এ সর্বোচ্চ ২টি মিলের বিন্দু কাজে লাগায়। p = 231 − 1 নিলে সীমা প্রায় 2.8 × 10−9, আর ২,০০০ চেষ্টায় একবারও পার পায়নি। শিক্ষা: field বড় রাখাই soundness-এর চাবি, আর তার খরচ সামান্য, কারণ সংখ্যাগুলোর দৈর্ঘ্য log p bit.
IP = PSPACE.
IP ⊆ PSPACE, প্রমাণের রূপরেখা। Input w আর verifier V স্থির রাখুন। সবচেয়ে ভালো prover-এর সঙ্গে accept-এর সম্ভাবনা একটি গাছের মান: V-এর বার্তার জায়গায় তার সব মুদ্রার ওপর গড়, prover-এর বার্তার জায়গায় সব সম্ভাব্য বার্তার ওপর সর্বোচ্চ। গাছের গভীরতা polynomial, তাই পর্ব ৬৫-এর TQBF evaluator-এর মতো depth-first হিসাবে polynomial জায়গা লাগে, সময় exponential হলেও। মান ≥ 2/3 কি না দেখে সিদ্ধান্ত। ∎
PSPACE ⊆ IP, শুধু ধারণা। TQBF PSPACE-complete, তাই TQBF ∈ IP দেখানোই যথেষ্ট। ∃x আর ∀x-কেও arithmetize করা হয়: ∀x ψ → ψ(0) · ψ(1), আর ∃x ψ → 1 − (1 − ψ(0))(1 − ψ(1)). তারপর sum-check-এর মতো quantifier একে একে খোলা হয়। সমস্যা হলো প্রতিটি গুণে degree দ্বিগুণ হয়ে exponential হতে পারে; Shamir-এর কৌশল প্রতিটি ধাপে একটি “degree কমানো” (linearization) ক্রিয়া যোগ করে, যা 0/1 মান বদলায় না কিন্তু degree রাখে 1. বিস্তারিত Sipser-এর বইয়ের interactive proof অধ্যায়ে আছে।
IP = PSPACE ইতিহাসেও গুরুত্বপূর্ণ: এমন oracle জানা আছে যার সামনে IP আর PSPACE আলাদা হয়ে যায়, তাই ফলটি relativization-এর বাধা পেরোনো একটি প্রমাণ। পর্ব ৬৩-এ দেখেছেন, পরে algebrization নামের আরেকটি বাধা দেখায় যে শুধু এই কৌশল দিয়েও P বনাম NP মীমাংসা হবে না।
৬ · Zero knowledge — প্রমাণ দেওয়া, কিন্তু কিছু না শেখানো
GI-এর সাধারণ প্রমাণ হলো permutation σ নিজেই দেখিয়ে দেওয়া। কিন্তু ধরুন σ একটি গোপন চাবি: যে σ জানে, সে-ই বাজারঘরের সার্ভারে প্রবেশ করতে পারে। তখন প্রশ্ন হয়: σ না দেখিয়ে কি প্রমাণ করা যায় যে আমি σ জানি, বা অন্তত G0 ≅ G1? Goldwasser, Micali আর Rackoff ১৯৮৫ সালের প্রবন্ধে interactive proof-এর সঙ্গেই এই প্রশ্নের নিখুঁত রূপ দেন: zero-knowledge proof.
বাজারঘরের ছয়টি অর্ডারের মধ্যে কিছু জোড়া একই ডেলিভারি-কর্মী পায়, তাই সেই জোড়ার slot আলাদা হতে হবে (সকাল, দুপুর, বিকেল)। একজন পরিকল্পনাকারী দাবি করেন তাঁর কাছে একটি বৈধ slot-পরিকল্পনা আছে, কিন্তু পরিকল্পনাটি তাঁর ব্যবসার গোপন সম্পদ। তিনি টেবিলে ছয়টি উল্টানো কাপ রাখেন, প্রতিটির নিচে একটি অর্ডারের slot-কার্ড, তবে প্রতিবার slot-এর নামগুলো গোপনে এলোমেলোভাবে অদলবদল করে (যেমন সকাল ↔ বিকেল)। ব্যবস্থাপক যেকোনো একটি দ্বন্দ্ব-জোড়া বেছে শুধু সেই দুটি কাপ তোলেন: দুটি কার্ড আলাদা কি না। পরিকল্পনা বৈধ হলে প্রতিবার আলাদা দেখা যায়; ভুয়া হলে কোনো এক দ্বন্দ্বে ধরা পড়ার ঝুঁকি থাকে। অথচ ব্যবস্থাপক প্রতিবার দেখেন শুধু “দুটি এলোমেলো আলাদা slot”, যা তিনি নিজেই মুদ্রা ছুড়ে বানাতে পারতেন। এটিই zero knowledge-এর মর্ম। কাপের কাজটি গাণিতিকভাবে করে একটি commitment scheme (অংশ ৭)।
“কিছুই শেখে না” কথাটিকে গণিতে আনার কৌশল হলো তুলনা: verifier কথোপকথন থেকে যা পায়, তা কি সে prover ছাড়াই, নিজে নিজে বানাতে পারত? পারলে কথোপকথন তাকে নতুন কিছু দেয়নি।
Language A-র একটি interactive proof (P, V) perfect zero-knowledge, যদি প্রতিটি polynomial সময়ের verifier-কৌশল V* (সে protocol না মেনে যা খুশি প্রশ্ন করতে পারে) এর জন্য একটি প্রত্যাশিত polynomial সময়ের probabilistic algorithm S থাকে, যাকে বলা হয় simulator, যাতে প্রতিটি w ∈ A-তে S(w)-এর আউটপুটের বণ্টন আর P-এর সঙ্গে কথোপকথনে V*-এর দেখা সবকিছুর (তার মুদ্রা আর পাওয়া বার্তা) বণ্টন হুবহু এক।
বণ্টন দুটি শুধু খুব কাছাকাছি হলে statistical, আর polynomial সময়ের কোনো যন্ত্র আলাদা করতে না পারলে computational zero knowledge. শুধু সৎ V-এর জন্য S থাকলে বলা হয় honest-verifier zero knowledge.
লক্ষ করুন, শর্তটি শুধু w ∈ A-তে। Simulator-এর কাছে গোপন σ নেই, অথচ তাকে এমন কথোপকথন বানাতে হবে যা আসলটির থেকে আলাদা করা যায় না। প্রথমে অদ্ভুত লাগে: simulator যদি σ ছাড়াই “প্রমাণ” বানাতে পারে, তাহলে প্রমাণের মূল্য কী? উত্তর: আসল কথোপকথনে verifier-এর প্রশ্ন আসে prover বার্তা পাঠানোর পরে, আর সেটাই prover-কে আটকায়। Simulator ক্রম উল্টে দিতে পারে: আগে প্রশ্নটি আন্দাজ করে, তারপর বার্তা বানায়, আর আন্দাজ ভুল হলে শুরু থেকে আবার চালায় (rewind). Prover-এর এই সুবিধা নেই।
সাধারণ input G0, G1; prover-এর গোপন σ, যাতে G1 = σ(G0). প্রতিটি round:
- P একটি এলোমেলো permutation π বেছে H = π(G1) পাঠায়।
- V এলোমেলো b ∈ {0, 1} পাঠায়।
- b = 1 হলে P পাঠায় ρ = π; b = 0 হলে ρ = π ∘ σ, অর্থাৎ v ↦ π(σ(v)).
- V মেলায় ρ(Gb) = H.
1P: এলোমেলো π, H ← π(G1) → V2V: মুদ্রা b → P3b = 1: ρ ← π4b = 0: ρ ← π ∘ σ5V: ρ(G_b) = H হলে পাস
| H | |
| b | |
| ρ |
- গোপন σ. G0 হলো পথ 0-1-2-3. σ = (2, 0, 3, 1) মানে 0 → 2, 1 → 0, 2 → 3, 3 → 1; তাই edge 01 → 20, 12 → 03, 23 → 31, অর্থাৎ G1 = 02 03 13.
- প্রথম বার্তা. P বাছে π = (3, 1, 0, 2) আর পাঠায় H = π(G1): 02 → 30, 03 → 32, 13 → 12, অর্থাৎ H = 03 23 12, পথ 0-3-2-1. প্রতি round-এ নতুন π, তাই H একটি নতুন এলোমেলো copy.
- প্রশ্ন. H পাঠানোর পরে V মুদ্রা ছোড়ে: b = 0, অর্থাৎ “H কীভাবে G0 থেকে আসে, দেখান”। P আগে থেকে b জানত না।
- উত্তর. ρ = π ∘ σ: ρ(0) = π(2) = 0, ρ(1) = π(0) = 3, ρ(2) = π(3) = 2, ρ(3) = π(1) = 1; তাই ρ = (0, 3, 2, 1).
- যাচাই. ρ(G0): 01 → 03, 12 → 32, 23 → 21, অর্থাৎ 03 23 12 = H. পাস। b = 1 হলে P পাঠাত π নিজে, আর V মেলাত π(G1) = H.
- V কী শিখল. π সুষম এলোমেলো বলে ρ = π ∘ σ-ও সুষম এলোমেলো, σ-এর কোনো ছাপ নেই। V কখনো π আর ρ দুটিই পায় না; পেলে σ = π−1 ∘ ρ বের হয়ে যেত।
Protocol ৬.২-এর completeness 1, প্রতি round-এ soundness error 1/2, আর এটি perfect zero-knowledge.
প্রমাণ।
- Completeness: b = 1-এ π(G1) = H সংজ্ঞা থেকে; b = 0-এ (π ∘ σ)(G0) = π(σ(G0)) = π(G1) = H. — সরাসরি হিসাব
- Soundness: G0 ≇ G1 হলে যেকোনো H বড়জোর একটি Gb-এর isomorphic, তাই দুটি প্রশ্নের অন্তত একটির কোনো বৈধ ρ নেই। V-এর b H-এর পরে আর স্বাধীনভাবে আসে, তাই ধরা পড়ার সম্ভাবনা ≥ 1/2. — প্রশ্ন আসে পরে
- Simulator: S-এর কাজ: এলোমেলো b′ আর এলোমেলো ρ বেছে H = ρ(Gb′) বানানো; V*-কে H দিয়ে তার প্রশ্ন b নেওয়া; b = b′ হলে (H, b, ρ) আউটপুট দেওয়া, নইলে V*-কে শুরুর অবস্থায় ফিরিয়ে আবার চেষ্টা। G0 ≅ G1 বলে H-এর বণ্টন b′-এর ওপর নির্ভর করে না, তাই V* b′ জানতে পারে না, আর প্রতিটি চেষ্টায় সফলতার সম্ভাবনা ঠিক 1/2: প্রত্যাশিত চেষ্টা ২টি। — আন্দাজ আর rewind
- বণ্টন এক: আসল কথোপকথনে b সুষম, ρ একটি সুষম এলোমেলো permutation (b = 1-এ ρ = π, b = 0-এ ρ = π ∘ σ, দুটিই সুষম), আর H = ρ(Gb). Simulator-এর সফল আউটপুটেও b সুষম, ρ সুষম আর H = ρ(Gb). তাই দুটি বণ্টন হুবহু এক। ∎
নিচের ব্লক সংজ্ঞাটি একটি ছোট উদাহরণে হুবহু পরীক্ষা করে: stepper-এর G0 আর σ নিয়ে সৎ verifier-এর সঙ্গে সব ২৪ × ২ = ৪৮টি সমান-সম্ভাব্য আসল কথোপকথন তালিকা করে, আর simulator-এর (যে σ কোথাও ব্যবহার করে না) সব সফল আউটপুটও তালিকা করে, তারপর দুটি বণ্টন মেলায়। শেষে একটি মিথ্যা দাবি (পথ ≅ তারা-আকৃতির graph) পরীক্ষা করে।
# Zero-knowledge proof for graph isomorphism: real transcripts vs a simulator.
from itertools import permutations
from collections import Counter
PERMS = list(permutations(range(4)))
def graph(edges): return frozenset(frozenset(e) for e in edges)
def relabel(G, p): return frozenset(frozenset(p[v] for v in e) for e in G)
G0 = graph([(0, 1), (1, 2), (2, 3)]) # a path on 4 vertices
sigma = (2, 0, 3, 1) # the prover's secret: G1 = sigma(G0)
G1 = relabel(G0, sigma)
print("G0 =", sorted(map(sorted, G0)), "| G1 =", sorted(map(sorted, G1)))
real = Counter() # every (pi, b) is equally likely
for pi in PERMS:
H = relabel(G1, pi) # prover's first message
for b in (0, 1): # honest verifier's coin
rho = pi if b == 1 else tuple(pi[sigma[v]] for v in range(4))
assert relabel((G0, G1)[b], rho) == H # the verifier's check passes
real[(H, b, rho)] += 1
sim = Counter() # simulator: no sigma used anywhere
for guess in (0, 1):
for rho in PERMS:
H = relabel((G0, G1)[guess], rho)
for b in (0, 1): # verifier's coin; keep only lucky runs
if b == guess: sim[(H, b, rho)] += 1
print("distinct transcripts: real", len(real), "| simulated", len(sim))
print("same distribution:", real == sim)
print("answers rho seen when b = 0:", len({t[2] for t in real if t[1] == 0}), "of", len(PERMS), "(all of them)")
STAR = graph([(0, 1), (0, 2), (0, 3)]) # not isomorphic to G0: claim is false
caught = 0 # even an all-powerful cheater fails here
for c in (0, 1):
for pi in PERMS:
H = relabel((G0, STAR)[c], pi)
for b in (0, 1):
ok = any(relabel((G0, STAR)[b], r) == H for r in PERMS)
caught += not ok
print(f"false claim G0 ~ star: cheater caught in {caught} of 96 cases = {caught/96:.2f}")আসল আউটপুট (ব্রাউজারের Python):
G0 = [[0, 1], [1, 2], [2, 3]] | G1 = [[0, 2], [0, 3], [1, 3]]
distinct transcripts: real 48 | simulated 48
same distribution: True
answers rho seen when b = 0: 24 of 24 (all of them)
false claim G0 ~ star: cheater caught in 48 of 96 cases = 0.50
আসল আর simulated কথোপকথন দুটিতেই ৪৮টি আলাদা transcript, প্রতিটি একবার, আর বণ্টন দুটি হুবহু এক (True): perfect zero knowledge-এর সংজ্ঞা এই ছোট উদাহরণে সরাসরি পূরণ হলো। b = 0-এ verifier যে ρ দেখে, তা ২৪টি permutation-এর প্রতিটিই সমান সম্ভাবনায় হতে পারে, তাই একটি ρ দেখে σ সম্পর্কে কিছু বলা যায় না। শেষ লাইনে দাবিটি মিথ্যা: পথ আর তারা-আকৃতির graph-এর degree-তালিকাই আলাদা। এখানে prover সর্বশক্তিমান হলেও, যে-ই H পাঠাক, ৯৬টি সমান-সম্ভাব্য ক্ষেত্রের ঠিক ৪৮টিতে বৈধ উত্তর নেই: soundness error ঠিক 1/2.
এই protocol আরও একটি জিনিস দেখায়। একই H-এর জন্য দুটি প্রশ্নেরই উত্তর দিতে পারে এমন prover থেকে σ = π−1 ∘ ρ বের করা যায়। তাই protocol-টি শুধু “G0 ≅ G1” নয়, “আমি σ জানি” দাবিরও প্রমাণ দেয়; একে বলা হয় proof of knowledge. পরিচয় যাচাইয়ের protocol-গুলো ঠিক এই ধরনের দাবি করে।
৭ · সব NP-র জন্য zero knowledge, আর বাস্তবে এর ব্যবহার
GI-এর protocol সুন্দর, কিন্তু GI একটি বিশেষ সমস্যা। Goldreich, Micali আর Wigderson ১৯৮৬ সালে দেখান: one-way function থাকলে NP-র প্রতিটি language-এর computational zero-knowledge proof আছে। কৌশলটি অংশ ৬-এর কাপের গল্প। NP-complete 3-COLOR-এর জন্য protocol বানালেই চলে, কারণ যেকোনো NP দাবি polynomial সময়ে 3-COLOR-এর একটি instance-এ রূপান্তর করা যায় (পর্ব ৬১)। প্রতিটি round-এ prover রংগুলো এলোমেলোভাবে অদলবদল করে প্রতিটি vertex-এর রং একটি commitment-এ “কাপের নিচে” রাখে, verifier একটি এলোমেলো edge বেছে শুধু তার দুই প্রান্ত খুলতে বলে।
Commitment scheme-এর দুটি গুণ লাগে: hiding (খোলার আগে ভেতরের মান বোঝা যায় না) আর binding (একবার রাখার পর মান বদলানো যায় না)। One-way function থাকলে এমন scheme বানানো যায় বলে জানা, আর এখানেই cryptographic অনুমান ঢোকে, যা one-way function-এর পর্ব ৭৬-এ বিস্তারিত আসবে। নিচের JavaScript ব্লক কাপগুলো সরাসরি অনুকরণ করে (commitment-এর গণিত বাদ দিয়ে): বাজারঘরের ছয়টি অর্ডার, নয়টি দ্বন্দ্ব, একটি বৈধ আর একটি ভুয়া slot-পরিকল্পনা।
// Bazarghar delivery slots: a zero-knowledge "cups" protocol for 3-colouring
let seed = 74; // small seeded PRNG (mulberry32)
function rand() { seed = (seed + 0x6D2B79F5) | 0; let t = seed;
t = Math.imul(t ^ (t >>> 15), t | 1); t ^= t + Math.imul(t ^ (t >>> 7), t | 61);
return ((t ^ (t >>> 14)) >>> 0) / 4294967296; }
const pick = (n) => Math.floor(rand() * n);
const E = [[0,1],[0,2],[1,2],[1,3],[2,4],[3,4],[3,5],[4,5],[0,5]]; // order conflicts
const good = [0, 1, 2, 0, 1, 2]; // a valid slot plan: no conflict shares a slot
const bad = [0, 1, 2, 0, 1, 1]; // a fake plan: edge 4-5 shares slot 1
function round(col) { // one round; returns opened colours or null
const perm = [[0,1,2],[0,2,1],[1,0,2],[1,2,0],[2,0,1],[2,1,0]][pick(6)];
const cups = col.map((c) => perm[c]); // prover hides recoloured plan under cups
const [u, v] = E[pick(E.length)]; // verifier lifts the cups of one conflict
return cups[u] !== cups[v] ? [cups[u], cups[v]] : null;
}
const T = 9000;
let pass = 0, seen = {};
for (let i = 0; i < T; i++) {
const r = round(good); if (r) { pass++; seen[r.join("")] = (seen[r.join("")] || 0) + 1; }
}
console.log(`valid plan: passed ${pass}/${T} rounds`);
console.log("opened slot pairs:", JSON.stringify(seen));
let ok = 0;
for (let i = 0; i < T; i++) if (round(bad)) ok++;
console.log(`fake plan: survives one round ${(ok / T).toFixed(3)} (exact 8/9 = 0.889)`);
const m = E.length;
for (const target of [0.5, 0.01, 1e-6]) {
const k = Math.ceil(Math.log(target) / Math.log(1 - 1 / m));
console.log(`rounds so a fake plan survives with prob <= ${target}: k = ${k}`);
}আসল আউটপুট (ব্রাউজারের JavaScript):
valid plan: passed 9000/9000 rounds
opened slot pairs: {"10":1491,"12":1476,"20":1537,"21":1500,"02":1505,"01":1491}
fake plan: survives one round 0.894 (exact 8/9 = 0.889)
rounds so a fake plan survives with prob <= 0.5: k = 6
rounds so a fake plan survives with prob <= 0.01: k = 40
rounds so a fake plan survives with prob <= 0.000001: k = 118
বৈধ পরিকল্পনা ৯,০০০ round-এর প্রতিটিতে পাস করে। খোলা কাপে দেখা slot-জোড়া (যেমন "01" মানে সকাল আর দুপুর) ছয় রকমের, আর প্রতিটি প্রায় ১,৫০০ বার, অর্থাৎ সমান সম্ভাবনায়: রং প্রতিবার নতুন করে অদলবদল হয় বলে verifier শুধু “দুটি আলাদা slot” দেখে, পরিকল্পনার কিছুই নয়। ভুয়া পরিকল্পনার একটিমাত্র দ্বন্দ্ব (4-5) ভুল, তাই verifier সেই edge বাছলে তবেই ধরা পড়ে: টিকে থাকার হার প্রায় 8/9. তাই একটি round খুব দুর্বল; (8/9)k ≤ 10−6 চাইলে k = 118 round লাগে। সাধারণভাবে m-টি edge-এ প্রায় m · ln(1/ε) round লাগে, যা এখনো polynomial.
৭.১ Interaction ছাড়া — Fiat–Shamir
বাস্তবে বারবার কথোপকথন অসুবিধাজনক, আর কথোপকথনের transcript তৃতীয় কাউকে দেখিয়ে লাভ নেই, কারণ simulator ঠিক এমন transcript বানাতে পারে। Fiat আর Shamir ১৯৮৬ সালে প্রস্তাব করেন: verifier-এর এলোমেলো প্রশ্নের বদলে prover-এর প্রথম বার্তা (আর সব প্রকাশ্য input) একটি cryptographic hash function-এ দিয়ে তার ফলকে প্রশ্ন ধরা হোক। তখন প্রমাণটি একটি বার্তা হয়ে যায়, যা যে কেউ যাচাই করতে পারে। এই Fiat–Shamir heuristic-এর নিরাপত্তা সাধারণত “random oracle” নামের একটি আদর্শায়িত মডেলে যুক্তি দিয়ে দেখানো হয়, শর্তহীন প্রমাণ নয়। Hash-এ কোনো প্রকাশ্য input বাদ পড়লে বাস্তবের implementation-এ গুরুতর ত্রুটি হয়েছে বলে নিরাপত্তা-গবেষকেরা জানিয়েছেন। Hash function-এর নিরাপত্তার দিক সাইবারসিকিউরিটি কোর্সের পর্ব ০৯-এ আছে।
৭.২ কোথায় কাজে লাগে, আর কোথায় সতর্কতা
- পরিচয় যাচাই. Schnorr-এর ১৯৮৯ সালের দিকের identification protocol একই ছকের: prover একটি গোপন চাবি জানে বলে প্রমাণ দেয়, চাবি না পাঠিয়ে। এটি challenge-response পদ্ধতির একটি গাণিতিক রূপ। বাস্তবের login বেশিরভাগ ক্ষেত্রে password, OTP বা passkey-র digital signature দিয়ে চলে; সেগুলোর নকশা সাইবারসিকিউরিটি কোর্সের পর্ব ১৫ আর পর্ব ১৬-এ।
- Blockchain আর বড় গণনার যাচাই. কিছু blockchain ব্যবস্থা ছোট, non-interactive zero-knowledge argument ব্যবহার করে, যাতে একটি লেনদেন বৈধ কি না যাচাই করা যায় পরিমাণ প্রকাশ না করে, বা অনেক লেনদেনের সঠিকতা একটি ছোট প্রমাণে দেখানো যায়। এগুলো argument, অর্থাৎ soundness শুধু polynomial সময়ের প্রতারকের বিরুদ্ধে, আর নির্ভর করে cryptographic অনুমান, কখনো কখনো একটি বিশ্বস্ত প্রাথমিক setup, আর ত্রুটিহীন implementation-এর ওপর। “Zero knowledge” শব্দটি থাকলেই কোনো ব্যবস্থা নিরাপদ বা গোপন হয়ে যায় না।
- নিজে বানাবেন না. এই পর্বের protocol শেখার জন্য; বাস্তবের নিরাপত্তায় যাচাই-করা library আর প্রতিষ্ঠিত মানদণ্ড ব্যবহার করুন, আর পরীক্ষা চালান শুধু নিজের system-এ।
আরও গভীরে: Verifier যদি দুজন prover-কে আলাদা ঘরে, যোগাযোগ ছাড়া, জেরা করতে পারে (MIP, Ben-Or, Goldwasser, Kilian আর Wigderson ১৯৮৮), শক্তি আরও বাড়ে: Babai, Fortnow আর Lund (১৯৯০–৯১) দেখান MIP = NEXP. এই ফলের পথ ধরেই PCP উপপাদ্য এসেছে (পর্ব ৭১)। Prover-রা quantum entanglement ভাগ করতে পারলে Ji, Natarajan, Vidick, Wright আর Yuen ২০২০ সালের একটি দীর্ঘ প্রবন্ধে দাবি করেন MIP* = RE, অর্থাৎ halting problem-এর মতো undecidable প্রশ্নেরও এমন প্রমাণ যাচাই করা যায়; গণিতের Connes embedding সমস্যার একটি নেতিবাচক উত্তরও এ থেকে আসে বলে জানানো হয়েছে। প্রমাণটি বিশাল, আর বিশেষজ্ঞদের যাচাই দীর্ঘ সময় ধরে চলেছে।
পরীক্ষা ও ইন্টারভিউতে: বিশ্ববিদ্যালয়, চাকরি বা ইন্টারভিউর পরীক্ষায় এই ধরনের প্রশ্ন প্রায়ই আসে:
- IP-র সংজ্ঞা দিন। Probabilistic polynomial সময়ের verifier; w ∈ A-তে কোনো prover ≥ 2/3, w ∉ A-তে প্রতিটি prover ≤ 1/3.
- GNI ∈ IP দেখান। গোপন b আর π, H = π(Gb), prover b বলে; আলাদা হলে সবসময় ঠিক, একই হলে H ও b স্বাধীন, তাই ১/২.
- Verifier deterministic হলে কী হয়? পুরো কথোপকথন একটি certificate, তাই শ্রেণিটি NP.
- IP = PSPACE-এর মূল কৌশল? Arithmetization আর sum-check; soundness আসে n · d/p সীমা থেকে।
- Zero knowledge-এর সংজ্ঞা দিন। প্রতিটি verifier-কৌশলের জন্য একটি simulator, যে গোপন তথ্য ছাড়াই একই বণ্টনের কথোপকথন বানায়।
৮ · AI-এর যুগে interactive proof
AI assistant এই বিষয়ে সহজেই “সুন্দর কিন্তু ভুল” ব্যাখ্যা দেয়, কারণ সংজ্ঞাগুলোর খুঁটিনাটি (কে মুদ্রা দেখে, কোন quantifier কোথায়) বদলালেই অর্থ বদলে যায়। ধরার উপায়: সংজ্ঞায় ফিরে যাওয়া, আর ছোট graph-এ সব permutation গুনে সম্ভাবনা নিজে হিসাব করা।
| AI-এর সাধারণ ভুল | কীভাবে ধরবেন |
|---|---|
| Soundness-কে “কোনো একটি prover-এর জন্য” লেখা | Soundness সব prover-এর জন্য; completeness-এ “একটি সৎ prover আছে” |
| GNI protocol-এ verifier-এর b প্রকাশ্য, বা H-এর আগে b পাঠানো | তাহলে prover শুধু b ফেরত দেয়; ছোট script-এ প্রতারকের হার 1 হয়ে যায় |
| “IP = NP” বা “interaction শুধু ভুল কমায়, শক্তি বাড়ায় না” | IP = PSPACE প্রমাণিত; deterministic verifier হলে তবেই NP |
| Zero knowledge মানে “verifier শুধু হ্যাঁ/না দেখে” বলা, simulator বাদ দেওয়া | সংজ্ঞা simulator দিয়ে, আর তা প্রতিটি verifier-কৌশলের জন্য (honest-verifier আলাদা ধারণা) |
| “GI NP-complete” বা “GNI ∈ NP প্রমাণিত” | দুটিই অজানা; GI NP-complete হলে PH দ্বিতীয় স্তরে ধসে পড়ে |
| “Zero-knowledge proof শর্তহীন নিরাপদ”, blockchain নিয়ে অতিরঞ্জন | NP-র জন্য ZK one-way function-এর অনুমানে; বাস্তব ব্যবস্থা অনুমান আর implementation-এর ওপর নির্ভরশীল |
| বানানো সাল বা লেখক (GMR, Babai, Shamir, MIP* = RE) | Sipser, Arora–Barak বা মূল প্রবন্ধে মিলিয়ে নিন |
AI-কে কাজে লাগানোর ভালো উপায়: সংজ্ঞা হুবহু চাওয়া, প্রতিটি সম্ভাবনার সীমা কোন যুক্তি থেকে এল তা জিজ্ঞাসা করা, আর এমন script চাওয়া যা ছোট উদাহরণে সব সম্ভাবনা গুনে দাবিটি পরীক্ষা করে।
AI-এর উত্তর হাতে পেলে — যাচাইয়ের চেকলিস্ট
ভাবনার প্রশ্ন
প্রতিটি প্রশ্ন নিয়ে নিজে কিছুক্ষণ ভাবুন, তারপর “→ উত্তর” চাপুন।
প্র ০১Interaction আর এলোমেলোতা আলাদাভাবে প্রায় কিছুই যোগ করে না, অথচ দুটি মিলে NP থেকে PSPACE-এ পৌঁছায়। এই “যোগফলের চেয়ে বেশি” শক্তির উৎস কী?
আলাদাভাবে দেখলে: deterministic verifier-এর সঙ্গে interaction দিলে prover পুরো কথোপকথন আগেই লিখে দিতে পারে, তাই শ্রেণি থাকে NP. Prover ছাড়া শুধু এলোমেলোতা দিলে পাওয়া যায় BPP, যা P-র সমান বলেই বেশিরভাগ গবেষক মনে করেন। একসঙ্গে দিলে আসে IP = PSPACE, যা NP-র চেয়ে অনেক বড় বলে ধারণা করা হয় (যদিও NP ≠ PSPACE প্রমাণিত নয়)।
রহস্যটি অপ্রত্যাশিত প্রশ্নে। এলোমেলো verifier এমন প্রশ্ন করে যা prover আগে থেকে জানে না, তাই prover-কে আগেই সব সম্ভাব্য প্রশ্নের জন্য একটি সামঞ্জস্যপূর্ণ উত্তর-কৌশল রাখতে হয়। মিথ্যা দাবিতে এমন সামঞ্জস্য রাখা অসম্ভব হয়ে দাঁড়ায়। Sum-check-এ এটি সবচেয়ে স্পষ্ট: prover একটি polynomial পাঠানোর পর একটি এলোমেলো বিন্দুতে আটকে যায়, আর মিথ্যা polynomial সত্যটির সঙ্গে খুব কম বিন্দুতে মেলে। Verifier একটি বিশাল যোগফল নিজে হিসাব করে না; সে শুধু prover-কে নিজের কথার জালে আটকায়।
ইতিহাসও মজার। ১৯৮৫ সালের STOC সম্মেলনে দুটি আলাদা প্রবন্ধ প্রায় একই ধারণায় পৌঁছায়: Goldwasser, Micali আর Rackoff cryptography-র প্রশ্ন থেকে (কতটুকু “জ্ঞান” ফাঁস হয়), আর Babai group theory-র একটি প্রশ্ন থেকে (Arthur–Merlin). ১৯৯৩ সালে এই পাঁচজন গবেষক (Babai-এর সহলেখক Moran-সহ) প্রথম Gödel Prize ভাগ করে পান বলে জানা যায়। কয়েক বছর পরেও ধারণা ছিল IP হয়তো NP-র খুব কাছাকাছি; ১৯৯০ সালে IP = PSPACE সেই ধারণা ভেঙে দেয়।
একটি সূক্ষ্ম কথা: “বড় শ্রেণি” মানে prover-এর কাজ সহজ নয়। PSPACE-complete দাবির সৎ prover-কেও সম্ভবত exponential সময় লাগে। লাভটি verifier-এর: সে polynomial সময়ে এমন দাবিতে আস্থা পায়, যা নিজে কখনো যাচাই করতে পারত না।
মূল উপলব্ধি: এলোমেলো, অপ্রত্যাশিত প্রশ্ন prover-কে আগে থেকে সব প্রশ্নের সামঞ্জস্যপূর্ণ উত্তর রাখতে বাধ্য করে; মিথ্যা দাবিতে তা অসম্ভব, আর এই কারণেই interaction ও এলোমেলোতা মিলে polynomial সময়ের verifier PSPACE-এর দাবি যাচাই করতে পারে।
প্র ০২GNI protocol-এর পুরো জোর গোপন মুদ্রায়, অথচ Goldwasser–Sipser বলে public coin-ও যথেষ্ট। এই দুটি কথা একসঙ্গে সত্য হয় কীভাবে, আর graph isomorphism-এর জটিলতা নিয়ে এর তাৎপর্য কী?
দুটি কথা আসলে আলাদা protocol নিয়ে। এই নির্দিষ্ট GNI protocol-এ b প্রকাশ্য হলে protocol ভেঙে যায়: prover শুধু b ফেরত দেয়। Goldwasser আর Sipser ১৯৮৬ সালে দেখান যে প্রতিটি private-coin protocol-এর জন্য অন্য একটি public-coin protocol আছে, যা সামান্য বেশি বার্তায় একই language চেনে। নতুন protocol-এ প্রশ্নটি বদলে যায়: “কোন graph পাঠানো হয়েছে” নয়, বরং “verifier-কে সন্তুষ্ট করে এমন এলোমেলো মুদ্রার সেটটি কত বড়”। সেট বড় কি না প্রমাণ করার জন্য একটি প্রকাশ্য, এলোমেলো hash function যথেষ্ট, কারণ বড় সেটের কোনো উপাদান একটি নির্দিষ্ট hash-মানে পড়ার সম্ভাবনা বেশি, আর prover সেই উপাদান দেখাতে পারে।
GNI-এর ক্ষেত্রে: graph দুটি আলাদা হলে “G0 বা G1-এর copy, সঙ্গে একটি automorphism”-জোড়ার সেটের আকার 2 · n!, আর একই হলে n!. দ্বিগুণ পার্থক্য hash দিয়ে ধরা যায়, তাই GNI ∈ AM.
এর তাৎপর্য গভীর। Boppana, Håstad আর Zachos ১৯৮৭ সালে দেখান বলে পরিচিত, coNP ⊆ AM হলে polynomial hierarchy দ্বিতীয় স্তরে ধসে পড়ে। GI NP-complete হলে GNI coNP-complete হতো, তখন coNP ⊆ AM, আর PH ধসে পড়ত। যেহেতু বেশিরভাগ গবেষক বিশ্বাস করেন PH ধসে পড়ে না, GI-কে NP-complete মনে করা হয় না। অন্যদিকে GI P-তে আছে বলেও জানা নেই। ২০১৫ সালে László Babai একটি quasi-polynomial algorithm ঘোষণা করেন; ২০১৭ সালে প্রমাণের একটি ত্রুটি পাওয়া গেলে তিনি তা সংশোধন করেন বলে জানা যায়। বাস্তবে GI-এর প্রোগ্রামগুলো (যেমন canonical labelling-ভিত্তিক) প্রায় সব graph-এ দ্রুত চলে।
একটি শিক্ষণীয় বিষয়: একটি interactive proof-এর ফল, যা মূলত cryptography থেকে আসা ধারণা, একটি পুরোনো algorithm-এর প্রশ্ন সম্পর্কে শক্ত প্রমাণ দিল। Complexity-র বিভিন্ন শাখা এভাবে প্রায়ই অপ্রত্যাশিত জায়গায় মেলে।
মূল উপলব্ধি: একটি protocol private coin-এর ওপর নির্ভর করতে পারে, অথচ শ্রেণির স্তরে public coin একই শক্তি দেয়; GNI ∈ AM থেকে আসে যে GI NP-complete হলে PH ধসে পড়ত, যা GI-কে NP-intermediate প্রার্থী বানায়।
প্র ০৩IP = PSPACE কয়েক সপ্তাহের মধ্যে আবিষ্কৃত হয়, অথচ আগে অনেকে ভাবতেন coNP-রও interactive proof নেই। এই গল্প থেকে complexity-র অনুমান সম্পর্কে কী শেখা যায়?
১৯৮০-এর দশকের শেষে একটি জনপ্রিয় ধারণা ছিল: coNP-complete সমস্যার interactive proof থাকলে অদ্ভুত কিছু ঘটবে। এর পক্ষে একটি “প্রমাণও” ছিল: Fortnow আর Sipser ১৯৮৮ সালে দেখান, এমন একটি oracle আছে যার সামনে coNP-র interactive proof থাকে না। অর্থাৎ relativize করে এমন কোনো কৌশলে coNP ⊆ IP প্রমাণ করা যাবে না।
তারপর ১৯৮৯ সালের শেষে Noam Nisan একটি ধারণা e-mail-এ ছড়ান বলে জানা যায়, যা Lund, Fortnow আর Karloff-এর সঙ্গে দ্রুত একটি ফলে রূপ নেয়: permanent আর #SAT-এর মতো গোনার সমস্যার interactive proof আছে, তাই coNP ⊆ IP, এমনকি পুরো polynomial hierarchy IP-তে। কয়েক সপ্তাহের মধ্যে Adi Shamir দেখান IP = PSPACE. Babai এই ঘটনাপ্রবাহ নিয়ে “E-mail and the unexpected power of interaction” নামে একটি প্রবন্ধ লেখেন বলে জানা যায়। মূল কৌশল arithmetization: Boolean সূত্রকে polynomial বানিয়ে বড় field-এ নিয়ে যাওয়া, যা oracle-এর সঙ্গে খাপ খায় না, আর এ কারণেই relativization-এর বাধা পেরোনো গেল।
শিক্ষা তিনটি। প্রথম, oracle-ভিত্তিক বাধা মানে “অসম্ভব” নয়, বরং “এই ধরনের কৌশলে অসম্ভব”। দ্বিতীয়, বিশেষজ্ঞদের অনুমানও ভুল হয়; NL = coNL (১৯৮৭–৮৮) আরেকটি উদাহরণ। তাই P ≠ NP-র মতো অনুমানকে প্রমাণিত সত্যের মতো লেখা চলে না। তৃতীয়, নতুন কৌশলেরও সীমা আছে: ২০০৮ সালে Aaronson আর Wigderson দেখান, arithmetization-জাতীয় কৌশল একটি দুর্বলতর অর্থে relativize করে (algebrization), আর এমন কৌশল একা P বনাম NP মীমাংসা করতে পারবে না।
এই ফলের ব্যবহারিক উত্তরসূরিও আছে। Sum-check আর তার বংশধরেরা এখন “verifiable computation”-এর গবেষণার কেন্দ্রে: একটি দুর্বল যন্ত্র কীভাবে একটি শক্তিশালী সার্ভারের বিশাল গণনার ফল কম খরচে যাচাই করবে।
মূল উপলব্ধি: IP = PSPACE দেখায় যে relativization-এর বাধা একটি কৌশলের সীমা, সত্যের সীমা নয়; বিশেষজ্ঞদের প্রবল অনুমানও উল্টে যেতে পারে, তাই খোলা প্রশ্নকে খোলা বলেই লিখতে হয়।
প্র ০৪“Verifier কিছুই শেখেনি” কথাটি simulator দিয়ে সংজ্ঞায়িত। কিন্তু verifier তো দেখেছে যে দাবিটি সত্য! তাহলে “শূন্য জ্ঞান” আসলে কী মাপে, আর এর সীমা কোথায়?
Simulator-সংজ্ঞা শুধু w ∈ A-র ক্ষেত্রে খাটে। অর্থাৎ ধরে নেওয়া হয় দাবিটি সত্য, আর প্রশ্ন হলো: সেটুকুর বাইরে verifier কিছু পেল কি না। “দাবি সত্য” তথ্যটি zero knowledge-এর হিসাবের বাইরে, আর সেটি দেওয়াই প্রমাণের উদ্দেশ্য। Simulator যা দেখায়, তা হলো: verifier কথোপকথন থেকে যা কিছু polynomial সময়ে বের করতে পারত (যেমন σ-এর কোনো অংশ, বা একটি পরিকল্পনার slot), তা সে simulator চালিয়েই বের করতে পারত, prover ছাড়া।
সংজ্ঞায় “প্রতিটি verifier-কৌশল V*” খুব গুরুত্বপূর্ণ। সৎ verifier এলোমেলো প্রশ্ন করে, কিন্তু একজন অসৎ verifier প্রশ্ন বাছতে পারে H দেখে, যেমন H-এর hash থেকে। Honest-verifier zero knowledge এমন verifier-এর বিরুদ্ধে কিছু নিশ্চিত করে না। আরেকটি সূক্ষ্মতা: zero-knowledge protocol সমান্তরালে (parallel) চালালে zero knowledge-এর গুণ সাধারণভাবে রক্ষা পায় বলে প্রমাণ জানা নেই; Goldreich আর Krawczyk ১৯৯০ সালের দিকে এ নিয়ে নেতিবাচক ফল দেন বলে পরিচিত। তাই ভুল কমাতে round বাড়ানো হয় পরপর (sequential).
একটি চমকপ্রদ পরিণতি deniability: transcript তৃতীয় কাউকে দেখিয়ে লাভ নেই, কারণ verifier নিজেই simulator চালিয়ে হুবহু এমন transcript বানাতে পারত। Fiat–Shamir এই গুণ ইচ্ছা করে ভাঙে, যাতে প্রমাণ সবাইকে দেখানো যায়; তখন প্রমাণটি একটি digital signature-এর মতো আচরণ করে, আর Schnorr signature ঠিক এভাবে identification protocol থেকে আসে।
সীমাও আছে। Zero knowledge কথোপকথন নিয়ে কথা বলে, পুরো system নিয়ে নয়: সময় মাপা, ত্রুটি-বার্তা, দুর্বল এলোমেলো সংখ্যা বা ভুল hash-input থেকে গোপন তথ্য ফাঁস হতে পারে। আবার NP-র সাধারণ ZK protocol computational, অর্থাৎ one-way function-এর অনুমানের ওপর দাঁড়িয়ে। আর statistical zero knowledge-এ NP-complete সমস্যার প্রমাণ থাকলে polynomial hierarchy ধসে পড়ে বলে জানা যায় (Fortnow, Aiello–Håstad-এর কাজ), তাই সেখানে অনুমান এড়ানো কঠিন।
মূল উপলব্ধি: Zero knowledge মাপে “দাবি সত্য” তথ্যের বাইরে কী ফাঁস হলো; simulator প্রতিটি verifier-কৌশলের জন্য থাকতে হয়, আর গুণটি কথোপকথনের, পুরো system-এর নয়, তাই implementation আর অনুমান আলাদাভাবে যাচাই করতে হয়।
প্র ০৫একটি interactive proof-এর শেষে ভুলের সম্ভাবনা 2−100. গণিতের প্রথাগত প্রমাণের সঙ্গে তুলনায় এটি কি “প্রমাণ”? গণিতজ্ঞ আর কম্পিউটার বিজ্ঞানীরা এই প্রশ্ন কীভাবে দেখেন?
প্রথাগত গণিতে প্রমাণ একটি লেখা, যা যে কেউ যেকোনো সময় ধাপে ধাপে মিলিয়ে দেখতে পারে; তার নিশ্চয়তা শর্তহীন। Interactive proof দুইভাবে আলাদা। প্রথমত, নিশ্চয়তা সম্ভাবনাভিত্তিক: 2−100 সম্ভাবনায় ভুল থেকে যেতে পারে। দ্বিতীয়ত, প্রমাণটি একটি ঘটনা, লেখা নয়: আস্থা পায় শুধু সেই verifier, যার মুদ্রা গোপন ছিল। Transcript পরে অন্য কাউকে দেখালে তার কাছে তা অর্থহীন, কারণ এমন transcript সাজিয়েও বানানো যায়।
প্রথম আপত্তির উত্তরে অনেকে বলেন, 2−100 এত ছোট যে বাস্তবে প্রথাগত প্রমাণের চেয়েও নির্ভরযোগ্য হতে পারে: মানুষের লেখা দীর্ঘ প্রমাণে ভুল থাকার ঘটনা গণিতের ইতিহাসে বিরল নয়, আর computer hardware-এর এলোমেলো ত্রুটির সম্ভাবনাও এর চেয়ে বেশি বলে যুক্তি দেওয়া হয়। Miller–Rabin দিয়ে বড় মৌলিক সংখ্যা বাছাইয়ের সময় (পর্ব ৬৯) cryptography এই যুক্তিই মেনে চলে। তবে এর জন্য দরকার সত্যিকারের এলোমেলো, prover-এর কাছে অজানা মুদ্রা।
দ্বিতীয় আপত্তির উত্তর এসেছে PCP তত্ত্ব থেকে। সেখানে প্রমাণ আবার একটি লেখা, তবে বিশেষভাবে সাজানো, যাতে verifier এলোমেলো কয়েকটি জায়গা পড়েই উচ্চ সম্ভাবনায় সঠিকতা বুঝতে পারে। PCP উপপাদ্য বলে, NP-র প্রতিটি দাবির এমন লেখা আছে, যার মাত্র ধ্রুবক-সংখ্যক bit পড়লেই চলে (পর্ব ৭১-এর বিষয়)। এর শিকড় multi-prover protocol-এ: দুজন আলাদা prover-কে জেরা করা আর একটি স্থির লেখাকে এলোমেলো জায়গায় পড়া প্রায় একই কাজ।
গণিতের নিজের জগতেও পরিবর্তন এসেছে। চার রঙের উপপাদ্যের মতো computer-সহায়িত প্রমাণ, আর Lean বা Coq-এর মতো proof assistant-এ যাচাই-করা প্রমাণ দেখায় যে “প্রমাণ”-এর অর্থ সময়ের সঙ্গে বদলায়। Interactive proof সেই বিবর্তনের একটি তাত্ত্বিক প্রান্ত: প্রমাণ মানে verifier-এর মনে যুক্তিসঙ্গত আস্থা তৈরি করা, যার খরচ আর নিশ্চয়তা দুটিই মাপা যায়।
মূল উপলব্ধি: Interactive proof-এর নিশ্চয়তা সম্ভাবনাভিত্তিক আর verifier-নির্দিষ্ট; ভুলের সীমা প্রথাগত প্রমাণের বাস্তব ঝুঁকির চেয়েও ছোট হতে পারে, আর PCP তত্ত্ব আবার প্রমাণকে এমন লেখায় ফিরিয়ে আনে, যা এলোমেলো স্থানে পড়ে যাচাই করা যায়।
অনুশীলন
আগে কাগজে করুন, তারপর উত্তর মেলান। gni_protocol.py আর sum_check.py বদলে নিজের graph বা সূত্র দিয়েও যাচাই করতে পারেন।
-
নকশা: বাজারঘরের তিনটি গুদামের রাস্তার নকশা তিনটি graph G0, G1, G2. একজন পরামর্শক দাবি করেন তিনটি পরস্পর non-isomorphic. GNI-এর ধাঁচে একটি protocol নকশা করুন। Completeness কত? দাবি মিথ্যা হলে (অন্তত দুটি isomorphic) একটি round-এ প্রতারকের সবচেয়ে বেশি সাফল্য কত? প্রতারণার সম্ভাবনা ≤ 0.01 করতে কত round লাগে?
Protocol: V গোপনে i ∈ {0, 1, 2} আর এলোমেলো π বেছে H = π(Gi) পাঠায়; P একটি i′ বলে; i′ ≠ i হলে reject. তিনটি পরস্পর আলাদা হলে H ঠিক একটির isomorphic, তাই সৎ prover সবসময় ঠিক: completeness 1.
Soundness: সবচেয়ে খারাপ ক্ষেত্র ঠিক দুটি isomorphic, ধরুন G0 ≅ G1 ≇ G2. i = 2 হলে prover নিশ্চিত বলতে পারে (সম্ভাবনা ১/৩); i ∈ {0, 1} হলে H থেকে 0 আর 1 আলাদা করা যায় না, তাই সাফল্য ১/২. মোট 1/3 + (2/3)(1/2) = 2/3. তিনটিই isomorphic হলে সাফল্য মাত্র 1/3. তাই প্রতি round-এ সীমা 2/3, আর (2/3)k ≤ 0.01 থেকে k ≥ ln 100 / ln 1.5 ≈ 11.4, অর্থাৎ k = 12. ((2/3)11 ≈ 0.0116, (2/3)12 ≈ 0.0077.)
-
প্রমাণ: দেখান যে verifier deterministic হলে (মুদ্রা ছোড়ে না) এমন interactive proof-এ চেনা প্রতিটি language NP-তে। কোথায় soundness-এর সংজ্ঞা লাগে, স্পষ্ট করুন।
- V deterministic, তাই w আর prover-এর আগের বার্তাগুলো দিলে V-এর পরের বার্তা নির্ধারিত। পুরো কথোপকথন t = (p1, v1, p2, v2, …) polynomial দৈর্ঘ্যের। — সংজ্ঞা
- NP-র verifier N: “certificate t নিয়ে, প্রতিটি vi সত্যিই V(w, p1, …, pi)-এর সমান কি না মেলানো, আর শেষে V accept করে কি না দেখা।” এটি polynomial সময়। — V-কে ধাপে ধাপে চালানো
- w ∈ A: সৎ P-এর সঙ্গে V accept করে (deterministic বলে সম্ভাবনা 1, কারণ ≥ 2/3 মানে এখানে 1), তাই সেই কথোপকথনই একটি বৈধ t. — completeness
- w ∉ A: ধরুন N কোনো t গ্রহণ করে। তাহলে “t-এর বার্তাগুলো পাঠানো” কৌশলের prover P̃ V-কে সম্ভাবনা 1-এ accept করায়, যা soundness-এর সীমা ≤ 1/3-এর বিরোধী। তাই কোনো t গৃহীত হয় না। — soundness, “প্রতিটি prover” ∎
-
Trace: φ = x1 ∨ x2, field 𝔽7. (ক) φ̃ লিখুন আর #φ বের করুন। (খ) সৎ prover-এর g1(X) কী? যাচাইয়ের সমীকরণ মেলান। (গ) r1 = 4, r2 = 6 হলে বাকি কথোপকথন আর শেষ পরীক্ষা লিখুন। (ঘ) প্রতারক K = 4 দাবি করলে ধরা না পড়ার সম্ভাবনার সীমা কত?
(ক) φ̃ = x1 + x2 − x1x2; সমাধান 01, 10, 11, তাই #φ = 3. (খ) g1(X) = φ̃(X, 0) + φ̃(X, 1) = X + 1. যাচাই: g1(0) + g1(1) = 1 + 2 = 3 ✓.
(গ) নতুন দাবি g1(4) = 5. g2(X) = φ̃(4, X) = 4 + X − 4X = 4 − 3X; যাচাই 4 + 1 = 5 ✓. r2 = 6: দাবি 4 − 18 = −14 ≡ 0. শেষ পরীক্ষা: φ̃(4, 6) = 4 + 6 − 24 = −14 ≡ 0 ✓, accept. (ঘ) প্রতিটি চলকে degree 1, দুটি চলক: সীমা n · d/p = 2 · 1/7 = 2/7. Scratch script-এ সব সংখ্যা মিলিয়ে দেখা হয়েছে।
-
হিসাব: (ক) GNI protocol ১০ round চালালে প্রতারকের সাফল্যের সীমা কত? (খ) কাপ-protocol-এ ৯টি দ্বন্দ্ব আর একটিমাত্র ভুল দ্বন্দ্ব থাকলে প্রতারণা ≤ 2−20 করতে কত round? (গ) GI-এর zero-knowledge protocol-এর simulator k round-এর transcript বানাতে গড়ে কতবার চেষ্টা করে? (ঘ) Sum-check-এ n = 40 চলক, প্রতি চলকে degree 3, আর p = 261 − 1 হলে soundness-এর সীমা কত?
(ক) 2−10 = 1/1024 ≈ 0.00098. (খ) (8/9)k ≤ 2−20 ⇔ k ≥ 20 ln 2 / ln(9/8) ≈ 117.7, তাই k = 118; যাচাই: (8/9)117 ≈ 1.03 × 10−6, যা 2−20 ≈ 9.54 × 10−7-এর বেশি, আর (8/9)118 ≈ 9.2 × 10−7.
(গ) প্রতিটি round-এ সফলতা ১/২, তাই প্রত্যাশিত চেষ্টা ২টি; k round পরপর হলে প্রত্যাশিত মোট 2k চেষ্টা, যা polynomial. (ঘ) n · d/p = 120 / (261 − 1) ≈ 5.2 × 10−17.
নিজেকে যাচাই করুন
ভুল হলে কারণসহ ব্যাখ্যা পাবেন, আবার চেষ্টাও করতে পারবেন।
ক্রমGraph isomorphism-এর zero-knowledge protocol-এর ধাপগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)
- Prover একটি এলোমেলো permutation π বেছে H = π(G1) পাঠায়
- Verifier একটি এলোমেলো bit b পাঠায়
- Prover b = 1 হলে π, আর b = 0 হলে π ∘ σ পাঠায়
- Verifier মেলায় যে পাঠানো permutation Gb-কে H-এ নেয়
- পুরো round নতুন π আর b নিয়ে k বার পরপর চালানো হয়; সব পাস হলে accept
Class IP-র সংজ্ঞায় soundness শর্তটি কোনটি (w ∉ A)?
- সৎ prover কখনো মিথ্যা দাবি করে না
- এমন একটি prover আছে, যার সঙ্গে V অন্তত 2/3 সম্ভাবনায় reject করে
- প্রতিটি prover P̃-এর জন্য Pr[(V ↔ P̃)(w) accepts] ≤ 1/3
- Prover V-এর সব মুদ্রা দেখতে পায়, তবু ১/৩-এর বেশি জেতে না
Graph non-isomorphism-এর protocol-এ verifier গোপনে b ∈ {0, 1} আর এলোমেলো π বেছে H = π(Gb) পাঠায়, prover b′ বলে। G0 ≅ G1 হলে যেকোনো prover-এর এক round-এ সাফল্যের সম্ভাবনা কত?
- ঠিক 1/2
- 1, কারণ prover সর্বশক্তিমান
- 1/n!, কারণ π এলোমেলো
- 0
Interactive proof সম্পর্কে নিচের কোন বক্তব্যটি প্রমাণিত সত্য?
- IP = NP
- Graph isomorphism NP-complete
- IP ⊆ BPP
- IP = PSPACE
একটি interactive proof-কে zero-knowledge বলার শর্ত কোনটি?
- Verifier শেষে শুধু accept বা reject দেখে
- প্রতিটি polynomial সময়ের verifier-কৌশলের জন্য একটি simulator আছে, যে prover ছাড়াই একই বণ্টনের কথোপকথন বানায়
- Prover polynomial সময়ে চলে
- Soundness error শূন্য
Sum-check protocol-এ n চলকের একটি polynomial, প্রতিটি চলকে degree ≤ d, আকার p-এর একটি field-এ। মিথ্যা দাবিতে verifier accept করার সম্ভাবনার জানা সীমা কোনটি?
- 2−n
- 1/2, যেকোনো p-এ
- n · d / p
- dn / p
Verifier deterministic হলে (কোনো মুদ্রা নেই) interactive proof দিয়ে ঠিক কোন শ্রেণির language চেনা যায়?
- PSPACE
- NP
- P
- BPP
শব্দকোষ
লেখার মধ্যে ডটেড দাগ দেওয়া শব্দে মাউস রাখুন বা চাপুন, অর্থ দেখাবে। এই পর্বের সব নতুন শব্দ এখানে একসাথে:
মনে রাখুন
- IP: probabilistic polynomial সময়ের verifier আর সর্বশক্তিমান prover; সত্য দাবিতে কোনো prover ≥ 2/3, মিথ্যা দাবিতে প্রতিটি prover ≤ 1/3. NP ⊆ IP, BPP ⊆ IP, আর deterministic verifier-এ শুধু NP.
- GNI protocol: গোপন b আর π, H = π(Gb); আলাদা graph-এ সৎ prover সবসময় ঠিক, একই graph-এ যেকোনো prover ১/২; k round-এ 2−k.
- Arthur–Merlin-এ মুদ্রা প্রকাশ্য; Goldwasser–Sipser অনুযায়ী তবু একই শক্তি, GNI ∈ AM, আর GI NP-complete হলে PH দ্বিতীয় স্তরে ধসে পড়ত।
- Arithmetization আর sum-check (soundness ≤ n · d/p) থেকে coNP ⊆ IP, আর Shamir-এর কৌশলে IP = PSPACE; ফলটি relativization-এর বাধা পেরোয়।
- Zero knowledge: প্রতিটি verifier-কৌশলের জন্য simulator; GI-এর protocol perfect zero-knowledge, one-way function থাকলে সব NP-র জন্য computational ZK, আর বাস্তব ব্যবহার অনুমান ও implementation-এর ওপর নির্ভরশীল।
আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ
- পর্ব ৬৯ · Randomized complexity — RP, BPP আর ZPPফিরে দেখুনAmplification, Schwartz–Zippel আর fingerprinting, এই পর্বের সম্ভাবনার হিসাবের ভিত্তি।
- পর্ব ৬৫ · PSPACE-completeness — TQBF আর gameসংযোগTQBF আর দুই খেলোয়াড়ের খেলা, IP = PSPACE-এর অন্য দিক।
- গণনার তত্ত্ব · কোর্স হোম৮৫টি পর্ব১৪টি মডিউলের পুরো মানচিত্র; পরের পর্ব ৭৫-এ quantum computation আর BQP.
- ডিসক্রিট ম্যাথমেটিক্স · পর্ব ৫৮ — গ্রাফের representation আর isomorphismপাশের ট্র্যাকIsomorphism-এর সংজ্ঞা আর invariant দিয়ে graph আলাদা করা।
- সাইবারসিকিউরিটি · পর্ব ০৭ — Cryptography-র ভিত্তিপাশের ট্র্যাকগোপনীয়তা, অখণ্ডতা আর পরিচয়, আর নিজে crypto না বানানোর নীতি।