// ******************************************
// MQ identification scheme (5-round version)
// creates a random quadratic system of m equations in n variables
// and a key pair of MQIdent
//  The function MQIDround(Ch) generates, on the input of alpha \in F and Ch in (0,1), the output of the prover
// **********************************************


q:=4;
F<w>:=GF(q);
m:=4;
n:=4;
Vm:=VectorSpace(F,m);
Vn:=VectorSpace(F,n);
Vnm:=VectorSpace(F,n+m);
Vnnm:=VectorSpace(F,2*n+m);
Pol<[x]>:=PolynomialRing(F,n);

printf "******************************************************** \n";
printf "*** MQ based identification scheme (5 pass version) *** \n";
printf "******************************************************** \n\n\n";


printf "***Parameters*** \n\n";
printf "F:= GF(%o) \n \n",q;
printf "m:= %o \n\n",m;
printf "n:= %o \n\n", n;

ev:= function(m,n,pol,s)
    v:=[];
    for i:=1 to m do
        v[i]:=Evaluate(pol[i],x[1],s[1]);
        for j:=2 to n do
            v[i]:=Evaluate(v[i],x[j],s[j]);
        end for;
    end for;
    v:=Vm!ChangeUniverse(v,F);
    return v;
end function;

pol:=[];
for i:= 1 to m do
    pol[i]:=Pol!0;
    for j:=1 to n do
        for k:=j to n do
            pol[i]:=pol[i]+Random(F)*x[j]*x[k];
        end for;
        pol[i]:=pol[i]+Random(F)*x[j];
    end for;
end for;

printf "\n\n***Key Generation***\n\n";
printf "P:= %o \n \n", pol;

s:= Random(Vn); // private key

v:=ev(m,n,pol,s);

printf "s:= %o \n \n", s;
printf "v:= %o \n \n", v;

MQIDround:= function(alpha,Ch)
    r0:=Random(Vn);
    t0:=Random(Vn);
    e0:=Random(Vm);

    r1:=s-r0;
    
    printf "r0:= %o \n \n", r0;
    printf "t0:= %o \n \n", t0;
    printf "e0:= %o \n \n", e0;
    printf "r1:= %o \n \n", r1;
        
    g:=ev(m,n,pol,t0+r1)-ev(m,n,pol,t0)-ev(m,n,pol,r1) + e0;

    c0:= Vnnm!(Eltseq(r0) cat Eltseq(t0) cat Eltseq(e0));
    c1:= Vnm!(Eltseq(r1) cat Eltseq(g));
    

    printf "c0:=Com %o \n \n", c0;
    printf "c1:=Com %o \n \n", c1;
    COM:=[Eltseq(c0),Eltseq(c1)];
    
    printf"Ch1:= %o \n\n\n", alpha;
    
    t1:= alpha * r0 - t0;
    e1:= alpha * ev(m,n,pol,r0) -e0;
    
    printf "t1:= %o \n \n", Vn!(t1);
    printf "e1:= %o \n\n\n", Vm!(e1);
    Rsp1:=[Eltseq(t1),Eltseq(e1)];

    printf"Ch2:= %o \n\n\n", Ch;
    
    case Ch:
        when 0: Rsp2:= r0;
        when 1: Rsp2:=r1;
    end case;
    
    printf "Rsp:= %o \n\n", Rsp2;
    return COM,Rsp1,Rsp2;
end function;  

MQver:= function(COM,alpha,Rsp1,Ch,Rsp2)
    tr:=true;
    case Ch:
        when 0: 
	     r0:= Rsp2; // parse responses and commitments
	     c0:= Vnnm!COM[1];
	     t1:=Vn!Rsp1[1];
	     e1:=Vm!Rsp1[2];
	     
            if Vnnm! (Eltseq(r0) cat Eltseq(alpha* r0 -t1) cat Eltseq( alpha * ev(m,n,pol,r0)-e1)) ne c0 then //check
	         tr:= false;
	     end if;

	 when 1: 
	     r1:= Rsp2; // parse responses and commitments

	     t1:=Vn!Rsp1[1];
	     e1:=Vm!Rsp1[2];
	     c1:=Vnm!COM[2];
	     
            if Vnm! (Eltseq(r1) cat Eltseq(alpha * (v - ev(m,n,pol,r1)) -ev(m,n,pol,t1+r1) + ev(m,n,pol,t1) + ev(m,n,pol,r1) - e1)) ne c1 then // check
	         tr:= false;
	     end if; 
    end case;
    return tr;
end function;