# Please do not post homework
# Aurora Hiveley, 04/18/24, Assignment 25

Help:= proc(): print(` VerifyOpt1(n,G,B1,B2), ZKP(n,G,pi,Opt), ZKP(n,G,pi,K) `): end:

with(combinat):


### problem 2 - modify ZKP

# 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))  
# outputs true if it is a faithful relabling of the graph G 
# otherwise false.
VerifyOpt1 := proc(n,G,B1,B2) local H,H2,i,j,edge:
H := {}: # initialize set of encoded edges of G using B1

for edge in G do 
  H := H union {{B1[edge[1]], B1[edge[2]]}}: # add encoded edge
od:

# build table from edges of H2 to compare to B2
for i from 1 to n do
 for j from i+1 to n do
   if member ({i,j},H) then
    H2[{i,j}]:=1:
   else
    H2[{i,j}]:=0:
   fi:
od:
od:

EqualEntries(H2,B2): # order in a table matters, so use EqualEntries instead of evalb()

end:



## modified ZKP1
ZKP2:=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:

# CHANGES WERE MADE BELOW THIS LINE
if Opt=1 then
  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 
    true:
  else
    false:
  fi:
fi:
end:




### problem 3 - ZKP

# uses ZKP2(n,G,pi,Opt) by having K rounds, and at each round, 
# picking Option 1 or Option 2 each with probability 1/2 
# returning true if and only if ZKP1(n,G,pi,Opt) always returns true.
ZKP := proc(n,G,pi,K) local i,Opt:

for i from 1 to K do
  if LD(1/2) then 
    Opt := 1:
  else
    Opt := 2:
  fi:

  if not ZKP2(n,G,pi,Opt) then 
    RETURN(false):
  fi:
od:

true:
end:






### COPIED FROM CLASS


#C25.txt: Zero-Knowledge Proofs. April 18, 2024
Help25:=proc(): print(`LD(p), RG(n,p), RHG(n,p), ZKP1(n,G,pi,Opt)`): end:
with(combinat):
#LD(p): inputs a pos. rational number from 0 to 1 and  outputs true with prob. p
LD:=proc(p) local i:i:=rand(1..denom(p))(): if i<=numer(p) then true:else false:fi:end:

#RG(n,p): inputs a pos. integer n and outputs a simple graph on n vertices where the
#prob of an edge is p (independetly)
RG:=proc(n,p) local i,j,G:
G:={}:
for i from 1 to n do
 for j from i+1 to n do
  if LD(p) then
    G:=G union {{i,j}}:
  fi:
 od:
od:
G:  
end:


#RHG(n,p): inputs a pos. integer n and outputs a simple  HAMILTONIAN graph on n vertices 
#where the
#prob of an edge is p (independetly) together with the Hamiltonian path
#The output is a pair [G,permutation] where the permutation of {1,...,n}
#is the Hamiltonian cycle that you know and you don't want anyone else to know
#BUT you do want to convince them that you DO know
RHG:=proc(n,p) local i,j,G,pi:
pi:=randperm(n):
G:={seq({pi[i],pi[i+1]},i=1..n-1), {pi[n],pi[1]}}:

for i from 1 to n do
 for j from i+1 to n do
  if LD(p) then
    G:=G union {{i,j}}:
  fi:
 od:
od:
[G, pi]:  
end:

#ZKP1(n,G,pi,Opt): Does ONE ROUND of the Blum protocol. Inputs a graph n,G,
#a Hamiltonian pi, and Opt=1 or 2 Opt=1 you show all the n+binomial(n,2) boxes
#Opt2, you show the contents of the n boxes correponsing to the mapping of
#your Hamiltonian
ZKP1:=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
 [op(B1),op(B2)]:
else
 {seq(B2[{sig[pi[i]],sig[pi[i+1]]}],i=1..n-1),B2[{sig[pi[n]],sig[pi[1]]}]}:
fi:
end: