#GLORIA LIU, Apr 20 2024, Assignment 25

read `C25.txt`:

#=====================================#
#1. Read and understand Manuel Blum's article on Zero-Knowledge proofs and Hadas Zeilberger's 
#engaging explanation of Zero-Knowledge proofs in plain English
#Done

#=====================================#
#2. Write a procedure
#VerifyOpt1(n,G,B1,B2)
#that inputs a positive integer n, a graph (set of edges) G, and tables B1 (of size n) and B2 (of 
#size binomial(n,2)) and outputs true if it is a faithful relabling of the graph G, otherwise false.
#Having done that Modify procedure ZKP1(n,G,pi,Opt) to return true or false, as follows:
#If it is Option 1, then it returns VerifyOpt1(n,G,B1,B2)
#If it is Option 2, then it returns true if you get {1}, otherwise it returns false.

VerifyOpt1:=proc(n,G,B1,B2) local box,n1,B1I,ind,val,i:
for ind,val in eval(B1) do
 B1I[val]:=ind:
od:
for ind,val in eval(B1I) do
 box:=val:
 n1:=ind:
 for i from n1+1 to n do
  if member({n1, i}, G) then
   if B2[{box, B1I[i]}]=0 then
    RETURN(false):
   fi:
  else
   if B2[{box, B1I[i]}]=1 then
    RETURN(false):
   fi:
  fi:
 od:
od:
true:
end:

ZKP1Mod:=proc(n,G,pi,Opt) local B1,B2,i,j,sig:
sig:=randperm(n):
for i from 1 to n do
 B1[i]:=sig[i]:
od:

for i from 1 to n do
 for j from i+1 to n do
   if member ({i,j},G) then
     B2[{sig[i],sig[j]}]:=1:
   else
    B2[{sig[i],sig[j]}]:=0:
   fi:
od:
od:

if Opt=1 then
 RETURN(VerifyOpt1(n,G,B1,B2)):
else
 if {seq(B2[{sig[pi[i]],sig[pi[i+1]]}],i=1..n-1),B2[{sig[pi[n]],sig[pi[1]]}]}={1} then
  RETURN(true):
 else
  RETURN(false):
 fi:
fi:
end:

#=====================================#
#3. Write a procedure
#ZKP(n,G,pi,K)
#that uses (the modified) ZKP1(n,G,pi,Opt) by having K rounds, and at each round, picking Option 1 or 
#Option 2 each with probability 1/2 and returning true if and only if ZKP1(m,G,pi,Opt) always returns 
#true.

ZKP:=proc(n,G,pi,K) local i,ra:
ra:=rand(1..2):
for i from 1 to K do
 if ra():=1 then
  if not ZKP1Mod(n,G,pi,1) then
   RETURN(false):
  fi:
 else
  if not ZKP1Mod*n,G,pi,2) then
   RETURN(false):
  fi:
 fi:
od:
true:
end:

#=====================================#
#4. Write a procedure
#R3CG(n,p)
#Skipped