gp-scripts: add zkp + test parameters

1 files changed, 129 insertions, 0 deletions

diff --git a/gp-scripts/zkp.gp b/gp-scripts/zkp.gp
new file mode 100644
index 0000000..9bf7b7d
--- /dev/null
+++ b/gp-scripts/zkp.gp
@@ -0,0 +1,129 @@
+\\ 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
+}
+
+;