multi_party_ecdsa/utilities/zk_pdl_with_slack/
mod.rs

1#![allow(non_snake_case)]
2/*
3    Multi-party ECDSA
4
5    Copyright 2018 by Kzen Networks
6
7    This file is part of Multi-party ECDSA library
8    (https://github.com/KZen-networks/multi-party-ecdsa)
9
10    Multi-party ECDSA is free software: you can redistribute
11    it and/or modify it under the terms of the GNU General Public
12    License as published by the Free Software Foundation, either
13    version 3 of the License, or (at your option) any later version.
14
15    @license GPL-3.0+ <https://github.com/KZen-networks/multi-party-ecdsa/blob/master/LICENSE>
16*/
17
18//! We use the proof as given in proof PIi in https://eprint.iacr.org/2016/013.pdf.
19//! This proof ws taken from the proof 6.3 (left side ) in https://www.cs.unc.edu/~reiter/papers/2004/IJIS.pdf
20//!
21//! Statement: (c, pk, Q, G)
22//! witness (x, r) such that Q = xG, c = Enc(pk, x, r)
23//! note that because of the range proof, the proof has a slack in the range: x in [-q^3, q^3]
24
25use curv::arithmetic::traits::*;
26use curv::cryptographic_primitives::hashing::{Digest, DigestExt};
27use curv::elliptic::curves::{secp256_k1::Secp256k1, Point, Scalar};
28use curv::BigInt;
29use paillier::EncryptionKey;
30use serde::{Deserialize, Serialize};
31use sha2::Sha256;
32use thiserror::Error;
33
34#[derive(Error, Debug)]
35pub enum ZkPdlWithSlackError {
36    #[error("zk pdl with slack verification failed")]
37    Verify,
38}
39
40#[derive(Clone, Debug, Serialize, Deserialize)]
41pub struct PDLwSlackStatement {
42    pub ciphertext: BigInt,
43    pub ek: EncryptionKey,
44    pub Q: Point<Secp256k1>,
45    pub G: Point<Secp256k1>,
46    pub h1: BigInt,
47    pub h2: BigInt,
48    pub N_tilde: BigInt,
49}
50#[derive(Clone)]
51pub struct PDLwSlackWitness {
52    pub x: Scalar<Secp256k1>,
53    pub r: BigInt,
54}
55
56#[derive(Debug, Clone, Serialize, Deserialize)]
57pub struct PDLwSlackProof {
58    z: BigInt,
59    u1: Point<Secp256k1>,
60    u2: BigInt,
61    u3: BigInt,
62    s1: BigInt,
63    s2: BigInt,
64    s3: BigInt,
65}
66
67impl PDLwSlackProof {
68    pub fn prove(witness: &PDLwSlackWitness, statement: &PDLwSlackStatement) -> Self {
69        let q3 = Scalar::<Secp256k1>::group_order().pow(3);
70        let q_N_tilde = Scalar::<Secp256k1>::group_order() * &statement.N_tilde;
71        let q3_N_tilde = &q3 * &statement.N_tilde;
72
73        let alpha = BigInt::sample_below(&q3);
74        let one = BigInt::one();
75        let beta = BigInt::sample_range(&one, &(&statement.ek.n - &one));
76        let rho = BigInt::sample_below(&q_N_tilde);
77        let gamma = BigInt::sample_below(&q3_N_tilde);
78
79        let z = commitment_unknown_order(
80            &statement.h1,
81            &statement.h2,
82            &statement.N_tilde,
83            &witness.x.to_bigint(),
84            &rho,
85        );
86        let u1 = &statement.G * &Scalar::<Secp256k1>::from(&alpha);
87        let u2 = commitment_unknown_order(
88            &(&statement.ek.n + BigInt::one()),
89            &beta,
90            &statement.ek.nn,
91            &alpha,
92            &statement.ek.n,
93        );
94        let u3 = commitment_unknown_order(
95            &statement.h1,
96            &statement.h2,
97            &statement.N_tilde,
98            &alpha,
99            &gamma,
100        );
101
102        let e = Sha256::new()
103            .chain_bigint(&BigInt::from_bytes(statement.G.to_bytes(true).as_ref()))
104            .chain_bigint(&BigInt::from_bytes(statement.Q.to_bytes(true).as_ref()))
105            .chain_bigint(&statement.ciphertext)
106            .chain_bigint(&z)
107            .chain_bigint(&BigInt::from_bytes(u1.to_bytes(true).as_ref()))
108            .chain_bigint(&u2)
109            .chain_bigint(&u3)
110            .result_bigint();
111
112        let s1 = &e * witness.x.to_bigint() + alpha;
113        let s2 = commitment_unknown_order(&witness.r, &beta, &statement.ek.n, &e, &BigInt::one());
114        let s3 = &e * rho + gamma;
115
116        PDLwSlackProof {
117            z,
118            u1,
119            u2,
120            u3,
121            s1,
122            s2,
123            s3,
124        }
125    }
126
127    pub fn verify(&self, statement: &PDLwSlackStatement) -> Result<(), ZkPdlWithSlackError> {
128        let e = Sha256::new()
129            .chain_bigint(&BigInt::from_bytes(statement.G.to_bytes(true).as_ref()))
130            .chain_bigint(&BigInt::from_bytes(statement.Q.to_bytes(true).as_ref()))
131            .chain_bigint(&statement.ciphertext)
132            .chain_bigint(&self.z)
133            .chain_bigint(&BigInt::from_bytes(self.u1.to_bytes(true).as_ref()))
134            .chain_bigint(&self.u2)
135            .chain_bigint(&self.u3)
136            .result_bigint();
137
138        let g_s1 = statement.G.clone() * &Scalar::<Secp256k1>::from(&self.s1);
139        let e_fe_neg: Scalar<Secp256k1> =
140            Scalar::<Secp256k1>::from(&(Scalar::<Secp256k1>::group_order() - &e));
141        let y_minus_e = &statement.Q * &e_fe_neg;
142        let u1_test = g_s1 + y_minus_e;
143
144        let u2_test_tmp = commitment_unknown_order(
145            &(&statement.ek.n + BigInt::one()),
146            &self.s2,
147            &statement.ek.nn,
148            &self.s1,
149            &statement.ek.n,
150        );
151        let u2_test = commitment_unknown_order(
152            &u2_test_tmp,
153            &statement.ciphertext,
154            &statement.ek.nn,
155            &BigInt::one(),
156            &(-&e),
157        );
158
159        let u3_test_tmp = commitment_unknown_order(
160            &statement.h1,
161            &statement.h2,
162            &statement.N_tilde,
163            &self.s1,
164            &self.s3,
165        );
166        let u3_test = commitment_unknown_order(
167            &u3_test_tmp,
168            &self.z,
169            &statement.N_tilde,
170            &BigInt::one(),
171            &(-&e),
172        );
173
174        if self.u1 == u1_test && self.u2 == u2_test && self.u3 == u3_test {
175            Ok(())
176        } else {
177            Err(ZkPdlWithSlackError::Verify)
178        }
179    }
180}
181
182pub fn commitment_unknown_order(
183    h1: &BigInt,
184    h2: &BigInt,
185    N_tilde: &BigInt,
186    x: &BigInt,
187    r: &BigInt,
188) -> BigInt {
189    let h1_x = BigInt::mod_pow(h1, x, N_tilde);
190    let h2_r = {
191        if r < &BigInt::zero() {
192            let h2_inv = BigInt::mod_inv(h2, N_tilde).unwrap();
193            BigInt::mod_pow(&h2_inv, &(-r), N_tilde)
194        } else {
195            BigInt::mod_pow(h2, r, N_tilde)
196        }
197    };
198    BigInt::mod_mul(&h1_x, &h2_r, N_tilde)
199}
200
201#[cfg(test)]
202mod test;
multi_party_ecdsa/utilities/zk_pdl_with_slack/mod.rs

multi_party_ecdsa/utilities/zk_pdl_with_slack/
mod.rs
