paillier_zk/
paillier_blum_modulus.rs

1//! ZK-proof of Paillier-Blum modulus. Called Пmod or Rmod in the CGGMP24 paper.
2//!
3//! ## Description
4//! A party P has a Paillier-Blum modulus `N = pq`, with p and q being primes such
5//! that `gcd(N, phi(N)) = 1` and `p,q = 3 \mod 4`. P wants to prove that those
6//! equalities about N hold, without disclosing p and q.
7//!
8//! ## Example
9//! ```rust
10//! # fn main() -> Result<(), Box<dyn std::error::Error>> {
11//! use fast_paillier::backend::Integer;
12//! let mut rng = rand_core::OsRng;
13//! # let mut rng = rand_dev::DevRng::new();
14//!
15//! // 0. Prover P derives two Blum primes and makes a Paillier-Blum modulus
16//! let p = Integer::generate_safe_prime(&mut rng, 256);
17//! let q = Integer::generate_safe_prime(&mut rng, 256);
18//! let n = &p * &q;
19//!
20//! // 1. P computes a non-interactive proof that `n` is a Paillier-Blum modulus:
21//! use paillier_zk::paillier_blum_modulus as p;
22//!
23//! // Security parameter
24//! const SECURITY: usize = 33;
25//! // Verifier and prover share the same state
26//! let shared_state = "some shared state";
27//!
28//! let data = p::Data { n: &n };
29//! let pdata = p::PrivateData { p: &p, q: &q };
30//!
31//! let proof =
32//!     p::non_interactive::prove::<{SECURITY}, sha2::Sha256>(
33//!         &shared_state,
34//!         data,
35//!         pdata,
36//!         &mut rng,
37//!     )?;
38//!
39//! // 2. P sends `data, commitment, proof` to the verifier V
40//!
41//! # fn send(_: &p::Data, _: &p::NiProof<{SECURITY}>) { }
42//! send(&data, &proof);
43//!
44//! // 3. V receives and verifies the proof:
45//!
46//! # let recv = || (data, proof);
47//! let (data, proof) = recv();
48//!
49//! p::non_interactive::verify::<{SECURITY}, sha2::Sha256>(
50//!     &shared_state,
51//!     data,
52//!     &proof,
53//!     &mut rng,
54//! )?;
55//! # Ok(()) }
56//! ```
57//! If the verification succeeded, V can continue communication with P
58
59use fast_paillier::backend::Integer;
60
61#[cfg(feature = "serde")]
62use serde::{Deserialize, Serialize};
63
64/// Public data that both parties know: the Paillier-Blum modulus
65#[derive(Debug, Clone, Copy, udigest::Digestable)]
66pub struct Data<'a> {
67    #[udigest(as = &crate::common::encoding::Integer)]
68    pub n: &'a Integer,
69}
70
71/// Private data of prover
72#[derive(Clone, Copy)]
73pub struct PrivateData<'a> {
74    pub p: &'a Integer,
75    pub q: &'a Integer,
76}
77
78/// Prover's first message, obtained by [`interactive::commit`]
79#[derive(Debug, Clone, udigest::Digestable)]
80#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
81pub struct Commitment {
82    #[udigest(as = crate::common::encoding::Integer)]
83    pub w: Integer,
84}
85
86/// Verifier's challenge to prover. Can be obtained deterministically by
87/// [`non_interactive::challenge`] or randomly by [`interactive::challenge`]
88///
89/// Consists of `M` singular challenges
90#[derive(Debug, PartialEq, Eq, Clone)]
91pub struct Challenge<const M: usize> {
92    pub ys: [Integer; M],
93}
94
95/// A part of proof. Having enough of those guarantees security
96#[derive(Debug, Clone)]
97#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
98pub struct ProofPoint {
99    pub x: Integer,
100    pub a: bool,
101    pub b: bool,
102    pub z: Integer,
103}
104
105/// The ZK proof. Computed by [`interactive::prove`].
106/// Consists of M proofs for each challenge
107#[derive(Debug, Clone)]
108#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
109pub struct Proof<const M: usize> {
110    #[cfg_attr(
111        // A trick to serialize arbitrary size arrays
112        feature = "serde",
113        serde(with = "serde_with::As::<[serde_with::Same; M]>")
114    )]
115    pub points: [ProofPoint; M],
116}
117
118/// The non-interactive ZK proof. Computed by [`non_interactive::prove`].
119/// Combines commitment and proof.
120#[derive(Debug, Clone)]
121#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
122pub struct NiProof<const M: usize> {
123    pub commitment: Commitment,
124    pub proof: Proof<M>,
125}
126
127/// The interactive version of the ZK proof. Should be completed in 3 rounds:
128/// prover commits to data, verifier responds with a random challenge, and
129/// prover gives proof with commitment and challenge.
130pub mod interactive {
131    use fast_paillier::backend::Integer;
132    use rand_core::RngCore;
133
134    use crate::common::{
135        fail_if,
136        sqrt::{blum_sqrt, find_residue, sample_invertible_with_neg_jacobi},
137    };
138    use crate::{BadExponent, Error, ErrorReason, InvalidProof, InvalidProofReason};
139
140    use super::{Challenge, Commitment, Data, PrivateData, Proof, ProofPoint};
141
142    /// Create random commitment
143    pub fn commit<R: RngCore>(Data { n }: Data, rng: &mut R) -> Commitment {
144        Commitment {
145            w: sample_invertible_with_neg_jacobi(n, rng),
146        }
147    }
148
149    /// Compute proof for given data and prior protocol values
150    pub fn prove<const M: usize>(
151        Data { n }: Data,
152        PrivateData { p, q }: PrivateData,
153        Commitment { ref w }: &Commitment,
154        challenge: &Challenge<M>,
155    ) -> Result<Proof<M>, Error> {
156        let blum_sqrt = |x| blum_sqrt(&x, p, q, n);
157        let phi = (p - 1) * (q - 1);
158        let n_inverse = n.invert_ref(&phi).ok_or(ErrorReason::Invert)?;
159
160        // We do an extra allocation as workaround while `array::try_map` is not stable
161        let points = challenge
162            .ys
163            .iter()
164            .map(|y| {
165                let z = y
166                    .pow_mod_ref(&n_inverse, n)
167                    .ok_or(BadExponent::undefined())?;
168                let (a, b, y_) = find_residue(y, w, p, q, n).ok_or(ErrorReason::FindResidue)?;
169                let x = blum_sqrt(blum_sqrt(y_));
170                Ok(ProofPoint { x, a, b, z })
171            })
172            .collect::<Result<Vec<_>, ErrorReason>>()?
173            .try_into()
174            .map_err(|_| ErrorReason::Length)?;
175        Ok(Proof { points })
176    }
177
178    /// Verify the proof. If this succeeds, the relation Rmod holds with chance
179    /// `1/2^M`
180    ///
181    /// Rng is used for primality checking of input data
182    pub fn verify<const M: usize, R: RngCore>(
183        data: Data,
184        commitment: &Commitment,
185        challenge: &Challenge<M>,
186        proof: &Proof<M>,
187        rng: &mut R,
188    ) -> Result<(), InvalidProof> {
189        if data.n.is_probably_prime(25, rng) != fast_paillier::backend::IsPrime::No {
190            return Err(InvalidProofReason::ModulusIsPrime.into());
191        }
192        if data.n.is_even() {
193            return Err(InvalidProofReason::ModulusIsEven.into());
194        }
195        fail_if(
196            InvalidProofReason::RangeCheck(1),
197            commitment.w.in_mult_group_of(data.n),
198        )?;
199
200        for (point, y) in proof.points.iter().zip(challenge.ys.iter()) {
201            fail_if(
202                InvalidProofReason::RangeCheck(2),
203                point.x.in_mult_group_of(data.n),
204            )?;
205            fail_if(
206                InvalidProofReason::RangeCheck(3),
207                point.z.in_mult_group_of(data.n),
208            )?;
209            if point
210                .z
211                .pow_mod_ref(data.n, data.n)
212                .ok_or(InvalidProofReason::ModPow)?
213                != *y
214            {
215                return Err(InvalidProofReason::IncorrectNthRoot.into());
216            }
217            let y = if point.a { data.n - y } else { y.clone() };
218            let y = if point.b {
219                (y * &commitment.w).modulo(data.n)
220            } else {
221                y
222            };
223            if point
224                .x
225                .pow_mod_ref(&4.into(), data.n)
226                .ok_or(InvalidProofReason::ModPow)?
227                != y
228            {
229                return Err(InvalidProofReason::IncorrectFourthRoot.into());
230            }
231        }
232        Ok(())
233    }
234
235    /// Generate random challenge
236    ///
237    /// `data` parameter is used to generate challenge in correct range
238    pub fn challenge<const M: usize, R: RngCore>(Data { n }: Data, rng: &mut R) -> Challenge<M> {
239        let ys = [(); M].map(|()| Integer::sample_in_mult_group_of(rng, n));
240        Challenge { ys }
241    }
242}
243
244/// The non-interactive version of proof. Completed in one round, for example
245/// see the documentation of parent module.
246pub mod non_interactive {
247    use digest::Digest;
248
249    use crate::{Error, InvalidProof};
250
251    use super::{Challenge, Commitment, Data, NiProof, PrivateData};
252
253    /// Compute proof for the given data, producing random commitment and
254    /// deriving determenistic challenge.
255    ///
256    /// Obtained from the above interactive proof via Fiat-Shamir heuristic.
257    pub fn prove<const M: usize, D: Digest>(
258        shared_state: &impl udigest::Digestable,
259        data: Data,
260        pdata: PrivateData,
261        rng: &mut impl rand_core::RngCore,
262    ) -> Result<NiProof<M>, Error> {
263        let commitment = super::interactive::commit(data, rng);
264        let challenge = challenge::<M, D>(shared_state, data, &commitment);
265        let proof = super::interactive::prove(data, pdata, &commitment, &challenge)?;
266        Ok(NiProof { commitment, proof })
267    }
268
269    /// Verify the proof, deriving challenge independently from same data
270    ///
271    /// Rng is used for primality checking of input data
272    pub fn verify<const M: usize, D: Digest>(
273        shared_state: &impl udigest::Digestable,
274        data: Data,
275        proof: &NiProof<M>,
276        rng: &mut impl rand_core::RngCore,
277    ) -> Result<(), InvalidProof> {
278        let challenge = challenge::<M, D>(shared_state, data, &proof.commitment);
279        super::interactive::verify(data, &proof.commitment, &challenge, &proof.proof, rng)
280    }
281
282    /// Deterministically compute challenge based on prior known values in protocol
283    pub fn challenge<const M: usize, D: Digest>(
284        shared_state: &impl udigest::Digestable,
285        data: Data,
286        commitment: &Commitment,
287    ) -> Challenge<M> {
288        let tag = "paillier_zk.blum_modulus.ni_challenge";
289        let seed = udigest::inline_struct!(tag {
290            shared_state,
291            data,
292            commitment,
293        });
294        let mut rng = rand_hash::HashRng::<D, _>::from_seed(seed);
295
296        super::interactive::challenge(data, &mut rng)
297    }
298}
299
300#[cfg(test)]
301mod test {
302    use crate::common::test::generate_blum_prime;
303
304    type D = sha2::Sha256;
305
306    #[test]
307    fn passing() {
308        let mut rng = rand_dev::DevRng::new();
309        let p = generate_blum_prime(&mut rng, 256);
310        let q = generate_blum_prime(&mut rng, 256);
311        let n = &p * &q;
312        let data = super::Data { n: &n };
313        let pdata = super::PrivateData { p: &p, q: &q };
314        let shared_state = "shared state";
315        let proof =
316            super::non_interactive::prove::<65, D>(&shared_state, data, pdata, &mut rng).unwrap();
317        let r = super::non_interactive::verify::<65, D>(&shared_state, data, &proof, &mut rng);
318        match r {
319            Ok(()) => (),
320            Err(e) => panic!("{e:?}"),
321        }
322    }
323
324    #[test]
325    fn failing() {
326        let mut rng = rand_dev::DevRng::new();
327        let p = generate_blum_prime(&mut rng, 256);
328        let q = loop {
329            // non blum prime
330            let q = fast_paillier::backend::Integer::generate_prime(&mut rng, 256);
331            if q.mod_u(4) == 1 {
332                break q;
333            }
334        };
335        let n = &p * &q;
336        let data = super::Data { n: &n };
337        let pdata = super::PrivateData { p: &p, q: &q };
338        let shared_state = "shared state";
339        let proof =
340            super::non_interactive::prove::<65, D>(&shared_state, data, pdata, &mut rng).unwrap();
341        let r = super::non_interactive::verify::<65, D>(&shared_state, data, &proof, &mut rng);
342        if r.is_ok() {
343            panic!("proof should not pass");
344        }
345    }
346}
paillier_zk/paillier_blum_modulus.rs

paillier_zk/
paillier_blum_modulus.rs
