#March 28, 12:00noon-1:20pm 2013 Zero-Knowledge proofs

Help:=proc(): print(`RandHG(n,p) , OneStep(G,pi) `):
print(`VerifyOneStep(G,i,MrNakamura) `):

end:

with(combinat):

#RandHG(n,p), inputs a pos. integer n and a rational number
#p and outputs a graph on n vertices that has a Hamiltionian
#cycle, and the remaining edges are chosen independently
#with prob. p
RandHG:=proc(n,p) local pi,G, roullete,i,j, justin:
pi:=randperm(n):

roullete:=rand(1..denom(p)):
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
   justin:=roullete():
     if justin<=numer(p) then
        G:=G union { {i,j}}:
     fi:
  od:
od:

G,pi:
end:


#Options(G,pi,sig): Given a Hamil. graph G
#and a proof of its Ham. pi (n=nops(pi)) and
#a permutation sig, prepare both options
#either show your enemy the image of the graph
#under sig, OR, show the Hamiltonian cycle
Options:=proc(G,pi,sig) local G1,pi1,i,n,H:
n:=nops(pi):
G1:=subs({seq(i=sig[i],i=1..n)},G):
H:=subs({seq(i=sig[i],i=1..n)},pi):
[G1,sig,H]:
end:



OneStep:=proc(G,pi) local n,coin,sig,tomas:
n:=nops(pi):
sig:=randperm(n):
tomas:=Options(G,pi,sig):

coin:=rand(1..2)():

if coin=1 then
 RETURN(1,[op(1..2,tomas)]):
else
 RETURN(2,[tomas[1],tomas[3]]):
fi:
end:



VerifyOneStep:=proc(G,i,MrNakamura)  local G1,sig,G1a,H,t,n:
n:=nops(MrNakamura[2]):
if i=1 then 
 G1:=MrNakamura[1]:
 sig:=MrNakamura[2]:
 G1a:=subs({seq(i=sig[i],i=1..n)},G):

  RETURN(evalb(G1=G1a)):
else
 G1:=MrNakamura[1]:
 H:=MrNakamura[2]:
 n:=nops(H):
evalb({seq({H[t],H[t+1]},t=1..n-1),{H[n],H[1]}} minus G1 ={}):
fi:

end: