multi_party_ecdsa/utilities/mta/
range_proofs.rs

1#![allow(non_snake_case)]
2
3//! This file is a modified version of ING bank's range proofs implementation:
4//! https://github.com/ing-bank/threshold-signatures/blob/master/src/algorithms/zkp.rs
5//!
6//! Zero knowledge range proofs for MtA protocol are implemented here.
7//! Formal description can be found in Appendix A of https://eprint.iacr.org/2019/114.pdf
8//! There are some deviations from the original specification:
9//! 1) In Bob's proofs `gamma` is sampled from `[0;q^2 * N]` and `tau` from `[0;q^3 * N_tilde]`.
10//! 2) A non-interactive version is implemented, with challenge `e` computed via Fiat-Shamir.
11
12use curv::arithmetic::traits::*;
13use curv::cryptographic_primitives::hashing::{Digest, DigestExt};
14use curv::elliptic::curves::{secp256_k1::Secp256k1, Point, Scalar};
15use curv::BigInt;
16use sha2::Sha256;
17
18use paillier::{EncryptionKey, Randomness};
19use zk_paillier::zkproofs::DLogStatement;
20
21use serde::{Deserialize, Serialize};
22use std::borrow::Borrow;
23use zeroize::Zeroize;
24
25/// Represents the first round of the interactive version of the proof
26#[derive(Zeroize)]
27#[zeroize(drop)]
28struct AliceZkpRound1 {
29    alpha: BigInt,
30    beta: BigInt,
31    gamma: BigInt,
32    ro: BigInt,
33    z: BigInt,
34    u: BigInt,
35    w: BigInt,
36}
37
38impl AliceZkpRound1 {
39    fn from(
40        alice_ek: &EncryptionKey,
41        dlog_statement: &DLogStatement,
42        a: &BigInt,
43        q: &BigInt,
44    ) -> Self {
45        let h1 = &dlog_statement.g;
46        let h2 = &dlog_statement.ni;
47        let N_tilde = &dlog_statement.N;
48        let alpha = BigInt::sample_below(&q.pow(3));
49        let beta = BigInt::from_paillier_key(alice_ek);
50        let gamma = BigInt::sample_below(&(q.pow(3) * N_tilde));
51        let ro = BigInt::sample_below(&(q * N_tilde));
52        let z = (BigInt::mod_pow(h1, a, N_tilde) * BigInt::mod_pow(h2, &ro, N_tilde)) % N_tilde;
53        let u = ((alpha.borrow() * &alice_ek.n + 1)
54            * BigInt::mod_pow(&beta, &alice_ek.n, &alice_ek.nn))
55            % &alice_ek.nn;
56        let w =
57            (BigInt::mod_pow(h1, &alpha, N_tilde) * BigInt::mod_pow(h2, &gamma, N_tilde)) % N_tilde;
58        Self {
59            alpha,
60            beta,
61            gamma,
62            ro,
63            z,
64            u,
65            w,
66        }
67    }
68}
69
70/// Represents the second round of the interactive version of the proof
71struct AliceZkpRound2 {
72    s: BigInt,
73    s1: BigInt,
74    s2: BigInt,
75}
76
77impl AliceZkpRound2 {
78    fn from(
79        alice_ek: &EncryptionKey,
80        round1: &AliceZkpRound1,
81        e: &BigInt,
82        a: &BigInt,
83        r: &BigInt,
84    ) -> Self {
85        Self {
86            s: (BigInt::mod_pow(r, e, &alice_ek.n) * round1.beta.borrow()) % &alice_ek.n,
87            s1: (e * a) + round1.alpha.borrow(),
88            s2: (e * round1.ro.borrow()) + round1.gamma.borrow(),
89        }
90    }
91}
92
93/// Alice's proof
94#[derive(Debug, Clone, Serialize, Deserialize)]
95pub struct AliceProof {
96    z: BigInt,
97    e: BigInt,
98    s: BigInt,
99    s1: BigInt,
100    s2: BigInt,
101}
102
103impl AliceProof {
104    /// verify Alice's proof using the proof and public keys
105    pub fn verify(
106        &self,
107        cipher: &BigInt,
108        alice_ek: &EncryptionKey,
109        dlog_statement: &DLogStatement,
110    ) -> bool {
111        let N = &alice_ek.n;
112        let NN = &alice_ek.nn;
113        let N_tilde = &dlog_statement.N;
114        let h1 = &dlog_statement.g;
115        let h2 = &dlog_statement.ni;
116        let Gen = alice_ek.n.borrow() + 1;
117
118        if self.s1 > Scalar::<Secp256k1>::group_order().pow(3) {
119            return false;
120        }
121
122        let z_e_inv = BigInt::mod_inv(&BigInt::mod_pow(&self.z, &self.e, N_tilde), N_tilde);
123        let z_e_inv = match z_e_inv {
124            // z must be invertible, yet the check is done here
125            None => return false,
126            Some(c) => c,
127        };
128
129        let w = (BigInt::mod_pow(h1, &self.s1, N_tilde)
130            * BigInt::mod_pow(h2, &self.s2, N_tilde)
131            * z_e_inv)
132            % N_tilde;
133
134        let gs1 = (self.s1.borrow() * N + 1) % NN;
135        let cipher_e_inv = BigInt::mod_inv(&BigInt::mod_pow(cipher, &self.e, NN), NN);
136        let cipher_e_inv = match cipher_e_inv {
137            None => return false,
138            Some(c) => c,
139        };
140
141        let u = (gs1 * BigInt::mod_pow(&self.s, N, NN) * cipher_e_inv) % NN;
142
143        let e = Sha256::new()
144            .chain_bigint(N)
145            .chain_bigint(&Gen)
146            .chain_bigint(cipher)
147            .chain_bigint(&self.z)
148            .chain_bigint(&u)
149            .chain_bigint(&w)
150            .result_bigint();
151        if e != self.e {
152            return false;
153        }
154
155        true
156    }
157    /// Create the proof using Alice's Paillier private keys and public ZKP setup.
158    /// Requires randomness used for encrypting Alice's secret a.
159    /// It is assumed that secp256k1 curve is used.
160    pub fn generate(
161        a: &BigInt,
162        cipher: &BigInt,
163        alice_ek: &EncryptionKey,
164        dlog_statement: &DLogStatement,
165        r: &BigInt,
166    ) -> Self {
167        let round1 = AliceZkpRound1::from(
168            alice_ek,
169            dlog_statement,
170            a,
171            Scalar::<Secp256k1>::group_order(),
172        );
173
174        let Gen = alice_ek.n.borrow() + 1;
175        let e = Sha256::new()
176            .chain_bigint(&alice_ek.n)
177            .chain_bigint(&Gen)
178            .chain_bigint(cipher)
179            .chain_bigint(&round1.z)
180            .chain_bigint(&round1.u)
181            .chain_bigint(&round1.w)
182            .result_bigint();
183
184        let round2 = AliceZkpRound2::from(alice_ek, &round1, &e, a, r);
185
186        Self {
187            z: round1.z.clone(),
188            e,
189            s: round2.s,
190            s1: round2.s1,
191            s2: round2.s2,
192        }
193    }
194}
195
196/// Represents first round of the interactive version of the proof
197#[derive(Zeroize)]
198#[zeroize(drop)]
199struct BobZkpRound1 {
200    pub alpha: BigInt,
201    pub beta: BigInt,
202    pub gamma: BigInt,
203    pub ro: BigInt,
204    pub ro_prim: BigInt,
205    pub sigma: BigInt,
206    pub tau: BigInt,
207    pub z: BigInt,
208    pub z_prim: BigInt,
209    pub t: BigInt,
210    pub w: BigInt,
211    pub v: BigInt,
212}
213
214impl BobZkpRound1 {
215    /// `b` - Bob's secret
216    /// `beta_prim`  - randomly chosen in `MtA` by Bob
217    /// `a_encrypted` - Alice's secret encrypted by Alice
218    fn from(
219        alice_ek: &EncryptionKey,
220        dlog_statement: &DLogStatement,
221        b: &Scalar<Secp256k1>,
222        beta_prim: &BigInt,
223        a_encrypted: &BigInt,
224        q: &BigInt,
225    ) -> Self {
226        let h1 = &dlog_statement.g;
227        let h2 = &dlog_statement.ni;
228        let N_tilde = &dlog_statement.N;
229        let b_bn = b.to_bigint();
230
231        let alpha = BigInt::sample_below(&q.pow(3));
232        let beta = BigInt::from_paillier_key(alice_ek);
233        let gamma = BigInt::sample_below(&(q.pow(2) * &alice_ek.n));
234        let ro = BigInt::sample_below(&(q * N_tilde));
235        let ro_prim = BigInt::sample_below(&(q.pow(3) * N_tilde));
236        let sigma = BigInt::sample_below(&(q * N_tilde));
237        let tau = BigInt::sample_below(&(q.pow(3) * N_tilde));
238        let z = (BigInt::mod_pow(h1, &b_bn, N_tilde) * BigInt::mod_pow(h2, &ro, N_tilde)) % N_tilde;
239        let z_prim = (BigInt::mod_pow(h1, &alpha, N_tilde)
240            * BigInt::mod_pow(h2, &ro_prim, N_tilde))
241            % N_tilde;
242        let t = (BigInt::mod_pow(h1, beta_prim, N_tilde) * BigInt::mod_pow(h2, &sigma, N_tilde))
243            % N_tilde;
244        let w =
245            (BigInt::mod_pow(h1, &gamma, N_tilde) * BigInt::mod_pow(h2, &tau, N_tilde)) % N_tilde;
246        let v = (BigInt::mod_pow(a_encrypted, &alpha, &alice_ek.nn)
247            * (gamma.borrow() * &alice_ek.n + 1)
248            * BigInt::mod_pow(&beta, &alice_ek.n, &alice_ek.nn))
249            % &alice_ek.nn;
250        Self {
251            alpha,
252            beta,
253            gamma,
254            ro,
255            ro_prim,
256            sigma,
257            tau,
258            z,
259            z_prim,
260            t,
261            w,
262            v,
263        }
264    }
265}
266
267/// represents second round of the interactive version of the proof
268struct BobZkpRound2 {
269    pub s: BigInt,
270    pub s1: BigInt,
271    pub s2: BigInt,
272    pub t1: BigInt,
273    pub t2: BigInt,
274}
275
276impl BobZkpRound2 {
277    /// `e` - the challenge in interactive ZKP, the hash in non-interactive ZKP
278    /// `b` - Bob's secret
279    /// `beta_prim` - randomly chosen in `MtA` by Bob
280    /// `r` - randomness used by Bob on  Alice's public Paillier key to encrypt `beta_prim` in `MtA`
281    fn from(
282        alice_ek: &EncryptionKey,
283        round1: &BobZkpRound1,
284        e: &BigInt,
285        b: &Scalar<Secp256k1>,
286        beta_prim: &BigInt,
287        r: &Randomness,
288    ) -> Self {
289        let b_bn = b.to_bigint();
290        Self {
291            s: (BigInt::mod_pow(r.0.borrow(), e, &alice_ek.n) * round1.beta.borrow()) % &alice_ek.n,
292            s1: (e * b_bn) + round1.alpha.borrow(),
293            s2: (e * round1.ro.borrow()) + round1.ro_prim.borrow(),
294            t1: (e * beta_prim) + round1.gamma.borrow(),
295            t2: (e * round1.sigma.borrow()) + round1.tau.borrow(),
296        }
297    }
298}
299
300/// Additional fields in Bob's proof if MtA is run with check
301pub struct BobCheck {
302    u: Point<Secp256k1>,
303    X: Point<Secp256k1>,
304}
305
306/// Bob's regular proof
307#[derive(Clone, PartialEq, Debug, Serialize, Deserialize)]
308pub struct BobProof {
309    t: BigInt,
310    z: BigInt,
311    e: BigInt,
312    s: BigInt,
313    s1: BigInt,
314    s2: BigInt,
315    t1: BigInt,
316    t2: BigInt,
317}
318
319#[allow(clippy::too_many_arguments)]
320impl BobProof {
321    pub fn verify(
322        &self,
323        a_enc: &BigInt,
324        mta_avc_out: &BigInt,
325        alice_ek: &EncryptionKey,
326        dlog_statement: &DLogStatement,
327        check: Option<&BobCheck>,
328    ) -> bool {
329        let N = &alice_ek.n;
330        let NN = &alice_ek.nn;
331        let N_tilde = &dlog_statement.N;
332        let h1 = &dlog_statement.g;
333        let h2 = &dlog_statement.ni;
334
335        if self.s1 > Scalar::<Secp256k1>::group_order().pow(3) {
336            return false;
337        }
338
339        let z_e_inv = BigInt::mod_inv(&BigInt::mod_pow(&self.z, &self.e, N_tilde), N_tilde);
340        let z_e_inv = match z_e_inv {
341            // z must be invertible, yet the check is done here
342            None => return false,
343            Some(c) => c,
344        };
345
346        let z_prim = (BigInt::mod_pow(h1, &self.s1, N_tilde)
347            * BigInt::mod_pow(h2, &self.s2, N_tilde)
348            * z_e_inv)
349            % N_tilde;
350
351        let mta_e_inv = BigInt::mod_inv(&BigInt::mod_pow(mta_avc_out, &self.e, NN), NN);
352        let mta_e_inv = match mta_e_inv {
353            None => return false,
354            Some(c) => c,
355        };
356
357        let v = (BigInt::mod_pow(a_enc, &self.s1, NN)
358            * BigInt::mod_pow(&self.s, N, NN)
359            * (self.t1.borrow() * N + 1)
360            * mta_e_inv)
361            % NN;
362
363        let t_e_inv = BigInt::mod_inv(&BigInt::mod_pow(&self.t, &self.e, N_tilde), N_tilde);
364        let t_e_inv = match t_e_inv {
365            None => return false,
366            Some(c) => c,
367        };
368
369        let w = (BigInt::mod_pow(h1, &self.t1, N_tilde)
370            * BigInt::mod_pow(h2, &self.t2, N_tilde)
371            * t_e_inv)
372            % N_tilde;
373
374        let Gen = alice_ek.n.borrow() + 1;
375        let mut values_to_hash = vec![
376            &alice_ek.n,
377            &Gen,
378            a_enc,
379            mta_avc_out,
380            &self.z,
381            &z_prim,
382            &self.t,
383            &v,
384            &w,
385        ];
386        let e = match check {
387            Some(_) => {
388                let X_x_coor = check.unwrap().X.x_coord().unwrap();
389                values_to_hash.push(&X_x_coor);
390                let X_y_coor = check.unwrap().X.y_coord().unwrap();
391                values_to_hash.push(&X_y_coor);
392                let u_x_coor = check.unwrap().u.x_coord().unwrap();
393                values_to_hash.push(&u_x_coor);
394                let u_y_coor = check.unwrap().u.y_coord().unwrap();
395                values_to_hash.push(&u_y_coor);
396                values_to_hash
397                    .into_iter()
398                    .fold(Sha256::new(), |acc, b| acc.chain_bigint(b))
399                    .result_bigint()
400            }
401            None => values_to_hash
402                .into_iter()
403                .fold(Sha256::new(), |acc, b| acc.chain_bigint(b))
404                .result_bigint(),
405        };
406
407        if e != self.e {
408            return false;
409        }
410
411        true
412    }
413
414    pub fn generate(
415        a_encrypted: &BigInt,
416        mta_encrypted: &BigInt,
417        b: &Scalar<Secp256k1>,
418        beta_prim: &BigInt,
419        alice_ek: &EncryptionKey,
420        dlog_statement: &DLogStatement,
421        r: &Randomness,
422        check: bool,
423    ) -> (BobProof, Option<Point<Secp256k1>>) {
424        let round1 = BobZkpRound1::from(
425            alice_ek,
426            dlog_statement,
427            b,
428            beta_prim,
429            a_encrypted,
430            Scalar::<Secp256k1>::group_order(),
431        );
432
433        let Gen = alice_ek.n.borrow() + 1;
434        let mut values_to_hash = vec![
435            &alice_ek.n,
436            &Gen,
437            a_encrypted,
438            mta_encrypted,
439            &round1.z,
440            &round1.z_prim,
441            &round1.t,
442            &round1.v,
443            &round1.w,
444        ];
445        let mut check_u = None;
446        let e = if check {
447            let (X, u) = {
448                let ec_gen = Point::generator();
449                let alpha = Scalar::<Secp256k1>::from(&round1.alpha);
450                (ec_gen * b, ec_gen * alpha)
451            };
452            check_u = Some(u.clone());
453            let X_x_coor = X.x_coord().unwrap();
454            values_to_hash.push(&X_x_coor);
455            let X_y_coor = X.y_coord().unwrap();
456            values_to_hash.push(&X_y_coor);
457            let u_x_coor = u.x_coord().unwrap();
458            values_to_hash.push(&u_x_coor);
459            let u_y_coor = u.y_coord().unwrap();
460            values_to_hash.push(&u_y_coor);
461            values_to_hash
462                .into_iter()
463                .fold(Sha256::new(), |acc, b| acc.chain_bigint(b))
464                .result_bigint()
465        } else {
466            values_to_hash
467                .into_iter()
468                .fold(Sha256::new(), |acc, b| acc.chain_bigint(b))
469                .result_bigint()
470        };
471
472        let round2 = BobZkpRound2::from(alice_ek, &round1, &e, b, beta_prim, r);
473
474        (
475            BobProof {
476                t: round1.t.clone(),
477                z: round1.z.clone(),
478                e,
479                s: round2.s,
480                s1: round2.s1,
481                s2: round2.s2,
482                t1: round2.t1,
483                t2: round2.t2,
484            },
485            check_u,
486        )
487    }
488}
489
490/// Bob's extended proof, adds the knowledge of $`B = g^b \in \mathcal{G}`$
491#[derive(Clone, PartialEq, Debug, Serialize, Deserialize)]
492pub struct BobProofExt {
493    proof: BobProof,
494    u: Point<Secp256k1>,
495}
496
497#[allow(clippy::too_many_arguments)]
498impl BobProofExt {
499    pub fn verify(
500        &self,
501        a_enc: &BigInt,
502        mta_avc_out: &BigInt,
503        alice_ek: &EncryptionKey,
504        dlog_statement: &DLogStatement,
505        X: &Point<Secp256k1>,
506    ) -> bool {
507        // check basic proof first
508        if !self.proof.verify(
509            a_enc,
510            mta_avc_out,
511            alice_ek,
512            dlog_statement,
513            Some(&BobCheck {
514                u: self.u.clone(),
515                X: X.clone(),
516            }),
517        ) {
518            return false;
519        }
520
521        // fiddle with EC points
522        let (x1, x2) = {
523            let ec_gen = Point::generator();
524            let s1 = Scalar::<Secp256k1>::from(&self.proof.s1);
525            let e = Scalar::<Secp256k1>::from(&self.proof.e);
526            (ec_gen * s1, (X * &e) + &self.u)
527        };
528
529        if x1 != x2 {
530            return false;
531        }
532
533        true
534    }
535}
536
537/// sample random value of an element of a multiplicative group
538pub trait SampleFromMultiplicativeGroup {
539    fn from_modulo(N: &BigInt) -> BigInt;
540    fn from_paillier_key(ek: &EncryptionKey) -> BigInt;
541}
542
543impl SampleFromMultiplicativeGroup for BigInt {
544    fn from_modulo(N: &BigInt) -> BigInt {
545        let One = BigInt::one();
546        loop {
547            let r = Self::sample_below(N);
548            if r.gcd(N) == One {
549                return r;
550            }
551        }
552    }
553
554    fn from_paillier_key(ek: &EncryptionKey) -> BigInt {
555        Self::from_modulo(ek.n.borrow())
556    }
557}
558
559#[cfg(test)]
560pub(crate) mod tests {
561    use super::*;
562    use paillier::traits::{Encrypt, EncryptWithChosenRandomness, KeyGeneration};
563    use paillier::{Add, DecryptionKey, Mul, Paillier, RawCiphertext, RawPlaintext};
564
565    fn generate(
566        a_encrypted: &BigInt,
567        mta_encrypted: &BigInt,
568        b: &Scalar<Secp256k1>,
569        beta_prim: &BigInt,
570        alice_ek: &EncryptionKey,
571        dlog_statement: &DLogStatement,
572        r: &Randomness,
573    ) -> BobProofExt {
574        // proving a basic proof (with modified hash)
575        let (bob_proof, u) = BobProof::generate(
576            a_encrypted,
577            mta_encrypted,
578            b,
579            beta_prim,
580            alice_ek,
581            dlog_statement,
582            r,
583            true,
584        );
585
586        BobProofExt {
587            proof: bob_proof,
588            u: u.unwrap(),
589        }
590    }
591
592    pub(crate) fn generate_init() -> (DLogStatement, EncryptionKey, DecryptionKey) {
593        let (ek_tilde, dk_tilde) = Paillier::keypair().keys();
594        let one = BigInt::one();
595        let phi = (&dk_tilde.p - &one) * (&dk_tilde.q - &one);
596        let h1 = BigInt::sample_below(&ek_tilde.n);
597        let (xhi, _) = loop {
598            let xhi_ = BigInt::sample_below(&phi);
599            match BigInt::mod_inv(&xhi_, &phi) {
600                Some(inv) => break (xhi_, inv),
601                None => continue,
602            }
603        };
604        let h2 = BigInt::mod_pow(&h1, &xhi, &ek_tilde.n);
605
606        let (ek, dk) = Paillier::keypair().keys();
607        let dlog_statement = DLogStatement {
608            g: h1,
609            ni: h2,
610            N: ek_tilde.n,
611        };
612        (dlog_statement, ek, dk)
613    }
614
615    #[test]
616    fn alice_zkp() {
617        let (dlog_statement, ek, _) = generate_init();
618
619        // Alice's secret value
620        let a = Scalar::<Secp256k1>::random().to_bigint();
621        let r = BigInt::from_paillier_key(&ek);
622        let cipher = Paillier::encrypt_with_chosen_randomness(
623            &ek,
624            RawPlaintext::from(a.clone()),
625            &Randomness::from(&r),
626        )
627        .0
628        .clone()
629        .into_owned();
630
631        let alice_proof = AliceProof::generate(&a, &cipher, &ek, &dlog_statement, &r);
632
633        assert!(alice_proof.verify(&cipher, &ek, &dlog_statement));
634    }
635
636    #[test]
637    fn bob_zkp() {
638        let (dlog_statement, ek, _) = generate_init();
639
640        (0..5).for_each(|_| {
641            let alice_public_key = &ek;
642
643            // run MtA protocol with different inputs
644            (0..5).for_each(|_| {
645                // Simulate Alice
646                let a = Scalar::<Secp256k1>::random().to_bigint();
647                let encrypted_a = Paillier::encrypt(alice_public_key, RawPlaintext::from(a))
648                    .0
649                    .clone()
650                    .into_owned();
651
652                // Bob follows MtA
653                let b = Scalar::<Secp256k1>::random();
654                // E(a) * b
655                let b_times_enc_a = Paillier::mul(
656                    alice_public_key,
657                    RawCiphertext::from(encrypted_a.clone()),
658                    RawPlaintext::from(&b.to_bigint()),
659                );
660                let beta_prim = BigInt::sample_below(&alice_public_key.n);
661                let r = Randomness::sample(alice_public_key);
662                let enc_beta_prim = Paillier::encrypt_with_chosen_randomness(
663                    alice_public_key,
664                    RawPlaintext::from(&beta_prim),
665                    &r,
666                );
667
668                let mta_out = Paillier::add(alice_public_key, b_times_enc_a, enc_beta_prim);
669
670                let (bob_proof, _) = BobProof::generate(
671                    &encrypted_a,
672                    &mta_out.0.clone().into_owned(),
673                    &b,
674                    &beta_prim,
675                    alice_public_key,
676                    &dlog_statement,
677                    &r,
678                    false,
679                );
680                assert!(bob_proof.verify(
681                    &encrypted_a,
682                    &mta_out.0.clone().into_owned(),
683                    alice_public_key,
684                    &dlog_statement,
685                    None
686                ));
687
688                // Bob follows MtAwc
689                let ec_gen = Point::generator();
690                let X = ec_gen * &b;
691                let bob_proof = generate(
692                    &encrypted_a,
693                    &mta_out.0.clone().into_owned(),
694                    &b,
695                    &beta_prim,
696                    alice_public_key,
697                    &dlog_statement,
698                    &r,
699                );
700                assert!(bob_proof.verify(
701                    &encrypted_a,
702                    &mta_out.0.clone().into_owned(),
703                    alice_public_key,
704                    &dlog_statement,
705                    &X
706                ));
707            });
708        });
709    }
710}
multi_party_ecdsa/utilities/mta/range_proofs.rs

multi_party_ecdsa/utilities/mta/
range_proofs.rs
