zk_paillier/zkproofs/
range_proof.rs

1/*
2    zk-paillier
3
4    Copyright 2018 by Kzen Networks
5
6    zk-paillier is free software: you can redistribute
7    it and/or modify it under the terms of the GNU General Public
8    License as published by the Free Software Foundation, either
9    version 3 of the License, or (at your option) any later version.
10
11    @license GPL-3.0+ <https://github.com/KZen-networks/zk-paillier/blob/master/LICENSE>
12*/
13use std::borrow::Borrow;
14use std::mem;
15
16use bit_vec::BitVec;
17use curv::arithmetic::traits::*;
18use curv::cryptographic_primitives::hashing::DigestExt;
19use curv::BigInt;
20use paillier::EncryptWithChosenRandomness;
21use paillier::Paillier;
22use paillier::{EncryptionKey, Randomness, RawCiphertext, RawPlaintext};
23use rand::prelude::*;
24use rayon::prelude::*;
25use serde::{Deserialize, Serialize};
26use sha2::{Digest, Sha256};
27
28use super::errors::IncorrectProof;
29
30const STATISTICAL_ERROR_FACTOR: usize = 40;
31
32#[derive(Default, Debug, Serialize, Deserialize, Clone)]
33pub struct EncryptedPairs {
34    #[serde(with = "crate::serialize::vecbigint")]
35    pub c1: Vec<BigInt>, // TODO[Morten] should not need to be public
36
37    #[serde(with = "crate::serialize::vecbigint")]
38    pub c2: Vec<BigInt>, // TODO[Morten] should not need to be public
39}
40
41#[derive(Default)]
42pub struct DataRandomnessPairs {
43    w1: Vec<BigInt>,
44    w2: Vec<BigInt>,
45    r1: Vec<BigInt>,
46    r2: Vec<BigInt>,
47}
48
49#[derive(Debug, Serialize, Deserialize)]
50pub struct ChallengeBits(Vec<u8>);
51
52// TODO[Morten] find better name
53#[derive(Debug, Serialize, Deserialize, Clone)]
54pub enum Response {
55    Open {
56        #[serde(with = "crate::serialize::bigint")]
57        w1: BigInt,
58
59        #[serde(with = "crate::serialize::bigint")]
60        r1: BigInt,
61
62        #[serde(with = "crate::serialize::bigint")]
63        w2: BigInt,
64
65        #[serde(with = "crate::serialize::bigint")]
66        r2: BigInt,
67    },
68
69    Mask {
70        j: u8,
71
72        #[serde(with = "crate::serialize::bigint")]
73        masked_x: BigInt,
74
75        #[serde(with = "crate::serialize::bigint")]
76        masked_r: BigInt,
77    },
78}
79
80#[derive(Debug, Serialize, Deserialize, Clone)]
81pub struct Proof(Vec<Response>);
82
83pub struct Commitment(BigInt);
84
85impl ChallengeBits {
86    fn sample(big_length: usize) -> ChallengeBits {
87        let mut rng = thread_rng();
88        let mut bytes: Vec<u8> = vec![0; big_length / 8];
89        rng.fill_bytes(&mut bytes);
90        ChallengeBits(bytes)
91    }
92}
93
94impl From<Vec<u8>> for ChallengeBits {
95    fn from(x: Vec<u8>) -> Self {
96        ChallengeBits(x)
97    }
98}
99
100pub struct ChallengeRandomness(BigInt);
101
102/// Zero-knowledge range proof that a value x<q/3 lies in interval [0,q].
103///
104/// The verifier is given only c = ENC(ek,x).
105/// The prover has input x, dk, r (randomness used for calculating c)
106/// It is assumed that q is known to both.
107///
108/// References:
109/// - Appendix A in [Lindell'17](https://eprint.iacr.org/2017/552)
110/// - Section 1.2.2 in [Boudot '00](https://www.iacr.org/archive/eurocrypt2000/1807/18070437-new.pdf)
111///
112///
113/// This is an interactive version of the proof, assuming only DCRA which is alreasy assumed for
114/// Paillier cryptosystem security
115pub struct RangeProof;
116
117impl RangeProof {
118    pub fn verifier_commit(ek: &EncryptionKey) -> (Commitment, ChallengeRandomness, ChallengeBits) {
119        let e = ChallengeBits::sample(STATISTICAL_ERROR_FACTOR);
120        // commit to challenge
121        let m = compute_digest(&e.0);
122        let r = BigInt::sample_below(&ek.n);
123        let com = get_paillier_commitment(ek, &m, &r);
124
125        (Commitment(com), ChallengeRandomness(r), e)
126    }
127
128    pub fn generate_encrypted_pairs(
129        ek: &EncryptionKey,
130        range: &BigInt,
131        error_factor: usize,
132    ) -> (EncryptedPairs, DataRandomnessPairs) {
133        let range_scaled_third = range.div_floor(&BigInt::from(3));
134        let range_scaled_two_thirds = BigInt::from(2) * &range_scaled_third;
135
136        let mut w1: Vec<_> = (0..error_factor)
137            .into_par_iter()
138            .map(|_| BigInt::sample_range(&range_scaled_third, &range_scaled_two_thirds))
139            .collect();
140
141        let mut w2: Vec<_> = w1.par_iter().map(|x| x - &range_scaled_third).collect();
142
143        // with probability 1/2 switch between w1i and w2i
144        for i in 0..error_factor {
145            // TODO[Morten] need secure randomness?
146            if random() {
147                mem::swap(&mut w2[i], &mut w1[i]);
148            }
149        }
150
151        let r1: Vec<_> = (0..error_factor)
152            .into_par_iter()
153            .map(|_| BigInt::sample_below(&ek.n))
154            .collect();
155
156        let r2: Vec<_> = (0..error_factor)
157            .into_par_iter()
158            .map(|_| BigInt::sample_below(&ek.n))
159            .collect();
160
161        let c1: Vec<_> = w1
162            .par_iter()
163            .zip(&r1)
164            .map(|(wi, ri)| {
165                Paillier::encrypt_with_chosen_randomness(
166                    ek,
167                    RawPlaintext::from(wi),
168                    &Randomness::from(ri),
169                )
170                .0
171                .into_owned()
172            })
173            .collect();
174
175        let c2: Vec<_> = w2
176            .par_iter()
177            .zip(&r2)
178            .map(|(wi, ri)| {
179                Paillier::encrypt_with_chosen_randomness(
180                    ek,
181                    RawPlaintext::from(wi),
182                    &Randomness::from(ri),
183                )
184                .0
185                .into_owned()
186            })
187            .collect();
188
189        (
190            EncryptedPairs { c1, c2 },
191            DataRandomnessPairs { w1, w2, r1, r2 },
192        )
193    }
194
195    pub fn verify_commit(
196        ek: &EncryptionKey,
197        com: &Commitment,
198        r: &ChallengeRandomness,
199        e: &ChallengeBits,
200    ) -> Result<(), IncorrectProof> {
201        let m = compute_digest(&e.0);
202        let com_tag = get_paillier_commitment(ek, &m, &r.0);
203        if com.0 == com_tag {
204            Ok(())
205        } else {
206            Err(IncorrectProof)
207        }
208    }
209
210    pub fn generate_proof(
211        ek: &EncryptionKey,
212        secret_x: &BigInt,
213        secret_r: &BigInt,
214        e: &ChallengeBits,
215        range: &BigInt,
216        data: &DataRandomnessPairs,
217        error_factor: usize,
218    ) -> Proof {
219        let range_scaled_third: BigInt = range.div_floor(&BigInt::from(3));
220        let range_scaled_two_thirds = BigInt::from(2) * &range_scaled_third;
221        let bits_of_e = BitVec::from_bytes(&e.0);
222        let reponses: Vec<_> = (0..error_factor)
223            .into_par_iter()
224            .map(|i| {
225                let ei = bits_of_e[i];
226                if !ei {
227                    Response::Open {
228                        w1: data.w1[i].clone(),
229                        r1: data.r1[i].clone(),
230                        w2: data.w2[i].clone(),
231                        r2: data.r2[i].clone(),
232                    }
233                } else if secret_x + &data.w1[i] > range_scaled_third
234                    && secret_x + &data.w1[i] < range_scaled_two_thirds
235                {
236                    Response::Mask {
237                        j: 1,
238                        masked_x: secret_x + &data.w1[i],
239                        masked_r: secret_r * &data.r1[i] % &ek.n,
240                    }
241                } else {
242                    Response::Mask {
243                        j: 2,
244                        masked_x: secret_x + &data.w2[i],
245                        masked_r: secret_r * &data.r2[i] % &ek.n,
246                    }
247                }
248            })
249            .collect();
250
251        Proof(reponses)
252    }
253
254    pub fn verifier_output(
255        ek: &EncryptionKey,
256        e: &ChallengeBits,
257        encrypted_pairs: &EncryptedPairs,
258        proof: &Proof,
259        range: &BigInt,
260        cipher_x: &BigInt,
261        error_factor: usize,
262    ) -> Result<(), IncorrectProof> {
263        let cipher_x_raw = RawCiphertext::from(cipher_x);
264        let range_scaled_third: BigInt = range.div_floor(&BigInt::from(3i32));
265        let range_scaled_two_thirds: BigInt = BigInt::from(2i32) * &range_scaled_third;
266
267        let bits_of_e = BitVec::from_bytes(&e.0);
268        let responses = &proof.0;
269
270        let verifications: Vec<bool> = (0..error_factor)
271            .into_par_iter()
272            .map(|i| {
273                let ei = bits_of_e[i];
274                let response = &responses[i];
275
276                match (ei, response) {
277                    (false, Response::Open { w1, r1, w2, r2 }) => {
278                        let mut res = true;
279
280                        let expected_c1i: BigInt = Paillier::encrypt_with_chosen_randomness(
281                            ek,
282                            RawPlaintext::from(w1),
283                            &Randomness::from(r1),
284                        )
285                        .into();
286                        let expected_c2i: BigInt = Paillier::encrypt_with_chosen_randomness(
287                            ek,
288                            RawPlaintext::from(w2),
289                            &Randomness::from(r2),
290                        )
291                        .into();
292
293                        if expected_c1i != encrypted_pairs.c1[i] {
294                            res = false;
295                        }
296                        if expected_c2i != encrypted_pairs.c2[i] {
297                            res = false;
298                        }
299
300                        let flag = (*w2 < range_scaled_third
301                            && *w1 > range_scaled_third
302                            && *w1 < range_scaled_two_thirds)
303                            || (*w1 < range_scaled_third
304                                && *w2 > range_scaled_third
305                                && *w2 < range_scaled_two_thirds);
306
307                        if !flag {
308                            res = false;
309                        }
310
311                        res
312                    }
313
314                    (
315                        true,
316                        Response::Mask {
317                            j,
318                            masked_x,
319                            masked_r,
320                        },
321                    ) => {
322                        let mut res = true;
323
324                        let c = if *j == 1 {
325                            &encrypted_pairs.c1[i] * cipher_x_raw.0.borrow() % &ek.nn
326                        } else {
327                            &encrypted_pairs.c2[i] * cipher_x_raw.0.borrow() % &ek.nn
328                        };
329
330                        let enc_zi = Paillier::encrypt_with_chosen_randomness(
331                            ek,
332                            RawPlaintext::from(masked_x),
333                            &Randomness::from(masked_r.clone()),
334                        );
335                        if &c != enc_zi.0.borrow() {
336                            res = false;
337                        }
338                        if *masked_x < range_scaled_third || *masked_x > range_scaled_two_thirds {
339                            res = false;
340                        }
341
342                        res
343                    }
344
345                    _ => false,
346                }
347            })
348            .collect();
349
350        if verifications.iter().all(|b| *b) {
351            Ok(())
352        } else {
353            Err(IncorrectProof)
354        }
355    }
356}
357
358/// hash based commitment scheme : digest = H(m||r), works under random oracle model. |r| is of length security parameter
359fn get_paillier_commitment(ek: &EncryptionKey, x: &BigInt, r: &BigInt) -> BigInt {
360    let com_pi =
361        Paillier::encrypt_with_chosen_randomness(ek, RawPlaintext::from(x), &Randomness::from(r));
362    com_pi.0.into_owned()
363}
364
365fn compute_digest(bytes: &[u8]) -> BigInt {
366    let mut hasher = Sha256::new();
367    hasher.update(bytes);
368    hasher.result_bigint()
369}
370
371#[cfg(test)]
372mod tests {
373    use super::*;
374    use crate::zkproofs::correct_key::CorrectKey;
375    use paillier::{Keypair, Randomness};
376
377    const RANGE_BITS: usize = 256; //for elliptic curves with 256bits for example
378
379    fn test_keypair() -> Keypair {
380        let p = BigInt::from_str_radix("148677972634832330983979593310074301486537017973460461278300587514468301043894574906886127642530475786889672304776052879927627556769456140664043088700743909632312483413393134504352834240399191134336344285483935856491230340093391784574980688823380828143810804684752914935441384845195613674104960646037368551517", 10).unwrap();
381        let q = BigInt::from_str_radix("158741574437007245654463598139927898730476924736461654463975966787719309357536545869203069369466212089132653564188443272208127277664424448947476335413293018778018615899291704693105620242763173357203898195318179150836424196645745308205164116144020613415407736216097185962171301808761138424668335445923774195463", 10).unwrap();
382        Keypair { p, q }
383    }
384
385    #[test]
386    fn test_generate_encrypted_pairs() {
387        let (ek, _dk) = test_keypair().keys();
388        let range = BigInt::from(0x000F_FFFF_FFFF_FFFFu64);
389        RangeProof::generate_encrypted_pairs(&ek, &range, STATISTICAL_ERROR_FACTOR);
390        //Paillier::verifier_commit();
391    }
392
393    #[test]
394    fn test_commit_decommit() {
395        let (verifier_ek, verifier_dk) = test_keypair().keys();
396        let (com, r, e) = RangeProof::verifier_commit(&verifier_ek);
397        // 1. verifier sends the prover (com,r,e,verifier_ek)
398        // 2. prover is playing verifier for zk correct_key protocol to make sure verifier_ek was generated correctly:
399        let (challenge, verification_aid) = CorrectKey::challenge(&verifier_ek);
400        // 3. verifier is proving correct_key
401        let proof_results = CorrectKey::prove(&verifier_dk, &challenge);
402        assert!(proof_results.is_ok());
403        // 4. prover verifies correct key proof:
404        let result = CorrectKey::verify(&proof_results.unwrap(), &verification_aid);
405        assert!(result.is_ok());
406        assert!(RangeProof::verify_commit(&verifier_ek, &com, &r, &e).is_ok())
407    }
408
409    #[test]
410    fn test_generate_proof() {
411        let (ek, _dk) = test_keypair().keys();
412        let (verifier_ek, _verifier_dk) = test_keypair().keys();
413        let range = BigInt::from(0x000F_FFFF_FFFF_FFFFu64);
414        let (_com, _r, e) = RangeProof::verifier_commit(&verifier_ek);
415        let (_encrypted_pairs, data_and_randmoness_pairs) =
416            RangeProof::generate_encrypted_pairs(&ek, &range, STATISTICAL_ERROR_FACTOR);
417        let secret_r = BigInt::sample_below(&ek.n);
418        let secret_x = BigInt::from(0x0FFF_FFFFu64);
419        let _z_vector = RangeProof::generate_proof(
420            &ek,
421            &secret_x,
422            &secret_r,
423            &e,
424            &range,
425            &data_and_randmoness_pairs,
426            STATISTICAL_ERROR_FACTOR,
427        );
428    }
429
430    #[test]
431    fn test_range_proof_correct_proof() {
432        // common:
433        let range = BigInt::sample(RANGE_BITS);
434        // prover:
435        let (ek, _dk) = test_keypair().keys();
436        let (verifier_ek, verifier_dk) = test_keypair().keys();
437        // verifier:
438        let (com, r, e) = RangeProof::verifier_commit(&verifier_ek);
439        let (challenge, verification_aid) = CorrectKey::challenge(&verifier_ek);
440        let proof_results = CorrectKey::prove(&verifier_dk, &challenge);
441        let _result = CorrectKey::verify(&proof_results.unwrap(), &verification_aid);
442        assert!(RangeProof::verify_commit(&verifier_ek, &com, &r, &e).is_ok());
443        // prover:
444        let (encrypted_pairs, data_and_randmoness_pairs) =
445            RangeProof::generate_encrypted_pairs(&ek, &range, STATISTICAL_ERROR_FACTOR);
446        // prover:
447        let secret_r = BigInt::sample_below(&ek.n);
448        let secret_x = BigInt::sample_below(&range.div_floor(&BigInt::from(3)));
449        // common:
450        let cipher_x = Paillier::encrypt_with_chosen_randomness(
451            &ek,
452            RawPlaintext::from(&secret_x),
453            &Randomness(secret_r.clone()),
454        );
455        // verifer decommits (tested in test_commit_decommit)
456        // prover:
457        let z_vector = RangeProof::generate_proof(
458            &ek,
459            &secret_x,
460            &secret_r,
461            &e,
462            &range,
463            &data_and_randmoness_pairs,
464            STATISTICAL_ERROR_FACTOR,
465        );
466        // verifier:
467        let result = RangeProof::verifier_output(
468            &ek,
469            &e,
470            &encrypted_pairs,
471            &z_vector,
472            &range,
473            &cipher_x.0,
474            STATISTICAL_ERROR_FACTOR,
475        );
476        assert!(result.is_ok());
477    }
478
479    #[test]
480    fn test_range_proof_incorrect_proof() {
481        // common:
482        let range = BigInt::sample(RANGE_BITS);
483        // prover:
484        let (ek, _dk) = test_keypair().keys();
485        let (verifier_ek, _verifier_dk) = test_keypair().keys();
486        // verifier:
487        let (_com, _r, e) = RangeProof::verifier_commit(&verifier_ek);
488        // prover:
489        let (encrypted_pairs, data_and_randmoness_pairs) =
490            RangeProof::generate_encrypted_pairs(&ek, &range, STATISTICAL_ERROR_FACTOR);
491        // prover:
492        let secret_r = BigInt::sample_below(&ek.n);
493        let secret_x = BigInt::sample_range(
494            &(BigInt::from(100i32) * &range),
495            &(BigInt::from(10000i32) * &range),
496        );
497        // common:
498        let cipher_x = Paillier::encrypt_with_chosen_randomness(
499            &ek,
500            RawPlaintext::from(&secret_x),
501            &Randomness(secret_r.clone()),
502        );
503        // verifer decommits (tested in test_commit_decommit)
504        // prover:
505        let z_vector = RangeProof::generate_proof(
506            &ek,
507            &secret_x,
508            &secret_r,
509            &e,
510            &range,
511            &data_and_randmoness_pairs,
512            STATISTICAL_ERROR_FACTOR,
513        );
514        // verifier:
515        let result = RangeProof::verifier_output(
516            &ek,
517            &e,
518            &encrypted_pairs,
519            &z_vector,
520            &range,
521            &cipher_x.0,
522            STATISTICAL_ERROR_FACTOR,
523        );
524        assert!(result.is_err());
525    }
526}
zk_paillier/zkproofs/range_proof.rs

zk_paillier/zkproofs/
range_proof.rs
