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 12:57:25 UTC
[incubator-milagro-MPC] 05/11: Add mtawc zkp
This is an automated email from the ASF dual-hosted git repository.
sandreoli pushed a commit to branch add-mta-zk-proofs
in repository https://gitbox.apache.org/repos/asf/incubator-milagro-MPC.git
commit 10a191a1dbbfd003ae61b5e3d96ad6108cc2eca6
Author: Samuele Andreoli <sa...@yahoo.it>
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