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 41a1116ec5eabdaa1ecd886c6cfd5aec53b1d686 Author: Samuele Andreoli <[email protected]> AuthorDate: Wed Feb 5 17:04:34 2020 +0000 Add mtawc zkp --- include/amcl/mta.h | 184 +++++++++++++++++++++++++++++++++++++++++++++++++-- src/mta.c | 190 ++++++++++++++++++++++++++++++++++++++++++++++++++--- 2 files changed, 358 insertions(+), 16 deletions(-) diff --git a/include/amcl/mta.h b/include/amcl/mta.h index 0db289b..a78593f 100644 --- a/include/amcl/mta.h +++ b/include/amcl/mta.h @@ -29,14 +29,16 @@ under the License. #include "amcl/amcl.h" #include "amcl/paillier.h" #include "amcl/commitments.h" +#include "amcl/ecp_SECP256K1.h" #include "amcl/ecdh_SECP256K1.h" #ifdef __cplusplus extern "C" { #endif -#define MTA_OK 0 /**< Proof successfully verified */ -#define MTA_FAIL 61 /**< Invalid proof */ +#define MTA_OK 0 /**< Proof successfully verified */ +#define MTA_FAIL 61 /**< Invalid proof */ +#define MTA_INVALID_ECP 62 /**< Invalid ECP */ /* MTA protocol API */ @@ -107,7 +109,9 @@ void MPC_SUM_MTA(octet *A, octet *B, octet *ALPHA, octet *BETA, octet *SUM); /* MTA Zero Knowledge Proofs API*/ -// The protocol requires a BC modulus (Pt, Qt, Nt, h1, h2) and a Paillier PK (N, g) +// The protocols require a BC modulus (Pt, Qt, Nt, h1, h2) and a Paillier PK (N, g) + +/* Range Proof API */ /** \brief Secret random values for the Range Proof commitment */ typedef struct @@ -239,7 +243,7 @@ extern void MTA_RP_commitment_fromOctets(MTA_RP_commitment *c, octet *Z, octet * */ extern void MTA_RP_proof_toOctets(octet *S, octet *S1, octet *S2, MTA_RP_proof *p); -/** \brief Read the commitments from octets +/** \brief Read the proof from octets * * @param p Destination proof * @param S Octet with the s component of the proof @@ -254,6 +258,8 @@ extern void MTA_RP_proof_fromOctets(MTA_RP_proof *p, octet *S, octet *S1, octet */ extern void MTA_RP_commitment_rv_kill(MTA_RP_commitment_rv *rv); +/* Receiver Zero Knowledge Proof API */ + /** \brief Secret random values for the receiver ZKP commitment */ typedef struct { @@ -355,8 +361,6 @@ extern void MTA_ZK_challenge(PAILLIER_public_key *key, COMMITMENTS_BC_pub_modulu */ extern void MTA_ZK_prove(PAILLIER_public_key *key, MTA_ZK_commitment_rv *rv, octet *X, octet *Y, octet *R, octet *E, MTA_ZK_proof *p); -// TODO go from here - /** \brief Verify a Proof for Receiver ZKP * * Verify the proof of knowledge of x, y associated to c1, c2 and of x range @@ -412,7 +416,7 @@ extern void MTA_ZK_commitment_fromOctets(MTA_ZK_commitment *c, octet *Z, octet * */ extern void MTA_ZK_proof_toOctets(octet *S, octet *S1, octet *S2, octet *T1, octet *T2, MTA_ZK_proof *p); -/** \brief Read the commitments from octets +/** \brief Read the proof from octets * * @param p Destination proof * @param S Octet with the s component of the proof @@ -429,6 +433,172 @@ extern void MTA_ZK_proof_fromOctets(MTA_ZK_proof *p, octet *S, octet *S1, octet */ extern void MTA_ZK_commitment_rv_kill(MTA_ZK_commitment_rv *rv); +/* Receiver Zero Knowledge Proof with Check API */ + +/** \brief Secret random values for the receiver ZKP with check commitment */ +typedef MTA_ZK_commitment_rv MTA_ZKWC_commitment_rv; + +/** \brief Public commitment for the Receiver ZKP with check */ +typedef struct +{ + MTA_ZK_commitment zkc; /**< Commitment for the base Recevier ZKP */ + ECP_SECP256K1 U; /**< Commitment for the DLOG knowledge proof */ +} MTA_ZKWC_commitment; + +/** \brief Range Proof for the Receiver ZKP with check */ +typedef MTA_ZK_proof MTA_ZKWC_proof; + +/** \brief Commitment Generation for Receiver ZKP with check + * + * Generate a commitment for the values x, y and c1 + * + * <ol> + * <li> \f$ \alpha \in_R [0, \ldots, q^3]\f$ + * <li> \f$ \beta \in_R [0, \ldots, N]\f$ + * <li> \f$ \gamma \in_R [0, \ldots, N]\f$ + * <li> \f$ \rho \in_R [0, \ldots, q\tilde{N}]\f$ + * <li> \f$ \rho_1 \in_R [0, \ldots, q^{3}\tilde{N}]\f$ + * <li> \f$ \sigma \in_R [0, \ldots, q\tilde{N}]\f$ + * <li> \f$ \tau \in_R [0, \ldots, q\tilde{N}]\f$ + * <li> \f$ z = h_1^{x}h_2^{\rho} \text{ }\mathrm{mod}\text{ }\tilde{N} \f$ + * <li> \f$ z_1 = h_1^{\alpha}h_2^{\rho_1} \text{ }\mathrm{mod}\text{ }\tilde{N} \f$ + * <li> \f$ t = h_1^{y}h_2^{\sigma} \text{ }\mathrm{mod}\text{ }\tilde{N} \f$ + * <li> \f$ w = h_1^{\gamma}h_2^{\tau} \text{ }\mathrm{mod}\text{ }\tilde{N} \f$ + * <li> \f$ v = c1^{\alpha}g^{\gamma}\beta^{N} \text{ }\mathrm{mod}\text{ }N^2 \f$ + * <li> \f$ U = \alpha.G + * </ol> + * + * @param RNG csprng for random generation + * @param key Paillier key used to encrypt C1 + * @param mod Public BC modulus of the verifier + * @param X Message to prove knowledge and range + * @param Y Message to prove knowledge + * @param C1 Base Paillier Ciphertext + * @param c Destinaton commitment + * @param rv Random values associated to the commitment. If RNG is NULL this is read + */ +extern void MTA_ZKWC_commit(csprng *RNG, PAILLIER_public_key *key, COMMITMENTS_BC_pub_modulus *mod, octet *X, octet *Y, octet *C1, MTA_ZKWC_commitment *c, MTA_ZKWC_commitment_rv *rv); + +/** \brief Deterministic Challenge generations for Receiver ZKP with check + * + * Generate a challenge binding together public parameters and commitment + * + * <ol> + * <li> \f$ e = H( g | \tilde{N} | h_1 | h_2 | q | c_1 | c_2 | U | z | z1 | t | v | w ) \f$ + * </ol> + * + * @param key Public Paillier key of the prover + * @param mod Public BC modulus of the verifier + * @param C1 Base Paillier Ciphertext + * @param C2 New Paillier Ciphertext to prove knowledge and range + * @param c Commitment of the prover + * @param E Destination challenge + */ +extern void MTA_ZKWC_challenge(PAILLIER_public_key *key, COMMITMENTS_BC_pub_modulus *mod, octet *C1, octet *C2, octet *X, MTA_ZKWC_commitment *c, octet *E); + +/** \brief Proof generation for Receiver ZKP with check + * + * Generate a proof of knowledge of x, y and a range proof for x. + * These values are the same as for the ZKP without check. The + * knwoledge of the DLOG can be verified using the value U in the + * commitment + * + * <ol> + * <li> \f$ s = \beta r^e \text{ }\mathrm{mod}\text{ }N \f$ + * <li> \f$ s_1 = ex + \alpha \f$ + * <li> \f$ s_2 = e\rho + \rho_1 \f$ + * <li> \f$ t_1 = ey + \gamma \f$ + * <li> \f$ t_2 = e\sigma + \tau \f$ + * </ol> + * + * @param key Private Paillier key of the prover + * @param rv Random values associated to the commitment + * @param X Message to prove knowledge and range + * @param Y Message to prove knowledge + * @param R Random value used in the Paillier addition + * @param E Generated challenge + * @param p Destination proof + */ +extern void MTA_ZKWC_prove(PAILLIER_public_key *key, MTA_ZKWC_commitment_rv *rv, octet *X, octet *Y, octet *R, octet *E, MTA_ZKWC_proof *p); + +/** \brief Verify a Proof for Receiver ZKP with check + * + * Verify the proof of knowledge of x, y associated to c1, c2 and of x range. + * Additionally verify the knowledge of X = x.G + * + * <ol> + * <li> \f$ s_1 \stackrel{?}{\leq} q^3 \f$ + * <li> \f$ z_1 \stackrel{?}{=} h_1^{s_1}h_2^{s_2}z^{-e} \text{ }\mathrm{mod}\text{ }\tilde{N} \f$ + * <li> \f$ w \stackrel{?}{=} h_1^{t_1}h_2^{t_2}t^{-e} \text{ }\mathrm{mod}\text{ }\tilde{N} \f$ + * <li> \f$ v \stackrel{?}{=} c1^{s_1}s^{N}g^{t_1}c2^{-e} \text{ }\mathrm{mod}\text{ }N^2 \f$ + * <li> \f$ U \stackrel{?}{=} s_1.G - e.X \f$ + * </ol> + * + * @param key Public Paillier key of the prover + * @param mod Private BC modulus of the verifier + * @param C1 Base Paillier Ciphertext + * @param C2 New Paillier Ciphertext to prove knowledge and range + * @param X Public ECP of the DLOG x.G + * @param E Generated challenge + * @param c Received commitment + * @param p Received proof + * @return MTA_OK if the proof is valid, MTA_FAIL otherwise + */ +extern int MTA_ZKWC_verify(PAILLIER_private_key *key, COMMITMENTS_BC_priv_modulus *mod, octet *C1, octet *C2, octet *X, octet *E, MTA_ZKWC_commitment *c, MTA_ZKWC_proof *p); + +/** \brief Dump the commitment to octets + * + * @param U Octet with the commitment for the DLOG ZKP. EGS_SECP256K1 + 1 long + * @param Z Destination Octet for the z component of the commitment. FS_2048 long + * @param Z1 Destination Octet for the z1 component of the commitment. FS_2048 long + * @param T Destination Octet for the t component of the commitment. FS_2048 long + * @param V Destination Octet for the v component of the commitment. FS_4096 long + * @param W Destination Octet for the w component of the commitment. FS_2048 long + * @param c Commitment to export + */ +extern void MTA_ZKWC_commitment_toOctets(octet *U, octet *Z, octet *Z1, octet *T, octet *V, octet *W, MTA_ZKWC_commitment *c); + +/** \brief Read the commitments from octets + * + * @param c Destination commitment + * @param U Octet with the commitment for the DLOG ZKP + * @param Z Octet with the z component of the commitment + * @param Z1 Octet with the z1 component of the commitment + * @param T Octet with the t component of the commitment + * @param V Octet with the v component of the commitment + * @param W Octet with the w component of the commitment + * @return MTA_INVALID_ECP if U is not a valid ECP, MTA_OK otherwise + */ +extern int MTA_ZKWC_commitment_fromOctets(MTA_ZKWC_commitment *c, octet *U, octet *Z, octet *Z1, octet *T, octet *V, octet *W); + +/** \brief Dump the proof to octets + * + * @param S Destination Octet for the s component of the proof. FS_2048 long + * @param S1 Destination Octet for the s1 component of the proof. HFS_2048 long + * @param S2 Destination Octet for the s2 component of the proof. FS_2048 + HFS_2048 long + * @param T1 Destination Octet for the t1 component of the proof. FS_2048 long + * @param T2 Destination Octet for the t2 component of the proof. FS_2048 + HFS_2048 long + * @param p Proof to export + */ +extern void MTA_ZKWC_proof_toOctets(octet *S, octet *S1, octet *S2, octet *T1, octet *T2, MTA_ZKWC_proof *p); + +/** \brief Read the proof from octets + * + * @param p Destination proof + * @param S Octet with the s component of the proof + * @param S1 Octet with the s1 component of the proof + * @param S2 Octet with the s2 component of the proof + * @param T1 Octet with the t1 component of the proof + * @param T2 Octet with the t2 component of the proof + */ +extern void MTA_ZKWC_proof_fromOctets(MTA_ZKWC_proof *p, octet *S, octet *S1, octet *S2, octet *T1, octet *T2); + +/** \brief Clean the memory containing the random values + * + * @param rv Random values to clean + */ +extern void MTA_ZKWC_commitment_rv_kill(MTA_ZKWC_commitment_rv *rv); + #ifdef __cplusplus } #endif diff --git a/src/mta.c b/src/mta.c index 5fa3a31..3022be0 100644 --- a/src/mta.c +++ b/src/mta.c @@ -141,7 +141,7 @@ void hash_RP_params(hash256 *sha, PAILLIER_public_key *key, COMMITMENTS_BC_pub_m // Process curve orer BIG_256_56_toBytes(OCT.val, q); - OCT.len = MODBYTES_256_56; + OCT.len = EGS_SECP256K1; OCT_hash(sha, &OCT); } @@ -450,7 +450,7 @@ void MTA_RP_challenge(PAILLIER_public_key *key, COMMITMENTS_BC_pub_modulus *mod, BIG_256_56_mod(t, q); BIG_256_56_toBytes(E->val, t); - E->len = MODBYTES_256_56; + E->len = EGS_SECP256K1; } void MTA_RP_prove(PAILLIER_private_key *key, MTA_RP_commitment_rv *rv, octet *M, octet *R, octet *E, MTA_RP_proof *p) @@ -628,7 +628,6 @@ int MTA_RP_verify(PAILLIER_public_key *key, COMMITMENTS_BC_priv_modulus *mod, oc return MTA_OK; } - void MTA_RP_commitment_toOctets(octet *Z, octet *U, octet *W, MTA_RP_commitment *c) { FF_2048_toOctet(Z, c->z, FFLEN_2048); @@ -777,9 +776,7 @@ void MTA_ZK_commit(csprng *RNG, PAILLIER_public_key *key, COMMITMENTS_BC_pub_mod void MTA_ZK_challenge(PAILLIER_public_key *key, COMMITMENTS_BC_pub_modulus *mod, octet *C1, octet *C2, MTA_ZK_commitment *c, octet *E) { hash256 sha; - - char oct[2*FS_2048]; - octet OCT = {0, sizeof(oct), oct}; + char digest[SHA256]; BIG_256_56 q; BIG_256_56 t; @@ -800,12 +797,12 @@ void MTA_ZK_challenge(PAILLIER_public_key *key, COMMITMENTS_BC_pub_modulus *mod, hash_ZK_commitment(&sha, c); /* Output */ - HASH256_hash(&sha, OCT.val); - BIG_256_56_fromBytesLen(t, OCT.val, SHA256); + HASH256_hash(&sha, digest); + BIG_256_56_fromBytesLen(t, digest, SHA256); BIG_256_56_mod(t, q); BIG_256_56_toBytes(E->val, t); - E->len = MODBYTES_256_56; + E->len = EGS_SECP256K1; } void MTA_ZK_prove(PAILLIER_public_key *key, MTA_ZK_commitment_rv *rv, octet *X, octet *Y, octet *R, octet *E, MTA_ZK_proof *p) @@ -1014,3 +1011,178 @@ void MTA_ZK_commitment_rv_kill(MTA_ZK_commitment_rv *rv) FF_2048_zero(rv->sigma, FFLEN_2048 + HFLEN_2048); FF_2048_zero(rv->tau, FFLEN_2048 + HFLEN_2048); } + +void MTA_ZKWC_commit(csprng *RNG, PAILLIER_public_key *key, COMMITMENTS_BC_pub_modulus *mod, octet *X, octet *Y, octet *C1, MTA_ZKWC_commitment *c, MTA_ZKWC_commitment_rv *rv) +{ + BIG_1024_58 ff_alpha[HFLEN_2048]; + BIG_1024_58 ff_q[HFLEN_2048]; + + BIG_256_56 alpha; + + char oct[HFS_2048]; + octet OCT = {0, sizeof(oct), oct}; + + char oct_alpha[EGS_SECP256K1]; + octet ALPHA = {0, sizeof(oct_alpha), oct_alpha}; + + /* Compute base commitment for the range and knowledge ZKP */ + + MTA_ZK_commit(RNG, key, mod, X, Y, C1, &(c->zkc), rv); + + /* Compute commitment for DLOG knowledge ZKP */ + + // Reduce alpha modulo curve order + OCT_fromHex(&OCT, curve_order_hex); + FF_2048_zero(ff_q, HFLEN_2048); + BIG_1024_58_fromBytesLen(ff_q[0], OCT.val, OCT.len); + + FF_2048_copy(ff_alpha, rv->alpha, HFLEN_2048); + FF_2048_mod(ff_alpha, ff_q, HFLEN_2048); + FF_2048_toOctet(&OCT, ff_alpha, HFLEN_2048); + OCT_chop(&OCT, &ALPHA, HFS_2048 - EGS_SECP256K1); + BIG_256_56_fromBytesLen(alpha, ALPHA.val, ALPHA.len); + + // Commit to U = alpha.G + ECP_SECP256K1_generator(&(c->U)); + ECP_SECP256K1_mul(&(c->U), alpha); +} + +void MTA_ZKWC_challenge(PAILLIER_public_key *key, COMMITMENTS_BC_pub_modulus *mod, octet *C1, octet *C2, octet *X, MTA_ZKWC_commitment *c, octet *E) +{ + hash256 sha; + char digest[SHA256]; + + char oct[EFS_SECP256K1 + 1]; + octet OCT = {0, sizeof(oct), oct}; + + BIG_256_56 q; + BIG_256_56 t; + + // Load curve order + BIG_256_56_rcopy(q, CURVE_Order_SECP256K1); + + HASH256_init(&sha); + + /* Bind to public parameters */ + hash_RP_params(&sha, key, mod, q); + + /* Bind to proof input */ + OCT_hash(&sha, C1); + OCT_hash(&sha, C2); + OCT_hash(&sha, X); + + /* Bind to proof commitment for DLOG */ + ECP_SECP256K1_toOctet(&OCT, &(c->U), 1); + OCT_hash(&sha, &OCT); + + /* Bind to proof commitment for Receiver ZK */ + hash_ZK_commitment(&sha, &(c->zkc)); + + /* Output */ + HASH256_hash(&sha, digest); + BIG_256_56_fromBytesLen(t, digest, SHA256); + BIG_256_56_mod(t, q); + + BIG_256_56_toBytes(E->val, t); + E->len = EGS_SECP256K1; +} + +void MTA_ZKWC_prove(PAILLIER_public_key *key, MTA_ZKWC_commitment_rv *rv, octet *X, octet *Y, octet *R, octet *E, MTA_ZKWC_proof *p) +{ + MTA_ZK_prove(key, rv, X, Y, R, E, p); +} + +int MTA_ZKWC_verify(PAILLIER_private_key *key, COMMITMENTS_BC_priv_modulus *mod, octet *C1, octet *C2, octet *X, octet *E, MTA_ZKWC_commitment *c, MTA_ZKWC_proof *p) +{ + int rc; + + BIG_256_56 e; + BIG_256_56 s1; + + ECP_SECP256K1 x; + ECP_SECP256K1 g; + + BIG_1024_58 ff_s1[HFLEN_2048]; + BIG_1024_58 ff_q[HFLEN_2048]; + + char oct[HFS_2048]; + octet OCT = {0, sizeof(oct), oct}; + + char oct_s1[EGS_SECP256K1]; + octet S1 = {0, sizeof(oct_s1), oct_s1}; + + // Terminate early in case of invalid input + rc = ECP_SECP256K1_fromOctet(&x, X); + if (rc != 1) + { + return MTA_INVALID_ECP; + } + + /* Verify base Receiver ZKP */ + + rc = MTA_ZK_verify(key, mod, C1, C2, E, &(c->zkc), p); + if (rc != MTA_OK) + { + return MTA_FAIL; + } + + /* Verify knowldege of DLOG X = x.G */ + + BIG_256_56_fromBytesLen(e, E->val, E->len); + + // Reduce s1 modulo curve order + OCT_fromHex(&OCT, curve_order_hex); + FF_2048_zero(ff_q, HFLEN_2048); + BIG_1024_58_fromBytesLen(ff_q[0], OCT.val, OCT.len); + + FF_2048_copy(ff_s1, p->s1, HFLEN_2048); + FF_2048_mod(ff_s1, ff_q, HFLEN_2048); + FF_2048_toOctet(&OCT, ff_s1, HFLEN_2048); + OCT_chop(&OCT, &S1, HFS_2048 - EGS_SECP256K1); + BIG_256_56_fromBytesLen(s1, S1.val, S1.len); + + // Check U = s1.G - e.X + ECP_SECP256K1_neg(&x); + ECP_SECP256K1_generator(&g); + ECP_SECP256K1_mul2(&x, &g, e, s1); + + if (!ECP_SECP256K1_equals(&x, &(c->U))) + { + return MTA_FAIL; + } + + return MTA_OK; +} + +void MTA_ZKWC_commitment_toOctets(octet *U, octet *Z, octet *Z1, octet *T, octet *V, octet *W, MTA_ZKWC_commitment *c) +{ + MTA_ZK_commitment_toOctets(Z, Z1, T, V, W, &(c->zkc)); + ECP_SECP256K1_toOctet(U, &(c->U), 1); +} + +int MTA_ZKWC_commitment_fromOctets(MTA_ZKWC_commitment *c, octet *U, octet *Z, octet *Z1, octet *T, octet *V, octet *W) +{ + if (ECP_SECP256K1_fromOctet(&(c->U), U) != 1) + { + return MTA_INVALID_ECP; + } + + MTA_ZK_commitment_fromOctets(&(c->zkc), Z, Z1, T, V, W); + + return MTA_OK; +} + +void MTA_ZKWC_proof_toOctets(octet *S, octet *S1, octet *S2, octet *T1, octet *T2, MTA_ZKWC_proof *p) +{ + MTA_ZK_proof_toOctets(S, S1, S2, T1, T2, p); +} + +void MTA_ZKWC_proof_fromOctets(MTA_ZKWC_proof *p, octet *S, octet *S1, octet *S2, octet *T1, octet *T2) +{ + MTA_ZK_proof_fromOctets(p, S, S1, S2, T1, T2); +} + +void MTA_ZKWC_commitment_rv_kill(MTA_ZKWC_commitment_rv *rv) +{ + MTA_ZK_commitment_rv_kill(rv); +} \ No newline at end of file
