You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@milagro.apache.org by sa...@apache.org on 2020/02/07 13:12:56 UTC
[incubator-milagro-MPC] 01/05: Add double Schnorr proof
This is an automated email from the ASF dual-hosted git repository.
sandreoli pushed a commit to branch add-dschnorr-proof
in repository https://gitbox.apache.org/repos/asf/incubator-milagro-MPC.git
commit 877350cf1910eea88162b7eb7a14b086a35b48e2
Author: Samuele Andreoli <sa...@yahoo.it>
AuthorDate: Thu Feb 6 13:29:28 2020 +0000
Add double Schnorr proof
---
include/amcl/schnorr.h | 54 ++++++++++++++-
src/schnorr.c | 182 ++++++++++++++++++++++++++++++++++++++++++++++---
2 files changed, 224 insertions(+), 12 deletions(-)
diff --git a/include/amcl/schnorr.h b/include/amcl/schnorr.h
index a3d9fdd..3a091cb 100644
--- a/include/amcl/schnorr.h
+++ b/include/amcl/schnorr.h
@@ -41,7 +41,7 @@ extern "C"
#define SFS_SECP256K1 MODBYTES_256_56 /**< Schnorr Field Size */
#define SCHNORR_OK 0 /**< Valid proof */
-#define SCHNORR_FAIL 51 /**< Invalid proof */
+#define SCHNORR_FAIL 51 /**< Invalid proof */
#define SCHNORR_INVALID_ECP 52 /**< Not a valid point on the curve */
/* Classic Schnorr's proofs API */
@@ -83,6 +83,58 @@ extern void SCHNORR_prove(octet *R, octet *E, octet *X, octet *P);
*/
extern int SCHNORR_verify(octet *V, octet *C, octet *E, octet *P);
+/* Double Schnorr's proofs API */
+
+// The double Schnorr Proof allows to prove knwoldedge of
+// s,l s.t. V = s.R + l.G for some R ECP
+
+/*! \brief Generate a commitment for the proof
+ *
+ * @param RNG CSPRNG to use for commitment
+ * @param R Public ECP base of the DLOG. Compressed form
+ * @param A Secret value used for the commitment. If RNG is NULL this is read
+ * @param B Secret value used for the commitment. If RNG is NULL this is read
+ * @param C Public commitment value. An ECP in compressed form
+ * @return SCHNORR_INVALID_ECP if R is not a valid ECP, SCHNORR_OK otherwise
+ */
+extern int SCHNORR_D_commit(csprng *RNG, octet *R, octet *A, octet *B, octet *C);
+
+/*! \brief Generate the challenge for the proof
+ *
+ * Compute the challenge for the proof. RFC8235#section-3.3 can not be applied
+ * here, but we try to follow closely by treating R like a secondary generator.
+ * Returns H(G, R, C, V)
+ *
+ * @param V Public ECP result of the DLOG. V = s.R + l.G. Compressed form
+ * @param R Public ECP base of the DLOG. Compressed form
+ * @param C Public commitment value. Compressed form
+ * @param E Challenge generated
+ */
+extern void SCHNORR_D_challenge(octet *R, octet *V, octet *C, octet *E);
+
+/*! \brief Generate the proof for the given commitment and challenge
+ *
+ * @param A Secret value used for the commitment
+ * @param B Secret value used for the commitment
+ * @param E Challenge received from the verifier
+ * @param S Secret exponent of the DLOG. V = s.R + l.G
+ * @param L Secret exponent of the DLOG. V = s.R + l.G
+ * @param T First component of the proof of knowldege of the DLOG
+ * @param U Second component of the proof of knowldege of the DLOG
+ */
+extern void SCHNORR_D_prove(octet *A, octet *B, octet *E, octet *S, octet *L, octet *T, octet *U);
+
+/*! \brief Verify the proof of knowledge for the DLOG
+ *
+ * @param R Public ECP base of the DLOG. Compressed form
+ * @param V Public ECP of the DLOG. V = s.R + l.G. Compressed form
+ * @param C Commitment value received from the prover
+ * @param E Challenge for the Schnorr Proof
+ * @param P Proof received from the prover
+ * @return SCHNORR_OK if the prove is valid or an error code
+ */
+extern int SCHNORR_D_verify(octet *R, octet *V, octet *C, octet *E, octet *T, octet *U);
+
#ifdef __cplusplus
}
#endif
diff --git a/src/schnorr.c b/src/schnorr.c
index 7be9103..eb1a7a3 100644
--- a/src/schnorr.c
+++ b/src/schnorr.c
@@ -44,7 +44,7 @@ void SCHNORR_commit(csprng *RNG, octet *R, octet *C)
{
BIG_256_56_randomnum(r, q, RNG);
BIG_256_56_toBytes(R->val, r);
- R->len = MODBYTES_256_56;
+ R->len = SGS_SECP256K1;
}
else
{
@@ -70,7 +70,7 @@ void SCHNORR_challenge(octet *V, octet *C, octet *E)
BIG_256_56 q;
ECP_SECP256K1 G;
- char o[2 * SFS_SECP256K1 + 1];
+ char o[SFS_SECP256K1 + 1];
octet O = {0, sizeof(o), o};
BIG_256_56_rcopy(q, CURVE_Order_SECP256K1);
@@ -89,7 +89,7 @@ void SCHNORR_challenge(octet *V, octet *C, octet *E)
BIG_256_56_mod(e, q);
BIG_256_56_toBytes(E->val, e);
- E->len = MODBYTES_256_56;
+ E->len = SGS_SECP256K1;
}
void SCHNORR_prove(octet *R, octet *E, octet *X, octet *P)
@@ -97,7 +97,6 @@ void SCHNORR_prove(octet *R, octet *E, octet *X, octet *P)
BIG_256_56 r;
BIG_256_56 e;
BIG_256_56 x;
- BIG_256_56 p;
BIG_256_56 q;
DBIG_256_56 d;
@@ -110,17 +109,17 @@ void SCHNORR_prove(octet *R, octet *E, octet *X, octet *P)
// Generate proof r - (e * x) mod the curve order
BIG_256_56_mul(d, e, x);
- BIG_256_56_dmod(p, d, q);
- BIG_256_56_modneg(p, p, q);
- BIG_256_56_add(p, p, r);
- BIG_256_56_mod(p, q);
+ BIG_256_56_dmod(x, d, q);
+ BIG_256_56_modneg(x, x, q);
+ BIG_256_56_add(x, x, r);
+ BIG_256_56_mod(x, q);
- BIG_256_56_toBytes(P->val, p);
- P->len = MODBYTES_256_56;
+ BIG_256_56_toBytes(P->val, x);
+ P->len = SGS_SECP256K1;
// Clean memory
BIG_256_56_zero(r);
- BIG_256_56_zero(x);
+ BIG_256_56_dzero(d);
}
int SCHNORR_verify(octet *V, octet*C, octet *E, octet *P)
@@ -162,3 +161,164 @@ int SCHNORR_verify(octet *V, octet*C, octet *E, octet *P)
return SCHNORR_OK;
}
+
+int SCHNORR_D_commit(csprng *RNG, octet *R, octet *A, octet *B, octet *C)
+{
+ BIG_256_56 a;
+ BIG_256_56 b;
+ BIG_256_56 q;
+
+ ECP_SECP256K1 G;
+ ECP_SECP256K1 ECPR;
+
+ BIG_256_56_rcopy(q, CURVE_Order_SECP256K1);
+ ECP_SECP256K1_generator(&G);
+
+ if (!ECP_SECP256K1_fromOctet(&ECPR, R))
+ {
+ return SCHNORR_INVALID_ECP;
+ }
+
+ // Read or generate secrets A, B
+ if (RNG != NULL)
+ {
+ BIG_256_56_randomnum(a, q, RNG);
+ BIG_256_56_randomnum(b, q, RNG);
+ BIG_256_56_toBytes(A->val, a);
+ BIG_256_56_toBytes(B->val, b);
+ A->len = SGS_SECP256K1;
+ B->len = SGS_SECP256K1;
+ }
+ else
+ {
+ BIG_256_56_fromBytesLen(a, A->val, A->len);
+ BIG_256_56_fromBytesLen(b, B->val, B->len);
+ }
+
+ // Generate commitment C = a.R + b.G
+ ECP_SECP256K1_mul2(&ECPR, &G, a, b);
+ ECP_SECP256K1_toOctet(C, &ECPR, 1);
+
+ // Clean memory
+ BIG_256_56_zero(a);
+ BIG_256_56_zero(b);
+
+ return SCHNORR_OK;
+}
+
+void SCHNORR_D_challenge(octet *R, octet *V, octet *C, octet *E)
+{
+ hash256 sha;
+
+ BIG_256_56 e;
+ BIG_256_56 q;
+ ECP_SECP256K1 G;
+
+ char o[SFS_SECP256K1 + 1];
+ octet O = {0, sizeof(o), o};
+
+ BIG_256_56_rcopy(q, CURVE_Order_SECP256K1);
+
+ ECP_SECP256K1_generator(&G);
+ ECP_SECP256K1_toOctet(&O, &G, 1);
+
+ // e = H(G,R,C,V) mod q
+ HASH256_init(&sha);
+ hash_octet(&sha, &O);
+ hash_octet(&sha, R);
+ hash_octet(&sha, C);
+ hash_octet(&sha, V);
+ HASH256_hash(&sha, o);
+
+ BIG_256_56_fromBytesLen(e, o, SHA256);
+ BIG_256_56_mod(e, q);
+
+ BIG_256_56_toBytes(E->val, e);
+ E->len = MODBYTES_256_56;
+}
+
+void SCHNORR_D_prove(octet *A, octet *B, octet *E, octet *S, octet *L, octet *T, octet *U)
+{
+ BIG_256_56 r;
+ BIG_256_56 e;
+ BIG_256_56 x;
+ BIG_256_56 q;
+ DBIG_256_56 d;
+
+ BIG_256_56_rcopy(q, CURVE_Order_SECP256K1);
+ BIG_256_56_fromBytesLen(e, E->val, E->len);
+
+ // Generate proof t = a + (e * s) mod the curve order
+ BIG_256_56_fromBytesLen(x, S->val, S->len);
+ BIG_256_56_fromBytesLen(r, A->val, A->len);
+
+ BIG_256_56_mul(d, e, x);
+ BIG_256_56_dmod(x, d, q);
+ BIG_256_56_add(x, x, r);
+ BIG_256_56_mod(x, q);
+
+ BIG_256_56_toBytes(T->val, x);
+ T->len = SGS_SECP256K1;
+
+ // Generate proof u = b + (e * l) mod the curve order
+ BIG_256_56_fromBytesLen(x, L->val, L->len);
+ BIG_256_56_fromBytesLen(r, B->val, B->len);
+
+ BIG_256_56_mul(d, e, x);
+ BIG_256_56_dmod(x, d, q);
+ BIG_256_56_add(x, x, r);
+ BIG_256_56_mod(x, q);
+
+ BIG_256_56_toBytes(U->val, x);
+ U->len = SGS_SECP256K1;
+
+ // Clean memory
+ BIG_256_56_zero(r);
+ BIG_256_56_dzero(d);
+}
+
+int SCHNORR_D_verify(octet *R, octet *V, octet *C, octet *E, octet *T, octet *U)
+{
+ ECP_SECP256K1 G;
+ ECP_SECP256K1 ECPR;
+ ECP_SECP256K1 ECPV;
+ ECP_SECP256K1 ECPC;
+
+ BIG_256_56 t;
+ BIG_256_56 u;
+
+ // Read octets
+ if (!ECP_SECP256K1_fromOctet(&ECPV, V))
+ {
+ return SCHNORR_INVALID_ECP;
+ }
+
+ if (!ECP_SECP256K1_fromOctet(&ECPR, R))
+ {
+ return SCHNORR_INVALID_ECP;
+ }
+
+ if (!ECP_SECP256K1_fromOctet(&ECPC, C))
+ {
+ return SCHNORR_INVALID_ECP;
+ }
+
+ BIG_256_56_fromBytesLen(t, T->val, T->len);
+ BIG_256_56_fromBytesLen(u, U->val, U->len);
+
+ // Compute verification t.R + u.G
+ ECP_SECP256K1_generator(&G);
+ ECP_SECP256K1_mul2(&ECPR, &G, t, u);
+
+ // Compute ground truth C + e.V
+ BIG_256_56_fromBytesLen(t, E->val, E->len);
+ ECP_SECP256K1_mul(&ECPV, t);
+ ECP_SECP256K1_add(&ECPV, &ECPC);
+
+ if (!ECP_SECP256K1_equals(&ECPV, &ECPR))
+ {
+ return SCHNORR_FAIL;
+ }
+
+ return SCHNORR_OK;
+}