paillier_zk/
no_small_factor.rs

1//! ZK-proof for factoring of a RSA modulus. Called Пfac or Rfac in the CGGMP24
2//! paper.
3//!
4//! ## Description
5//!
6//! Both parties agree on verifier [aux data](Aux) and [security level](SecurityParams). Common input is
7//! `n > 4*security.l`. Prover additionally knows primes `p, q < pow(2, security.l) * sqrt(n)`.
8//!
9//! Proof guarantees that each `p, q > pow(2, security.l)`.
10//!
11//! ## Example
12//!
13//! ```rust
14//! use fast_paillier::backend::Integer;
15//! use paillier_zk::no_small_factor as p;
16//! # mod pregenerated {
17//! #     use super::*;
18//! #     paillier_zk::load_pregenerated_data!(
19//! #         verifier_aux: p::Aux,
20//! #         primes_1536bits: [Integer; 4],
21//! #     );
22//! # }
23//!
24//! # fn main() -> Result<(), Box<dyn std::error::Error>> {
25//! let shared_state = "some shared state";
26//! let mut rng = rand_core::OsRng;
27//! # let mut rng = rand_dev::DevRng::new();
28//!
29//! // 0. Setup: prover and verifier share common Ring-Pedersen parameters, and
30//! // agree on the level of security
31//!
32//! let aux: p::Aux = pregenerated::verifier_aux();
33//! let security = p::SecurityParams {
34//!     l: 256,
35//!     epsilon: 512,
36//! };
37//!
38//! // 1. Prover prepares the data to obtain proof about
39//!
40//! let [p, q, ..] = pregenerated::primes_1536bits();
41//! let n = &p * &q;
42//! let n_root = n.sqrt_ref().unwrap();
43//! let data = p::Data {
44//!     n: &n,
45//!     n_root: &n_root,
46//! };
47//!
48//! // 2. Prover computes a non-interactive proof that both factors are large enough
49//!
50//! let proof = p::non_interactive::prove::<sha2::Sha256>(
51//!     &shared_state,
52//!     &aux,
53//!     data,
54//!     p::PrivateData { p: &p, q: &q },
55//!     &security,
56//!     &mut rng,
57//! )?;
58//!
59//! // 4. Prover sends this data to verifier
60//!
61//! # fn send(_: &Integer, _: &p::NiProof) {  }
62//! send(data.n, &proof);
63//!
64//! // 5. Verifier receives the data and the proof and verifies it
65//!
66//! # let recv = || (data.n, proof);
67//! let (n, proof) = recv();
68//! let n_root = n.sqrt_ref().unwrap();
69//! let data = p::Data {
70//!     n: &n,
71//!     n_root: &n_root,
72//! };
73//! p::non_interactive::verify::<sha2::Sha256>(&shared_state, &aux, data, &security, &proof)?;
74//! # Ok(()) }
75//! ```
76//!
77//! If the verification succeeded, verifier can continue communication with prover
78
79#[cfg(feature = "serde")]
80use serde::{Deserialize, Serialize};
81
82use fast_paillier::backend::Integer;
83
84pub use crate::common::{Aux, InvalidProof};
85
86/// Security parameters for proof. Choosing the values is a tradeoff between
87/// speed and chance of rejecting a valid proof or accepting an invalid proof
88#[derive(Debug, Clone, udigest::Digestable)]
89#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
90pub struct SecurityParams {
91    /// l in paper, security parameter for bit size of plaintext: it needs to
92    /// differ from sqrt(n) not more than by 2^l
93    pub l: usize,
94    /// Epsilon in paper, slackness parameter
95    pub epsilon: usize,
96}
97
98/// Public data that both parties know
99#[derive(Debug, Clone, Copy, udigest::Digestable)]
100pub struct Data<'a> {
101    /// N_i in the spec
102    #[udigest(as = &crate::common::encoding::Integer)]
103    pub n: &'a Integer,
104    /// A number close to square root of n
105    #[udigest(as = &crate::common::encoding::Integer)]
106    pub n_root: &'a Integer,
107}
108
109/// Private data of prover
110#[derive(Debug, Clone, Copy)]
111pub struct PrivateData<'a> {
112    pub p: &'a Integer,
113    pub q: &'a Integer,
114}
115
116/// Prover's data accompanying the commitment. Kept as state between rounds in
117/// the interactive protocol.
118#[derive(Debug, Clone)]
119#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
120pub struct PrivateCommitment {
121    pub alpha: Integer,
122    pub beta: Integer,
123    pub mu: Integer,
124    pub nu: Integer,
125    pub r: Integer,
126    pub x: Integer,
127    pub y: Integer,
128}
129
130/// Prover's first message, obtained by [`interactive::commit`]
131#[derive(Debug, Clone, udigest::Digestable)]
132#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
133pub struct Commitment {
134    #[udigest(as = crate::common::encoding::Integer)]
135    pub p: Integer,
136    #[udigest(as = crate::common::encoding::Integer)]
137    pub q: Integer,
138    #[udigest(as = crate::common::encoding::Integer)]
139    pub a: Integer,
140    #[udigest(as = crate::common::encoding::Integer)]
141    pub b: Integer,
142    #[udigest(as = crate::common::encoding::Integer)]
143    pub t: Integer,
144}
145
146/// Verifier's challenge to prover. Can be obtained deterministically by
147/// [`non_interactive::challenge`] or randomly by [`interactive::challenge`]
148pub type Challenge = Integer;
149
150/// The ZK proof, computed by [`interactive::prove`]
151#[derive(Debug, Clone)]
152#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
153pub struct Proof {
154    pub z1: Integer,
155    pub z2: Integer,
156    pub w1: Integer,
157    pub w2: Integer,
158    pub v: Integer,
159}
160
161/// The non-interactive ZK proof. Computed by [`non_interactive::prove`].
162/// Combines commitment and proof.
163#[derive(Debug, Clone)]
164#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
165pub struct NiProof {
166    commitment: Commitment,
167    proof: Proof,
168}
169
170/// Interactive version of the proof
171pub mod interactive {
172    use fast_paillier::backend::Integer;
173    use rand_core::RngCore;
174
175    use crate::{
176        common::{fail_if, fail_if_ne, IntegerExt, InvalidProofReason},
177        Error,
178    };
179
180    use super::{
181        Aux, Challenge, Commitment, Data, InvalidProof, PrivateCommitment, PrivateData, Proof,
182        SecurityParams,
183    };
184
185    /// Create random commitment
186    pub fn commit<R: RngCore>(
187        aux: &Aux,
188        data: Data,
189        pdata: PrivateData,
190        security: &SecurityParams,
191        mut rng: R,
192    ) -> Result<(Commitment, PrivateCommitment), Error> {
193        let two_to_l = Integer::one() << security.l;
194        let two_to_l_plus_e = Integer::one() << (security.l + security.epsilon);
195        let n_root_at_two_to_l_plus_e = &two_to_l_plus_e * data.n_root;
196        let aux_n_at_two_to_l = &two_to_l * &aux.rsa_modulo;
197        let aux_n_at_two_to_l_plus_e = &two_to_l_plus_e * &aux.rsa_modulo;
198        let n_at_aux_n = &aux.rsa_modulo * data.n;
199
200        let alpha = Integer::from_rng_half_pm(&mut rng, &n_root_at_two_to_l_plus_e);
201        let beta = Integer::from_rng_half_pm(&mut rng, &n_root_at_two_to_l_plus_e);
202        let mu = Integer::from_rng_half_pm(&mut rng, &aux_n_at_two_to_l);
203        let nu = Integer::from_rng_half_pm(&mut rng, &aux_n_at_two_to_l);
204        let r = Integer::from_rng_half_pm(&mut rng, &(&two_to_l_plus_e * &n_at_aux_n));
205        let x = Integer::from_rng_half_pm(&mut rng, &aux_n_at_two_to_l_plus_e);
206        let y = Integer::from_rng_half_pm(&mut rng, &aux_n_at_two_to_l_plus_e);
207
208        let p = aux.combine(pdata.p, &mu)?;
209        let q = aux.combine(pdata.q, &nu)?;
210        let a = aux.combine(&alpha, &x)?;
211        let b = aux.combine(&beta, &y)?;
212        let t = aux
213            .rsa_modulo
214            .combine(&q, &alpha, &aux.t, &r)
215            .ok_or_else(crate::BadExponent::undefined)?;
216
217        let commitment = Commitment { p, q, a, b, t };
218        let private_commitment = PrivateCommitment {
219            alpha,
220            beta,
221            mu,
222            nu,
223            r,
224            x,
225            y,
226        };
227        Ok((commitment, private_commitment))
228    }
229
230    /// Generate random challenge
231    ///
232    /// `security` parameter is used to generate challenge in correct range
233    pub fn challenge<R: RngCore>(security: &SecurityParams, rng: &mut R) -> Challenge {
234        Integer::from_rng_half_pm(rng, &(Integer::one() << security.l))
235    }
236
237    /// Compute proof for given data and prior protocol values
238    pub fn prove(
239        pdata: PrivateData,
240        pcomm: &PrivateCommitment,
241        challenge: &Challenge,
242    ) -> Result<Proof, Error> {
243        Ok(Proof {
244            z1: &pcomm.alpha + challenge * pdata.p,
245            z2: &pcomm.beta + challenge * pdata.q,
246            w1: &pcomm.x + challenge * &pcomm.mu,
247            w2: &pcomm.y + challenge * &pcomm.nu,
248            v: &pcomm.r - challenge * (&pcomm.nu * pdata.p),
249        })
250    }
251
252    /// Verify the proof
253    pub fn verify(
254        aux: &Aux,
255        data: Data,
256        commitment: &Commitment,
257        security: &SecurityParams,
258        challenge: &Challenge,
259        proof: &Proof,
260    ) -> Result<(), InvalidProof> {
261        // Verify that inputs are in expected domains
262        fail_if(
263            InvalidProofReason::RangeCheck(0),
264            aux.is_in_mult_group(&commitment.p),
265        )?;
266        fail_if(
267            InvalidProofReason::RangeCheck(1),
268            aux.is_in_mult_group(&commitment.q),
269        )?;
270        fail_if(
271            InvalidProofReason::RangeCheck(2),
272            aux.is_in_mult_group(&commitment.a),
273        )?;
274        fail_if(
275            InvalidProofReason::RangeCheck(3),
276            aux.is_in_mult_group(&commitment.b),
277        )?;
278        fail_if(
279            InvalidProofReason::RangeCheck(4),
280            aux.is_in_mult_group(&commitment.t),
281        )?;
282        // Verify the statement
283        // range check for N_i
284        {
285            let n_bits: usize = data
286                .n
287                .significant_bits()
288                .try_into()
289                .map_err(|_| InvalidProofReason::Conversion)?;
290            fail_if(InvalidProofReason::RangeCheck(5), n_bits >= 4 * security.l)?;
291        }
292        {
293            let lhs = aux.combine(&proof.z1, &proof.w1)?;
294            let p_to_e = aux.pow_mod(&commitment.p, challenge)?;
295            let rhs = (&commitment.a * p_to_e).modulo(&aux.rsa_modulo);
296            fail_if_ne(InvalidProofReason::EqualityCheck(6), &lhs, &rhs)?;
297            fail_if(
298                InvalidProofReason::MultGroupCheck(7),
299                aux.is_in_mult_group(&lhs),
300            )?;
301        }
302        {
303            let lhs = aux.combine(&proof.z2, &proof.w2)?;
304            let q_to_e = aux.pow_mod(&commitment.q, challenge)?;
305            let rhs = (&commitment.b * q_to_e).modulo(&aux.rsa_modulo);
306            fail_if_ne(InvalidProofReason::EqualityCheck(8), &lhs, &rhs)?;
307            fail_if(
308                InvalidProofReason::MultGroupCheck(9),
309                aux.is_in_mult_group(&lhs),
310            )?;
311        }
312        {
313            let r = aux.pow_mod(&aux.s, data.n)?;
314            let q_to_z1 = aux.pow_mod(&commitment.q, &proof.z1)?;
315            let t_to_v = aux.pow_mod(&aux.t, &proof.v)?;
316            let lhs = (q_to_z1 * t_to_v).modulo(&aux.rsa_modulo);
317            let rhs = (&commitment.t * aux.pow_mod(&r, challenge)?).modulo(&aux.rsa_modulo);
318            fail_if_ne(InvalidProofReason::EqualityCheck(10), &lhs, &rhs)?;
319            fail_if(
320                InvalidProofReason::MultGroupCheck(11),
321                aux.is_in_mult_group(&lhs),
322            )?;
323        }
324        let range = (Integer::from(1) << (security.l + security.epsilon)) * data.n_root;
325        // range check for z1
326        fail_if(
327            InvalidProofReason::RangeCheck(12),
328            proof.z1.is_in_half_pm(&range),
329        )?;
330        // range check for z2
331        fail_if(
332            InvalidProofReason::RangeCheck(13),
333            proof.z2.is_in_half_pm(&range),
334        )?;
335
336        Ok(())
337    }
338}
339
340/// Non-interactive version of the proof
341pub mod non_interactive {
342    use digest::Digest;
343
344    pub use crate::{Error, InvalidProof};
345
346    pub use super::{Aux, Challenge, Data, NiProof, PrivateData, SecurityParams};
347
348    /// Compute proof for the given data, producing random commitment and
349    /// deriving determenistic challenge.
350    ///
351    /// Obtained from the above interactive proof via Fiat-Shamir heuristic.
352    pub fn prove<D: Digest>(
353        shared_state: &impl udigest::Digestable,
354        aux: &Aux,
355        data: Data,
356        pdata: PrivateData,
357        security: &SecurityParams,
358        rng: &mut impl rand_core::RngCore,
359    ) -> Result<NiProof, Error> {
360        let (commitment, pcomm) = super::interactive::commit(aux, data, pdata, security, rng)?;
361        let challenge = challenge::<D>(shared_state, aux, data, &commitment, security);
362        let proof = super::interactive::prove(pdata, &pcomm, &challenge)?;
363        Ok(NiProof { commitment, proof })
364    }
365
366    /// Deterministically compute challenge based on prior known values in protocol
367    pub fn challenge<D: Digest>(
368        shared_state: &impl udigest::Digestable,
369        aux: &Aux,
370        data: Data,
371        commitment: &super::Commitment,
372        security: &SecurityParams,
373    ) -> Challenge {
374        let tag = "paillier_zk.no_small_factor.ni_challenge";
375        let seed = udigest::inline_struct!(tag {
376            shared_state,
377            security,
378            aux: aux.digest_public_data(),
379            data,
380            commitment,
381        });
382        let mut rng = rand_hash::HashRng::<D, _>::from_seed(&seed);
383        super::interactive::challenge(security, &mut rng)
384    }
385
386    /// Verify the proof, deriving challenge independently from same data
387    pub fn verify<D: Digest>(
388        shared_state: &impl udigest::Digestable,
389        aux: &Aux,
390        data: Data,
391        security: &SecurityParams,
392        proof: &NiProof,
393    ) -> Result<(), InvalidProof> {
394        let challenge = challenge::<D>(shared_state, aux, data, &proof.commitment, security);
395        super::interactive::verify(
396            aux,
397            data,
398            &proof.commitment,
399            security,
400            &challenge,
401            &proof.proof,
402        )
403    }
404}
405
406#[cfg(test)]
407mod test {
408    use crate::common::test::generate_blum_prime;
409    use crate::common::InvalidProofReason;
410
411    #[test]
412    fn passing() {
413        type D = sha2::Sha256;
414
415        let n_bitlen = 3072;
416        let security = super::SecurityParams {
417            l: 256,
418            epsilon: 512,
419        };
420
421        let mut rng = rand_dev::DevRng::new();
422        let p = generate_blum_prime(&mut rng, n_bitlen / 2);
423        let q = generate_blum_prime(&mut rng, n_bitlen / 2);
424        let n = &p * &q;
425        let n_root = n.sqrt_ref().unwrap();
426        let data = super::Data {
427            n: &n,
428            n_root: &n_root,
429        };
430
431        assert!(n.significant_bits() >= u64::from(n_bitlen) - 1);
432
433        let aux = crate::common::test::aux(&mut rng);
434        let shared_state = "shared state";
435        let proof = super::non_interactive::prove::<D>(
436            &shared_state,
437            &aux,
438            data,
439            super::PrivateData { p: &p, q: &q },
440            &security,
441            &mut rng,
442        )
443        .unwrap();
444        let r = super::non_interactive::verify::<D>(&shared_state, &aux, data, &security, &proof);
445        match r {
446            Ok(()) => (),
447            Err(e) => panic!("Proof should not fail with {e:?}"),
448        }
449    }
450
451    #[test]
452    fn failing() {
453        type D = sha2::Sha256;
454
455        let n_bitlen = 3072;
456        let security = super::SecurityParams {
457            l: 256,
458            epsilon: 512,
459        };
460
461        let mut rng = rand_dev::DevRng::new();
462        let p = generate_blum_prime(&mut rng, n_bitlen - (security.l as u32) / 2);
463        let q = generate_blum_prime(&mut rng, security.l as u32 / 2);
464        let n = &p * &q;
465        let n_root = n.sqrt_ref().unwrap();
466        let data = super::Data {
467            n: &n,
468            n_root: &n_root,
469        };
470
471        assert!(n.significant_bits() >= u64::from(n_bitlen) - 1);
472
473        let aux = crate::common::test::aux(&mut rng);
474        let shared_state = "shared state";
475        let proof = super::non_interactive::prove::<D>(
476            &shared_state,
477            &aux,
478            data,
479            super::PrivateData { p: &p, q: &q },
480            &security,
481            &mut rng,
482        )
483        .unwrap();
484        let r = super::non_interactive::verify::<D>(&shared_state, &aux, data, &security, &proof)
485            .expect_err("proof should not pass");
486        match r.reason() {
487            InvalidProofReason::RangeCheck(12) => (),
488            e => panic!("Proof should not fail with {e:?}"),
489        }
490    }
491}
paillier_zk/no_small_factor.rs

paillier_zk/
no_small_factor.rs
