\\ zero knowledge proofs

read(group);

\\ Don't use in production code!
\\ This is a very stupid implementation only used in performance evaluation.
kdf(in:vec) =
{
	prod(h=1,length(in),lift(in[h]))%q
}


zkp1_proof(G:intmod, x:int) =
{
	local(V:intmod, z:int, A:intmod, c:int, r:int);
	V = G^x;
	z = random(q);
	A = G^z;
	c = kdf([G, V, A]);
	r = (z+c*x)%q;
	[G, r, A, V]
}

zkp1_check(P:vec) =
{
	local(c:int, G:intmod, r:int, A:intmod, V:intmod);
	if (length(P) < 4, error("Proof1 too short."));
	if (type(P[1]) == "t_INTMOD", G = P[1], error("P[1] has wrong type."));
	if (type(P[2]) == "t_INT",    r = P[2], error("P[2] has wrong type."));
	if (type(P[3]) == "t_INTMOD", A = P[3], error("P[3] has wrong type."));
	if (type(P[4]) == "t_INTMOD", V = P[4], error("P[4] has wrong type."));
	c = kdf([G, V, A]);
	G^r == A*V^c
}


zkp2_proof(G1:intmod, G2:intmod, x:int) =
{
	local(V:intmod, W:intmod, z:int, A:intmod, B:intmod, c:int, r:int);
	V = G1^x;
	W = G2^x;
	z = random(q);
	A = G1^z;
	B = G2^z;
	c = kdf([G1, G2, V, W, A, B]);
	r = (z+c*x)%q;
	[G1, G2, r, A, B, V, W]
}

zkp2_check(P:vec) =
{
	local(c:int,
		G1:intmod, G2:intmod, r:int, A:intmod, B:intmod, V:intmod, W:intmod);
	if (length(P) < 7, error("Proof2 too short."));
	if (type(P[1]) == "t_INTMOD", G1 = P[1], error("P[1] has wrong type."));
	if (type(P[2]) == "t_INTMOD", G2 = P[2], error("P[2] has wrong type."));
	if (type(P[3]) == "t_INT",    r  = P[3], error("P[3] has wrong type."));
	if (type(P[4]) == "t_INTMOD", A  = P[4], error("P[4] has wrong type."));
	if (type(P[5]) == "t_INTMOD", B  = P[5], error("P[5] has wrong type."));
	if (type(P[6]) == "t_INTMOD", V  = P[6], error("P[6] has wrong type."));
	if (type(P[7]) == "t_INTMOD", W  = P[7], error("P[7] has wrong type."));
	c = kdf([G1, G2, V, W, A, B]);
	G1^r == A*V^c && G2^r == B*W^c
}


zkp3_proof(G:intmod, Y:intmod, M:intmod) =
{
	local(Alpha:intmod, Beta:intmod, A1:intmod, A2:intmod, B1:intmod, B2:intmod,
		d1:int, d2:int, r1:int, r2:int, w:int, r:int);
	r = random(q);
	Alpha = M*Y^r;
	Beta = G^r;
	if (M == Mod(1, p),
		d1 = random(q);
		r1 = random(q);
		w = random(q);
		A1 = G^r1 * Beta^d1;
		B1 = Y^r1 * (Alpha / G)^d1;
		A2 = G^w;
		B2 = Y^w;
		c = kdf([G, Alpha, Beta, A1, A2, B1, B2]);
		d2 = (c - d1) % q;
		r2 = (w - r*d2) % q;
		,
		if (M == G,
			d2 = random(q);
			r2 = random(q);
			w = random(q);
			A1 = G^w;
			B1 = Y^w;
			A2 = G^r2 * Beta^d2;
			B2 = Y^r2 * Alpha^d2;
			c = kdf([G, Alpha, Beta, A1, A2, B1, B2]);
			d1 = (c - d2) % q;
			r1 = (w - r*d1) % q;
			, error("M is neither 1 nor G")
		)
	);
	[G, Y, Alpha, Beta, A1, A2, B1, B2, d1, d2, r1, r2, r]
}

zkp3_check(P:vec) =
{
	local(c:int,
		G:intmod, Y:intmod, Alpha:intmod, Beta:intmod, A1:intmod, A2:intmod, B1:intmod, B2:intmod,
		d1:int, d2:int, r1:int, r2:int);
	if (length(P) < 12, error("Proof3 too short."));
	if (type(P[1] ) == "t_INTMOD", G      = P[1],  error("P[1]  has wrong type."));
	if (type(P[2] ) == "t_INTMOD", Y      = P[2],  error("P[2]  has wrong type."));
	if (type(P[3] ) == "t_INTMOD", Alpha  = P[3],  error("P[3]  has wrong type."));
	if (type(P[4] ) == "t_INTMOD", Beta   = P[4],  error("P[4]  has wrong type."));
	if (type(P[5] ) == "t_INTMOD", A1     = P[5],  error("P[5]  has wrong type."));
	if (type(P[6] ) == "t_INTMOD", A2     = P[6],  error("P[6]  has wrong type."));
	if (type(P[7] ) == "t_INTMOD", B1     = P[7],  error("P[7]  has wrong type."));
	if (type(P[8] ) == "t_INTMOD", B2     = P[8],  error("P[8]  has wrong type."));
	if (type(P[9] ) == "t_INT",    d1     = P[9],  error("P[9]  has wrong type."));
	if (type(P[10]) == "t_INT",    d2     = P[10], error("P[10] has wrong type."));
	if (type(P[11]) == "t_INT",    r1     = P[11], error("P[11] has wrong type."));
	if (type(P[12]) == "t_INT",    r2     = P[12], error("P[12] has wrong type."));
	c = kdf([G, Alpha, Beta, A1, A2, B1, B2]);
	c == (d1 + d2) % q &&
		A1 == G^r1 * Beta^d1 &&
		A2 == G^r2 * Beta^d2 &&
		B1 == Y^r1 * (Alpha / G)^d1 &&
		B2 == Y^r2 * Alpha^d2
}

;