/* ------------------------------------------------
generates key pair of balanced OV(o,v) over GF(q)
public key is stored in public_key.txt
private key is stored in private_key.txt
at the moment this program and the forgery is for a homogeneous case 
and cT is  set to zero instead a random vector
------------------------------------------------*/
clear ;

q:=2^4; // field size  use either 2^n (even characteristic) or a prime number (odd characteristic)
v:=5; // number of Vinegar variables
o:=v; // number of oil variables
n:=o+v;

//SetSeed(534392861, 34453) ;   // used for book  edition 1

printf "*********************************************** \n";
printf "***  Balanced OV Signature Scheme - Key Generation *** \n";
printf "*********************************************** \n \n";

timet := Cputime() ;

GF<w>:=GaloisField(q);
P<[x]>:=PolynomialRing(GF,n);
Pol<[y]>:=PolynomialRing(P,n);
Vn:=VectorSpace(GF,n);



// affine map T -----------------------------------------------------------------------------
repeat
	MT:=RandomMatrix(GF,n,n); 
until IsInvertible(MT) ;
cT:=Random(Vn);
cT:=[GF!0:i in [1..n]];

T:=[];
for loop:=1 to n do
	T[loop]:=P!0;
	for i:=1 to n do
		T[loop]:=T[loop]+MT[loop][i]*x[i];
	end for;
	T[loop]:=T[loop]+cT[loop];
end for;

// central map Q ---------------------------------------------------------------------------
Q:=[];
for loop:=1 to o do
	Q[loop]:=Pol!0;
	//quadratic terms
	for i:=1 to v do
		for j:=i to n do
			Q[loop]:=Q[loop]+Random(GF)*y[i]*y[j];
		end for;
	end for;
	//no linear terms 
	// for i:=1 to n do
	//	Q[loop]:=Q[loop]+Random(GF)*y[i];
	//end for;
	//no constant terms
	//Q[loop]:=Q[loop]+Random(GF);
end for;



// public key Pk ----------------------------------------------------------------------------
Pk:=Q;
D:=[];
for loop:=1 to o do
	for j:=1 to n do
		Pk[loop]:=Evaluate(Pk[loop],y[j],T[j]);
	end for;
end for;

for loop:=1 to o do
	D[loop]:=MonomialCoefficient(Pk[loop],1);
end for;

// Output ----------------------------------------------------------------------------
printf "q:= %o ; \n \n", q;
printf "o:= v:= %o ; \n \n",o ;
printf "n:= o + v := %o; \n \n",n;

printf "Balanced OV key generation time: %o\n",Cputime(timet);

printf "Write public_key.txt \n \n";
SetOutputFile("public_key.txt":Overwrite:=true);
printf "q:= %o ; \n \n", q;
printf "o:= %o ; \n \n", o;
printf "v:= %o ; \n \n", v;
printf "n:= o + v; \n \n";
printf "GF<w>:=GaloisField(q); \n \n";
printf "P<[x]>:=PolynomialRing(GF,n); \n \n";
printf "Pk:= %o ; \n \n", Pk;
UnsetOutputFile();
 
printf "Write private_key.txt \n \n";
SetOutputFile("private_key.txt":Overwrite:=true);
printf "q:= %o ; \n \n", q;
printf "o:= %o ; \n \n", o;
printf "v:= %o ; \n \n", v;
printf "n:=o+v; \n \n";
printf "GF<w>:=GaloisField(q); \n \n";
printf "P<[x]>:=PolynomialRing(GF,n); \n \n";
printf "Pol<[y]>:=PolynomialRing(P,n); \n \n";
printf "MT:= %o ; \n \n", Eltseq(MT);
printf "cT:= %o ; \n \n", Eltseq(cT);
printf "Q:= %o ; \n \n", Q;
UnsetOutputFile();