This is an automated email from the ASF dual-hosted git repository. sandreoli pushed a commit to branch update-model-no-replay in repository https://gitbox.apache.org/repos/asf/incubator-milagro-MPC.git
commit 6c5b375355c4789aa5d20e8e13ffefbf0183263f Author: Samuele Andreoli <[email protected]> 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; +}
