##ZeroKnowledgeProof.txt: Save this file as ZeroKnowledgeProof.txt   #
## To use it, stay in the                                            #
##same directory, get into Maple (by typing: maple <Enter> )         #
##and then type:  read  ZeroKnowledgeProof.txt<Enter>                #
##Then follow the instructions given there                           #
##                                                                   #
##Written by Doron Zeilberger, Rutgers University ,                  #
#DoronZeil at gmail dot com                                          #
######################################################################
 
#Created: Oct. 3, 2019
 
print(`Created:  Oct. 3,2019`):
print(` This is ZeroKnowledgeProof.txtt `):
print(`It is a Maple implementation of Manuel Blum's seminal article `):
print(``):
print(`How to Prove a Theorem so that no one can claim it`):
print(` Proceedings of the International Congress of Mathematicians, Berkely, California, USA, 1986`):
print(`pages 1444-1451. Available (viewed Sept. 29, 2019) from `):
print(`http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.469.9048&rep=rep1&type=pdf`):
print(``):
print(`Please report bugs of this Maple package to DoronZeil at gmail dot com `):
print(``):
 print(`The most current version of this  package `):
 print(` is  available from`):
 print(`http://sites.math.rutgers.edu/~zeilberg/  .`):

print(`---------------------------------------`):
 print(`For a list of the Supporting procedures type ezra1();, for help with`):
 print(`a specific procedure, type ezra(procedure_name);   .`):
 print(``):
print(`---------------------------------------`):

print(`---------------------------------------`):
 print(`For a list of the MAIN procedures that apply to both the Hamiltonian cycle problem and the 3-Coloring problem`):
  print(`Type ezra(); `):
 print(`a help with a specific procedure, type ezra(procedure_name);   .`):
 print(``):
print(`---------------------------------------`):

print(`---------------------------------------`):
 print(`For a list of the MAIN procedures about the Hamiltoniam Path problem, type ezraH();, for help with`):
 print(`a specific procedure, type ezra(procedure_name);   .`):
 print(``):
print(`---------------------------------------`):

print(`---------------------------------------`):
 print(`For a list of the MAIN procedures about the 3-Coloring problem, type ezraC();, for help with`):
 print(`a specific procedure, type ezra(procedure_name);   .`):
 print(``):
print(`---------------------------------------`):

with(combinat):

ezra1:=proc()

if args=NULL then
 print(` The supporting procedures are: CheckEnH, CheckHC, FindH,  GwFakeH, KufN `):
 print(``):

else
ezra(args):
fi:

end:

ezraC:=proc()

if args=NULL then
 print(` The  procedures about the 3-Coloing problem are: CheatC,CheatCs,  Check3C, CheckEnC, Find3C, GwC, MakeBoxesC, ManyCheatCs, ZKPC  `):
 print(``):

else
ezra(args):
fi:

end:

ezraH:=proc()

if args=NULL then
 print(` The  procedures about the Hamiltonain cycle problem are: CheatH, CheatHs, GwH, MakeBoxesH, ManyCheatHs, ZKPH,`):
 print(``):

else
ezra(args):
fi:

end:

ezra:=proc()

if args=NULL then
 print(`The main procedures are:  RaG, `):
 print(` `):


elif nops([args])=1 and op(1,[args])=CheatC then
print(`CheatC(G,N,k): Inputs a graph G on N vertices,  picks a random coloring, not necessarily proper`):
print(`and claims that he has a 3-Coloring C, he gives the verifer a choice.`):
print(`The Zero-Knowlege proof protocol hopefully should fail unless the prover found a proper coloring. Try`):
print(`G:=RaG(20,1/2); CheatC(G,20,10);`):

elif nops([args])=1 and op(1,[args])=CheatCs then
print(`CheatCs(G,N,k):  a silent version of CheatC(G,N,k). Only returns false,NumberOfRounds. Try:`):
print(`G:=RaG(20,1/2); CheatC(G,20,10);`):

elif nops([args])=1 and op(1,[args])=CheatH then
print(`CheatH(G,N,k): Like ZKPH(G,P,k) but where the prover does not have a Hamiltonian path, so he makes one up, and hopes for the best.Try`):
print(`G is a graph with N vertices`):
print(`G:=RaG(10,1/2): CheatH(G,10,10);`):

elif nops([args])=1 and op(1,[args])=CheatHs then
print(`CheatHs(G,N,k): Like CheatH(G,P,k)(q.v.), but quite, reutrns the number of steps until found out. Try:`):
print(`G:=RaG(20,1/2): CheatHs(G,20,20);`):


elif nops([args])=1 and op(1,[args])=Check3C then
print(`Check3C(G,C): Given a graph G om N vertices and a coloring C (with colors C) checks that it is a proper coloring.`):
print(`Try:`):
print(`Check3C({{1,2},{1,3},{2,3}},[1,2,3]);`):

elif nops([args])=1 and op(1,[args])=CheckEnC then
print(`CheckEnC(G,N,B1v,B2): Given a graph G on N vertices, an encoding of the vertices, B1v, and a B2 box, checks that the`):
print(`encoding is OK. Try:`):
print(`gu:=MakeBoxesC({{1,2},{1,3}},[1,2,3]); mu:=CheckEnC({{1,2},{1,3}},3,gu[2],gu[3]);`):
print(`lu:=GwC(10,1/2): gu:=MakeBoxesC(lu):CheckEnC(lu[1],10,gu[2],gu[3]); `):

elif nops([args])=1 and op(1,[args])=CheckEnH then
print(`CheckEnH(G,B1,B2): Given a graph G and a Hamiltnian cycle P, the prover makes boxes. Try:`):
print(`gu:=GwH(20,1/2);mu:=MakeBoxesH(gu); CheckEnH(gu[1],mu[1],mu[2]);`):

elif nops([args])=1 and op(1,[args])=CheckHC then
print(`CheckHC(P): Given an encoded Hamiltonian cycle, checks that it is OK. Try: `):
print(`gu:=GwH(20,1/2);P:=MakeBoxesH(gu)[3]; CheckHC(P);`):


elif nops([args])=1 and op(1,[args])=Find3C then
print(`Find3C(N,G): inputs a graph G on N vertices, finds a 3-coloring, or returns FAIL. Try`):
print(`Find3C(4,{{1,2},{1,3},{1,4}});`):


elif nops([args])=1 and op(1,[args])=FindH then
print(`FindH(G,N): Given a graph on N vertices, finds a Hamiltionian cycle by brute force`):

elif nops([args])=1 and op(1,[args])=GwFakeEn then
print(`GwFakeEn(N,p): Outputs a random graph with N vertices (prob. of an edge p), with a good-looking Hamilotian path`):
print(`but with false encoding`):
print(`GwFakeEn(20,1/2); `):

elif nops([args])=1 and op(1,[args])=GwFakeH then
print(`GwFakeH(N,p): A random graph with a Fake Hamiltonian cycle. Try:`):
print(`GwFakeH(10,1/2);`):

elif nops([args])=1 and op(1,[args])=GwC then
print(`GwC(N,eps): A random graph on N vertices with density eps (a rational number) together with a`):
print(`known coloring. The output is [G,C] where C is the coloring. It startw with  a coloring`):
print(`C and then constructs a random graph for which it is a legal coloring. Try:`):
print(`GwC(8,1/2);`):

elif nops([args])=1 and op(1,[args])=GwH then
print(`GwH(N,p): A random graph with N vertices, that has a Hamiltonian cycle and prob. of an edge p, followed by the Hamiltonian cycle. Try:`):
print(`GwH(30,1/2);`):

elif nops([args])=1 and op(1,[args])=KufN then
print(`KufN(N): {0,1,2}^N. Try:`):
print(`KufN(5);`):

elif nops([args])=1 and op(1,[args])=MakeBoxesC then
print(`MakeBoxesC(G,C): Given a graph G and a 3-Coloring C (with colors 1,2,3), the prover makes boxes. Try:`):
print(`MakeBoxesC({{1,2},{1,3},{2,3}},[1,2,3]);`):
print(`gu:=GwC(10,1/2):MakeBoxesC(gu);`):

elif nops([args])=1 and op(1,[args])=MakeBoxesH then
print(`MakeBoxesH(G,P): Given a graph G and a Hamiltnian cycle P, the prover makes boxes. Try:`):
print(`gu:=GwH(20,1/2);MakeBoxesH(gu); `):

elif nops([args])=1 and op(1,[args])=ManyCheatCs then
print(`ManyCheatCs(N,eps,K);`):
print(`Simulates CheatCs for graphs with N vertices and density eps K times, returns the list whose i-th entry is`):
print(` the number of times the cheater was found out at the i-th round. Try:`):
print(`ManyCheatCs(20,1/2,64);`):

elif nops([args])=1 and op(1,[args])=ManyCheatHs then
print(`ManyCheatHs(N,eps,K);`):
print(`Simulates CheatHs for graphs with N vertices and density eps K times, returns the list whose i-th entry is`):
print(` the number of times the cheater was found out at the i-th round. Try:`):
print(`ManyCheatHs(20,1/2,64);`):


elif nops([args])=1 and op(1,[args])=RaG then
print(`RaG(N,p): A random graph on {1, ..., N} with prob. of an edge being p. Try:`):
print(` RaG(30,2/3); `):

elif nops([args])=1 and op(1,[args])=ZKPC then
print(`ZKPC(G,C,k): A prover shows a graph and claims that he has a 3-Coloring C, he gives the verifer a choice.`):
print(`The Zero-Knowlege proof protocol for convincing the verifier that the prover knows the 3-coloring w/o revealing it. Try:`):
print(`ZKPC({{1,2},{1,3},{2,3}},[1,2,3],10);`):
print(`gu:=GwC(20,1/2): ZKPC(gu,10):`):

elif nops([args])=1 and op(1,[args])=ZKPH then
print(`ZKPH(G,P,k): The Zero-Knowlege protocol for the existence of a Hamiltonian path in the graph G, where P is the Hamiltonian path`):
print(`done k times . Try`):
print(`gu:=GwH(10,1/2): ZKPH(gu,10);`):



else
print(`There is no ezra for`,args):
fi:
 
end:

with(combinat):


#RaG(N,p): A random graph on {1, ..., N} with prob. of an edge being p
RaG:=proc(N,p) local m,n,ra,gu,i,j,ka:

if not type(p,fraction) then
  RETURN(FAIL):
fi:

m:=numer(p): n:=denom(p):
ra:=rand(1..n):

gu:={}:

for i from 1 to N do
 for j from i+1 to N do
   ka:=ra():
    if ka<=m then
       gu:=gu union {{i,j}}:
    fi:
 od:
od:

gu:

end:


#FindH(G,N): Given a graph on N vertices, finds a Hamiltionian cycle by brute force
FindH:=proc(G,N) local gu,pi,i1:
gu:=permute(N):

for pi in gu do
 if {seq({pi[i1],pi[i1+1]},i1=1..N-1),{pi[N],pi[1]}} minus G={} then
   RETURN(pi):
 fi:
od:

false:

end:

#GwH(N,p): A random graph with a Hamiltonian cycle
GwH:=proc(N,p) local G,pi,i:
pi:=randperm(N):

G:={seq({pi[i],pi[i+1]},i=1..N-1), {pi[N],pi[1]}}:
G:=G union RaG(N,p):
G, [seq({pi[i],pi[i+1]},i=1..N-1), {pi[N],pi[1]}]:
end:


#MakeBoxesH(G,P): Given a graph G and a Hamiltnian cycle P, the prover makes boxes. Try:
#gu:=GwH(20,1/2);MakeBoxesH(gu):
MakeBoxesH:=proc(G,P) local N,B1,B2,i,j,P1,i1:
N:=nops(P):
B1:=randperm(N):

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


P1:=[seq({B1[P[i1][1]],B1[P[i1][2]]} , i1=1..N)]:

B1,op(B2),P1:
end:

#CheckHC(P): Given an encoded Hamiltonian cycle, checks that it is OK. Try: 
#gu:=GwH(20,1/2);P:=MakeBoxesH(gu)[3]; CheckHC(P);
CheckHC:=proc(P) local N,i1:
N:=nops(P):
if {seq(P[i1][2],i1=1..N)}<>{1} then
 print(`Liar!, not all boxes are filled with 1, I refuse to believe you.`):
  RETURN(false):
fi:

if {seq( nops(P[i1][1] intersect P[i1+1][1]),i1=1..N-1)}<>{1} then
 print(`Liar!, it is not a cycle! , I refuse to believe you.`):
  RETURN(false):
fi:

if {seq( op(P[i1][1]), i1=1..N)}<>{seq(i1,i1=1..N)} then
 print(`Liar!, it is not a Hamiltonian cycle! It does not visit all the `, N, `vertices. I refuse to believe you.`):
  RETURN(false):
fi:
true:
end:



#CheckEnH(G,B1,B2): Given a graph G and a Hamiltnian cycle P, the prover makes boxes. Try:
#gu:=GwH(20,1/2);mu:=MakeBoxesH(gu); CheckEnH(gu[1],mu[1],mu[2]);

CheckEnH:=proc(G,B1,B2) local N,i,j:

N:=nops(B1):
for i from 1 to N do
 for j from i+1 to N do

    if member({i,j},G)  and     B2[{B1[i],B1[j]}]=0 then
     print(`Liar!, vertex `, i , `goes to `, B1[i], `vertex `, j, `goes to `, B1[j] ):
     print(`There is an edge in your graph between vertex`, i, `and vertex `, j):
     print(``):
    print (` yet the value of`, {B1[i],B1[j]}, ` in the B2 table is `, 0):
   RETURN(false):
    fi:

   if not member({i,j},G)  and     B2[{B1[i],B1[j]}]=1 then
     print(`Liar!, vertex `, i , `goes to `, B1[i], `vertex `, j, `goes to `, B1[j] ):
     print(`There is no edge in your graph between vertex`, i, `and vertex `, j):
     print(``):
    print (` yet the value of`, {B1[i],B1[j]}, ` in the B2 table is `, 1):

    RETURN(false):
    fi:


 od:
od:

true:
end:

#CheckEnHs(G,B1,B2): Given a graph G and a Hamiltnian cycle P, the prover makes boxes. Try:
#gu:=GwH(20,1/2);mu:=MakeBoxesH(gu); CheckEnHs(gu[1],mu[1],mu[2]);

CheckEnHs:=proc(G,B1,B2) local N,i,j:

N:=nops(B1):
for i from 1 to N do
 for j from i+1 to N do

    if member({i,j},G)  and     B2[{B1[i],B1[j]}]=0 then
   RETURN(false):
    fi:

   if not member({i,j},G)  and     B2[{B1[i],B1[j]}]=1 then
    RETURN(false):
    fi:


 od:
od:

true:
end:



#ZKPH(G,P,k): A prover shows a graph and claims that he has a Hamiltonian cycle, he gives the verifer a choice. Try:
#gu:=GwH(20,1/2): ZKPH(gu,8):
ZKPH:=proc(G,P,k) local ra,gu,N,i,d,gu3,B2,i1:
N:=nops(P):

ra:=rand(1..2):

print(`Dear Verifier. Conisider the following graph on`, N, `vertices labelled 1,...`, N, `given as a set of its edges `):
print(``):
print(G):
print(``):

print(`I know a Hamiltonian cycle on that graph, but there is no way that I would tell you this. But I want to convince you that I am not lying`):
print(``): 
print(`You have`, k, `rounds  to be convinced that I am not lying`):

for i from 1 to k do
gu:=MakeBoxesH(G,P):
B2:=gu[2]:
print(`This is round number`, i, ` I have encoded the graph with a random permutation. Do you want to see the encoded graph`):
print(`or do you want to see the encoded Hamiltonian cycle?`):

d:=ra():

if d=1 then
 print(`Verifier: I decided to see the encoded graph`):
 print(``):
 print(`Prover: here it is, go ahead and check that it is OK`):
 print(``):
 print(gu[1],gu[2]):
 if not CheckEnH(G,gu[1],gu[2]) then
   print(`Verifer: Liar!. I refuse to accept it.`):
  RETURN(FAIL):
  else
   print(`Verifier: Looks, OK`):
 fi:

else
 print(`Verifier: I decided to see the encoded Hamiltonian cycle`):
 print(``):
 print(`Prover: Here it is, go ahead and check that it is indeed a cycle through all the vertices`):
  gu3:=gu[3]:
   print(gu3):
 print(`and here are the contents of the B2 boxes. Go and check that they all contain 1, as they should. `):
   
print([seq( B2[ gu3[i1]  ], i1=1..N)]):

 

 if not  {seq( B2[ gu3[i1]] , i1=1..N)}={1} then
  print(`Verifer: Liar!. They are not all 1s`):
  RETURN(FAIL):
  else
   print(`Verifier: Looks, OK`):
 fi:

fi:

od:

print(`Prover: I hope that you are convinced that I do know a Hamiltonian cycle, even though you have no clue what it is. `):
print(``):
print(`----------------------------`):
print(``):
RETURN(true):

end:




#GwFakeH(N,p): A random graph with a Fake Hamiltonian cycle. Try:
#GwFakeH(10,1/2);
GwFakeH:=proc(N,p) local G,pi,i:
pi:=randperm(N):
G:=RaG(N,p):
G, [seq({pi[i],pi[i+1]},i=1..N-1), {pi[N],pi[1]}]:
end:


#GwFakeEn(N,p): Outputs a random graph with N vertices (prob. of an edge p), with a good-looking Hamilotian path
#but with false encoding
#GwFakeEn(20,1/2):OA
GwFakeEn:=proc(N,p) local G,P,B1,B2,i,j,P1,i1:
G:=RaG(N,p):
B1:=randperm(N):

P:=randperm(N):
P:=[seq({P[i1],P[i1+1]},i1=1..N-1),{P[N],P[1]}]:

P1:=[seq([{B1[P[i1][1]],B1[P[i1][2]]}, 1 ], i1=1..N)]:

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

for i1 from 1 to N do
 B2[{B1[P1[i1][1][1]],B1[P1[i1][1][2]]}]:=1:
od:

B1,op(B2),P1:
end:

#CheatH(G,N,k): Like ZKPH(G,P,k) but where the prover does not have a Hamiltonian path, so he makes one up, and hopes for the best.Try
#G is a graph with N vertices
#G:=RaG(20,1/2): CheatH(G,20,4):
CheatH:=proc(G,N,k) local pi,gu,i,d,P,e,i1,B2,gu3:

pi:=randperm(N):
P:=[seq({pi[i],pi[i+1]},i=1..N-1), {pi[N],pi[1]}]:

print(`Dear Verifier. Conisider the following graph on`, N, `vertices labelled 1,...`, N, `given as a set of its edges `):
print(``):
print(G):
print(``):

print(`I know a Hamiltonian cycle on that graph, but there is no way that I would tell you this. But I want to convince you that I am not lying`):
print(``): 
print(`You have`, k, `rounds  to be convinced that I am not lying`):

for i from 1 to k do

gu:=MakeBoxesH(G,P):

gu3:=gu[3]:
B2:=gu[2]:

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

if e=1 then

for i1  from 1 to nops(gu3) do
 B2[gu3[i1]]:=1:
od:


fi:


print(`This is round number`, i, ` I have encoded the graph with a random permutation. Do you want to see the encoded graph`):
print(`or do you want to see the encoded Hamiltonian cycle?`):

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

if d=1 then
 print(`You decided to see the encoded graph, here it is, go ahead and check that it is OK`):
 print(gu[1],B2):
 if not CheckEnH(G,gu[1],B2) then
   print(`Verifer: Liar!. I refuse to accept it.`):
   print(`You were found out at round`, i):
  RETURN(FAIL):
  else
   print(`Verifier: Looks, OK`):
 fi:

else
 print(`You decided to see the encoded Hamiltonian cycle, here it is, go ahead and check that it is indeed a cycle`):
 print(gu3):

 print(`and here are the contents of the B2 boxes, make sure that they all have a 1 in them.`):
   
print([seq( B2[ gu3[i1]  ], i1=1..N)]):

 if not  {seq( B2[ gu3[i1]] , i1=1..N)}={1} then
  print(`Verifer: Liar!. They are not all 1s`):
    print(`You were found out at round`, i):
  RETURN(FAIL):

  else
   print(`Verifier: Looks, OK`):
 fi:

 
fi:
od:

print(`Prover: I hope that you are convinced that I do know a Hamiltonian cycle, even though you have no clue what it is. `):
print(``):
print(`----------------------------`):
print(``):
RETURN(true):
end:


#CheatHs(G,N,k):Silnet version of CheatH(G,N,k).  Try:
#G:=RaG(20,1/2): CheatHs(G,20,10):
CheatHs:=proc(G,N,k) local pi,gu,i,d,P,e,i1,B2,gu3:

pi:=randperm(N):
P:=[seq({pi[i],pi[i+1]},i=1..N-1), {pi[N],pi[1]}]:



for i from 1 to k do

gu:=MakeBoxesH(G,P):

gu3:=gu[3]:
B2:=gu[2]:

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

if e=1 then

for i1  from 1 to nops(gu3) do
 B2[gu3[i1]]:=1:
od:


fi:



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

if d=1 then

 if not CheckEnHs(G,gu[1],B2) then

  RETURN(false,i):
 fi:

else


 if not  {seq( B2[ gu3[i1]] , i1=1..N)}={1} then
  RETURN(false,i):
 fi:

 
fi:
od:

true,i:
end:

#Check3C(G,C): Given a graph G om N vertices and a coloring C (with colors C) checks that it is a proper coloring.
#Try:
#Check3C({{1,2},{1,3},{2,3}},[1,2,3]);
Check3C:=proc(G,C) local e:

for e in G do
 if C[e[1]]=C[e[2]] then
#  print(`The two endpoints of edge`, e, ` are both colored by the same color`, C[e[1]]):
  RETURN(false):
 fi:
od:
true:

end:

#KufN(N): {0,1,2}^N. Try:
#KufN(5);
KufN:=proc(N) local i,gu,gu1:
option remember:
if N=0 then
 RETURN({[]}):
fi:
gu:=KufN(N-1):
{seq(seq([op(gu1),i],i=1..3),gu1 in gu)}:
end:




#Find3C(N,G): inputs a graph G on N vertices, finds a 3-coloring, or returns FAIL. Try
#Find3C(4,{{1,2},{1,3},{1,4}});
Find3C:=proc(N,G) local gu,gu1:
gu:=KufN(N):

for gu1 in gu do
 if Check3C(G,gu1) then
    RETURN(gu1):
 fi:
od:
FAIL:

end:


#GwC(N,eps): A random graph on N vertices with density eps (a rational number) together with a
#known coloring. The output is [G,C] where C is the coloring. It startw with  a coloring
#C and then constructs a random graph for which it is a legal coloring. Try:
#GwC(8,1/2);
GwC:=proc(N,eps) local ra1, C, i,j, ra2,  m,n,G,lu:

if not type(eps, fraction) and eps>0 and eps<1 then
 print(eps, `should be a fraction between 0 and 1`):
 RETURN(FAIL):
fi:

ra1:=rand(1..3):

C:=[seq(ra1(),i=1..N)]:

m:=numer(eps): n:=denom(eps):
ra2:=rand(1..n):

G:={}:

  for i from 1 to N do
    for j from i+1 to N do
      if C[i]<>C[j] then
          lu:=ra2():
           if lu<=m then
             G:=G union {{i,j}}:
           fi:
      fi:
   od:
 od:
G,C:
end:

         




#MakeBoxesC(G,C): Given a graph G and a 3-Coloring C (with colors 1,2,3), the prover makes boxes. Try:
#gu:=GwC(10,1/2):MakeBoxesC(gu);
MakeBoxesC:=proc(G,C) local N,i,j,gu,pi,B1c,B1v, B2:
N:=nops(C):

gu:=[seq(seq([i,j],i=1..3),j=1..N)]:
gu:
pi:=randperm(3*N):

for i from 1 to 3*N do
 B1c[pi[i]]:=gu[pi[i]][1]:
 B1v[pi[i]]:=gu[pi[i]][2]:
od:


for i from 1 to 3*N do
 for j from i+1 to 3*N do
      if C[B1v[i]]=B1c[i]  and  C[B1v[j]]=B1c[j]  and member({B1v[i], B1v[j]},G) then
          B2[i,j]:=1:
         else
           B2[i,j]:=0:
      fi:
 od:
od:
op(B1c),op(B1v), op(B2):
             

end:




#CheckEnC(G,N,B1v,B2): Given a graph G on N vertices, an encoding of the vertices, B1v, and a B2 box, checks that the
#encoding is OK. Try:
#gu:=MakeBoxes({{1,2},{1,3}},[1,2,3]); mu:=CheckEnC(G,3,gu[2],gu[3]);
CheckEnC:=proc(G,N,B1v,B2) local i,j:

for i from 1 to 3*N do
 for j from i+1 to 3*N do
     if not member({B1v[i],B1v[j]},G) and B2[i,j]=1 then
        RETURN(false):
     fi:
 od:
od:

true:

end:

   


#ZKPC(G,C,k): A prover shows a graph and claims that he has a 3-Coloring C, he gives the verifer a choice.
#The Zero-Knowlege proof protocol for convincing the verifier that the prover knows the 3-coloring w/o revealing it. Try:
#gu:=GwC(20,1/2): ZKPC(gu,10):
ZKPC:=proc(G,C,k) local ra,gu,N,i,d,B1c,B1v, B2,i1,j1:
N:=nops(C):
ra:=rand(1..2):

print(`Dear Verifier. Conisider the following graph on`, N, `vertices labelled 1,...`, N, `given as a set of its edges `):
print(``):
print(G):
print(``):

print(`I know a 3-Coloring (with colors 1,2,3) on that graph, but there is no way that I would tell you this. But I want to convince you that I am not lying`):
print(``): 
print(`You have`, k, `rounds  to be convinced that I am not lying`):

for i from 1 to k do

print(`This is round number `, i):
print(``):
 gu:=MakeBoxesC(G,C):
 B1c:=gu[1]:
  B1v:=gu[2]:
   B2:=gu[3]:
  print(`Prover: I have encoded the coloring and the graph into two kind of Boxes, B1[i] (each consisting of [color,vertex], and B2[i,j], you have two choices`):
  print(`Option 1: I will open ALL the B2 boxes, and all the`, 3*N, ` vertex-containing boxes of B1`):
   print(`Option 2: I will open the`, 3*N, `color B1 boxes, and only the boxes B2[i,j], such that the color of B1[i] contains the same color as B1[j]`):
   print(`These should all be 0`):
    d:=ra():

  print(`Verifier: I choose Option`, d):
   print(``):
    if d=1 then
   print(``):
   print(`Prover: The number containing boxes are as follows`):
   print(``):
    print(op(B1v)):
   print(``):
   print(`The Bij boxes are as follows`):
     print(``):
  print(op(B2)):
     print(``):
   if CheckEnC(G,N,B1v,B2)  then
    print(`Verifier: Looks OK`):
   else
   print(`Liar, something is wrong`):
     RETURN(false):
   fi:

   else

  print(`The colored boxes are`):
   print(``):
    print(op(B1c)):
   print(``):
 
   for i1 from 1 to 3*N do
      for j1 from i1+1 to 3*N do
         if B1c[i1]=B1c[j1] then
            print(`The color-boxes of the coded vertices`, i1,j1, `are the same, namely`, B1c[i1], `while the B2 value is`, B2[i1,j1] ):
             if B2[i1,j1]=1 then
                 print(`Liar, the value is 1, and it should be 0`):
                 RETURN(false):
             fi:


         fi:
      od:
   od:
    print(`Verifier: Looks OK`):
 fi:
 od:

print(`Prover: I hope that you are convinced that I do know a 3-Coloring of the graph, even though you have no clue what it is. `):
print(``):
print(`----------------------------`):
print(``):
RETURN(true):

end:




#CheatC(G,N,k): Inputs a graph G on N vertices,  picks a random coloring, not necessarily proper
#and claims that he has a 3-Coloring C, he gives the verifer a choice.
#The Zero-Knowlege proof protocol hopefully should fail unless the prover found a proper coloring. Try
#G:=RaG(20,1/2); CheatC(Gu,20,10);

CheatC:=proc(G,N,k) local raC,C,ra,gu,i,d,B1c,B1v, B2,i1,j1,e:

if not(type(N,integer) and N>0 and type(G,set) and {seq(type(G[i1],set),i1=1..nops(G))}={true} and {seq(nops(G[i1]),i1=1..nops(G))}={2}
           and type(k, integer) and k>0) then
   print(`Bad input`):
   RETURN(FAIL):
fi:


raC:=rand(1..3):

C:=[seq(raC(),i1=1..N)]:

if Check3C(G,C) then
 print(`By luck the prover found a proper coloring`):
 RETURN(FAIL):
fi:


ra:=rand(1..2):

print(`Dear Verifier. Conisider the following graph on`, N, `vertices labelled 1,...`, N, `given as a set of its edges `):
print(``):
print(G):
print(``):

print(`I know a 3-Coloring (with colors 1,2,3) on that graph, but there is no way that I would tell you this. But I want to convince you that I am not lying`):
print(``): 
print(`You have`, k, `rounds  to be convinced that I am not lying`):

for i from 1 to k do

print(`This is round number `, i):
print(``):
 gu:=MakeBoxesC(G,C):

    
 B1c:=gu[1]:
  B1v:=gu[2]:
   B2:=gu[3]:

e:=ra():

if e=2 then

  for i1 from 1 to 3*N do
   for j1 from i1+1 to 3*N do
     if B1c[i1]=B1c[j1] then
        B2[i1,j1]:=0:
     fi:
   od:
 od:
fi:

  print(`Prover: I have encoded the coloring and the graph into two kind of Boxes, B1[i] (each consisting of [color,vertex], and B2[i,j], you have two choices`):
  print(`Option 1: I will open ALL the B2 boxes, and all the`, 3*N, ` vertex-containing boxes of B1`):
   print(`Option 2: I will open the`, 3*N, `color B1 boxes, and only the boxes B2[i,j], such that the color of B1[i] contains the same color as B1[j]`):
   print(`These should all be 0`):
    d:=ra():

  print(`Verifier: I choose Option`, d):
   print(``):
    if d=1 then
   print(``):
   print(`Prover: The number containing boxes are as follows`):
   print(``):
    print(op(B1v)):
   print(``):
   print(`The Bij boxes are as follows`):
     print(``):
  print(op(B2)):
     print(``):
   if CheckEnC(G,N,B1v,B2)  then
    print(`Verifier: Looks OK`):
   else
   print(`Liar, something is wrong`):
    print(`You were found out after`, i, `rounds `):
     RETURN(false,i):
   fi:

   else

  print(`The colored boxes are`):
   print(``):
    print(op(B1c)):
   print(``):
 
   for i1 from 1 to 3*N do
      for j1 from i1+1 to 3*N do
         if B1c[i1]=B1c[j1] then
            print(`The color-boxes of the coded vertices`, i1,j1, `are the same, namely`, B1c[i1], `while the B2 value is`, B2[i1,j1] ):
             if B2[i1,j1]=1 then
                 print(`Liar, the value is 1, and it should be 0`):
                     print(`You were found out after`, i, `rounds `):
                 RETURN(false,i):
             fi:


         fi:
      od:
   od:
    print(`Verifier: Looks OK`):
 fi:
 od:

print(`Prover: I hope that you are convinced that I do know a 3-Coloring of the graph, even though you have no clue what it is. `):
print(``):
print(`----------------------------`):
print(``):
RETURN(true,i):

end:


#CheatCs(G,N,k): Silnet version of CheatC(G,N,k), only returns false,NumberOfRounds. Try:
#G:=RaG(20,1/2); CheatCs(G,20,10);

CheatCs:=proc(G,N,k) local raC,C,ra,gu,i,d,B1c,B1v, B2,i1,j1,e:

if not(type(N,integer) and N>0 and type(G,set) and {seq(type(G[i1],set),i1=1..nops(G))}={true} and {seq(nops(G[i1]),i1=1..nops(G))}={2}
           and type(k, integer) and k>0) then
   print(`Bad input`):
   RETURN(FAIL):
fi:


raC:=rand(1..3):

C:=[seq(raC(),i1=1..N)]:

if Check3C(G,C) then
 print(`By luck the prover found a proper coloring`):
 RETURN(FAIL):
fi:


ra:=rand(1..2):


for i from 1 to k do

 gu:=MakeBoxesC(G,C):

    
 B1c:=gu[1]:
  B1v:=gu[2]:
   B2:=gu[3]:

e:=ra():

if e=2 then

  for i1 from 1 to 3*N do
   for j1 from i1+1 to 3*N do
     if B1c[i1]=B1c[j1] then
        B2[i1,j1]:=0:
     fi:
   od:
 od:
fi:


    d:=ra():


    if d=1 then
   if not CheckEnC(G,N,B1v,B2)  then
     RETURN(false,i):
   fi:

   else

 
   for i1 from 1 to 3*N do
      for j1 from i1+1 to 3*N do
         if B1c[i1]=B1c[j1] then
             if B2[i1,j1]=1 then
                 RETURN(false,i):
             fi:


         fi:
      od:
   od:
 fi:
 od:

true,i:

end:


######################################################################


#ManyCheatHs(N,eps,K);
#Simulates CheatHs for graphs with N vertices and density eps K times, returns the list whose i-th entry is
#is the number of times the cheater was found out at the i-th round/ Try:
#ManyCheatHs(20,1/2,64);
ManyCheatHs:=proc(N,eps,K) local X,G,gu,i:
gu:=0:

for i from 1 to K do
 G:=RaG(N,eps): 
 gu:=gu+X^CheatHs(G,20,100)[2]:     
od:
evalf([seq(coeff(gu,X,i)/subs(X=1,gu),i=1..degree(gu,X))]):
end:

#ManyCheatCs(N,eps,K);
#Simulates CheatCs for graphs with N vertices and density eps K times, returns the list whose i-th entry is
#is the number of times the cheater was found out at the i-th round/ Try:
#ManyCheatCs(20,1/2,64);
ManyCheatCs:=proc(N,eps,K) local X,G,gu,i,ku:
gu:=0:
for i from 1 to K do
 G:=RaG(N,eps): 
 ku:=CheatCs(G,N,100):
 if ku<>FAIL then
  gu:=gu+X^ku[2]: 
 fi:
     
od:
evalf([seq(coeff(gu,X,i)/subs(X=1,gu),i=1..degree(gu,X))]):
end: