// ****************************************** // 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:=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;