paillier_zk/
paillier_encryption_in_range_with_el_gamal.rs

1//! ZK-proof of paillier encryption in range with El-Gamal commitment.
2//! Called Пenc-elg or Renc-elg in the CGGMP24
3//! paper.
4//!
5//! ## Description
6//!
7//! Common (public) inputs: verifier's [`Aux`] data, [`SecurityParams`] containing
8//! $\ell$ and $\varepsilon$, [curve `E`](Curve), Paillier public `key`, a `ciphertext`,
9//! and elliptic points $A, B, X$.
10//!
11//! Prover secret inputs: `plaintext`, `nonce`, scalars $a, b$, such that:
12//! * `plaintext` $\in \pm 2^\ell$
13//! * `ciphertext == key.encrypt_with(plaintext, nonce)`
14//! * $A = a \cdot G$
15//! * $B = b \cdot G$
16//! * $X = (a b + \text{plaintext}) \cdot G$
17//!
18//! Proof guarantees that `plaintext` $\in \pm 2^{\ell + \varepsilon}$.
19//!
20//! ## Example
21//!
22//! ```
23//! use paillier_zk::{paillier_encryption_in_range_with_el_gamal as p, IntegerExt};
24//! use fast_paillier::backend::Integer;
25//! use generic_ec::{Point, Scalar, curves::Secp256k1 as E};
26//! # mod pregenerated {
27//! #     use super::*;
28//! #     paillier_zk::load_pregenerated_data!(
29//! #         verifier_aux: p::Aux,
30//! #         someone_encryption_key: fast_paillier::EncryptionKey,
31//! #     );
32//! # }
33//! # fn main() -> Result<(), Box<dyn std::error::Error>> {
34//!
35//! let shared_state = "some shared state";
36//!
37//! let mut rng = rand_core::OsRng;
38//! # let mut rng = rand_dev::DevRng::new();
39//!
40//! // Both parties know predefined security parameters and verifier's aux data
41//! let aux: p::Aux = pregenerated::verifier_aux();
42//! let security = p::SecurityParams {
43//!     l: 256,
44//!     epsilon: 512,
45//! };
46//! // ...and someone's encryption key
47//! let key: fast_paillier::EncryptionKey =
48//!     pregenerated::someone_encryption_key();
49//!
50//! // Prover knows its secret `pdata` and `a`
51//! let a = Scalar::random(&mut rng);
52//! let pdata = p::PrivateData {
53//!     plaintext: &Integer::from_rng_half_pm(&mut rng, &(Integer::one() << security.l)),
54//!     nonce: &Integer::sample_in_mult_group_of(&mut rng, key.n()),
55//!     b: &Scalar::random(&mut rng),
56//! };
57//!
58//! // Both parties know the public data
59//! let data = p::Data {
60//!     key: &key,
61//!     ciphertext: &key
62//!         .encrypt_with(pdata.plaintext, pdata.nonce)
63//!         .unwrap(),
64//!     a: &(Point::generator() * a),
65//!     b: &(Point::generator() * pdata.b),
66//!     x: &(Point::generator() * (a * pdata.b + pdata.plaintext.to_scalar())),
67//! };
68//!
69//! // Prover computes a non-interactive proof:
70//! let proof = p::non_interactive::prove::<E, sha2::Sha256>(
71//!     &shared_state,
72//!     &aux,
73//!     data,
74//!     pdata,
75//!     &security,
76//!     &mut rng,
77//! )?;
78//!
79//! // Prover sends this data to verifier
80//! # use generic_ec::Curve;
81//! # fn send<E: Curve>(_: &p::Data<E>, _: &p::NiProof<E>) {  }
82//! send(&data, &proof);
83//!
84//! // Verifier receives the data and the proof and verifies it
85//! # let recv = || (data, proof);
86//! let (data, proof) = recv();
87//! p::non_interactive::verify::<E, sha2::Sha256>(
88//!     &shared_state,
89//!     &aux,
90//!     data,
91//!     &proof,
92//!     &security,
93//! );
94//! # Ok(()) }
95//! ```
96//!
97//! If the verification succeeded, verifier can continue communication with prover
98
99use fast_paillier::backend::Integer;
100use fast_paillier::{AnyEncryptionKey, Ciphertext, Nonce, Plaintext};
101use generic_ec::{Curve, Point, Scalar};
102
103#[cfg(feature = "serde")]
104use serde::{Deserialize, Serialize};
105
106pub use crate::common::Aux;
107pub use crate::common::InvalidProof;
108
109/// Security parameters for proof. Choosing the values is a tradeoff between
110/// security, speed and correctness
111#[derive(Debug, Clone, udigest::Digestable)]
112#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
113pub struct SecurityParams {
114    /// $\ell$ in paper
115    pub l: usize,
116    /// $\varepsilon$ in paper, slackness parameter
117    pub epsilon: usize,
118}
119
120/// Public data that both parties know
121#[derive(Debug, Clone, Copy, udigest::Digestable)]
122#[udigest(bound = "")]
123pub struct Data<'a, C: Curve> {
124    /// $N_0$ in paper
125    #[udigest(as = crate::common::encoding::AnyEncryptionKey)]
126    pub key: &'a dyn AnyEncryptionKey,
127    /// $C$ in paper
128    #[udigest(as = &crate::common::encoding::Integer)]
129    pub ciphertext: &'a Ciphertext,
130    /// $A$ in paper
131    pub a: &'a Point<C>,
132    /// $B$ in paper
133    pub b: &'a Point<C>,
134    /// $X$ in paper
135    pub x: &'a Point<C>,
136}
137
138/// Private data of prover
139#[derive(Clone, Copy)]
140pub struct PrivateData<'a, E: Curve> {
141    /// $x$ in paper
142    pub plaintext: &'a Plaintext,
143    /// $\rho$ in paper
144    pub nonce: &'a Nonce,
145    /// $b$ in paper
146    pub b: &'a Scalar<E>,
147}
148
149/// Prover's public commitment
150#[derive(Debug, Clone, udigest::Digestable)]
151#[udigest(bound = "")]
152#[cfg_attr(feature = "serde", derive(Serialize, Deserialize), serde(bound = ""))]
153pub struct Commitment<E: Curve> {
154    #[udigest(as = crate::common::encoding::Integer)]
155    pub s: Integer,
156    #[udigest(as = crate::common::encoding::Integer)]
157    pub t: Integer,
158    #[udigest(as = crate::common::encoding::Integer)]
159    pub d: Integer,
160    pub y: Point<E>,
161    pub z: Point<E>,
162}
163
164/// Prover's secret commitment nonce
165#[derive(Clone)]
166pub struct PrivateCommitment<E: Curve> {
167    pub alpha: Integer,
168    pub mu: Integer,
169    pub r: Integer,
170    pub beta: Scalar<E>,
171    pub gamma: Integer,
172}
173
174/// Verifier's challenge to prover. Can be obtained deterministically by
175/// [`non_interactive::challenge`] or randomly by [`interactive::challenge`]
176pub type Challenge = Integer;
177
178/// Range Proof with El-Gamal commitment. Computed by [`interactive::prove`]
179#[derive(Debug, Clone)]
180#[cfg_attr(feature = "serde", derive(Serialize, Deserialize), serde(bound = ""))]
181pub struct Proof<E: Curve> {
182    pub z1: Integer,
183    pub z2: Integer,
184    pub z3: Integer,
185    pub w: Scalar<E>,
186}
187
188/// The non-interactive ZK proof. Computed by [`non_interactive::prove`].
189/// Combines commitment and proof.
190#[derive(Debug, Clone)]
191#[cfg_attr(feature = "serde", derive(Serialize, Deserialize), serde(bound = ""))]
192pub struct NiProof<E: Curve> {
193    pub commitment: Commitment<E>,
194    pub proof: Proof<E>,
195}
196
197/// The interactive version of the ZK proof. Should be completed in 3 rounds:
198/// prover commits to data, verifier responds with a random challenge, and
199/// prover gives proof with commitment and challenge.
200pub mod interactive {
201    use fast_paillier::backend::Integer;
202    use generic_ec::{Curve, Point, Scalar};
203    use rand_core::RngCore;
204
205    use crate::{
206        common::{fail_if, fail_if_ne, InvalidProofReason},
207        BadExponent, Error,
208    };
209
210    use crate::common::{IntegerExt, InvalidProof};
211
212    use super::{
213        Aux, Challenge, Commitment, Data, PrivateCommitment, PrivateData, Proof, SecurityParams,
214    };
215
216    /// Create random commitment
217    pub fn commit<E: Curve>(
218        aux: &Aux,
219        data: Data<E>,
220        pdata: PrivateData<E>,
221        security: &SecurityParams,
222        rng: &mut impl RngCore,
223    ) -> Result<(Commitment<E>, PrivateCommitment<E>), Error> {
224        let two_to_l_plus_e = Integer::one() << (security.l + security.epsilon);
225        let n_j_at_two_to_l = (Integer::one() << security.l) * &aux.rsa_modulo;
226        let n_j_at_two_to_l_plus_e = &two_to_l_plus_e * &aux.rsa_modulo;
227
228        let alpha = Integer::from_rng_half_pm(rng, &two_to_l_plus_e);
229        let mu = Integer::from_rng_half_pm(rng, &n_j_at_two_to_l);
230        let r = Integer::sample_in_mult_group_of(rng, data.key.n());
231        let beta = Scalar::random(rng);
232        let gamma = Integer::from_rng_half_pm(rng, &n_j_at_two_to_l_plus_e);
233
234        let s = aux.combine(pdata.plaintext, &mu)?;
235        let t = aux.combine(&alpha, &gamma)?;
236        let d = data.key.encrypt_with(&alpha, &r)?;
237        let y = data.a * beta + Point::<E>::generator() * alpha.to_scalar();
238        let z = Point::<E>::generator() * beta;
239
240        Ok((
241            Commitment { s, t, d, y, z },
242            PrivateCommitment {
243                alpha,
244                mu,
245                r,
246                beta,
247                gamma,
248            },
249        ))
250    }
251
252    /// Compute proof for given data and prior protocol values
253    pub fn prove<E: Curve>(
254        data: Data<E>,
255        pdata: PrivateData<E>,
256        private_commitment: &PrivateCommitment<E>,
257        challenge: &Challenge,
258    ) -> Result<Proof<E>, Error> {
259        let z1 = &private_commitment.alpha + (challenge * pdata.plaintext);
260        let z2 = {
261            let nonce_to_challenge_mod_n: Integer = pdata
262                .nonce
263                .pow_mod_ref(challenge, data.key.n())
264                .ok_or(BadExponent::undefined())?;
265            (&private_commitment.r * nonce_to_challenge_mod_n).modulo(data.key.n())
266        };
267        let z3 = &private_commitment.gamma + (challenge * &private_commitment.mu);
268        let w = private_commitment.beta + (challenge.to_scalar() * pdata.b);
269        Ok(Proof { z1, z2, z3, w })
270    }
271
272    /// Verify the proof
273    pub fn verify<E: Curve>(
274        aux: &Aux,
275        data: Data<E>,
276        commitment: &Commitment<E>,
277        security: &SecurityParams,
278        challenge: &Challenge,
279        proof: &Proof<E>,
280    ) -> Result<(), InvalidProof> {
281        // Verify that inputs are in expected domains:
282        fail_if(
283            InvalidProofReason::RangeCheck(1),
284            data.ciphertext.in_mult_group_of(data.key.nn()),
285        )?;
286        fail_if(
287            InvalidProofReason::RangeCheck(2),
288            aux.is_in_mult_group(&commitment.s),
289        )?;
290        fail_if(
291            InvalidProofReason::RangeCheck(3),
292            aux.is_in_mult_group(&commitment.t),
293        )?;
294        fail_if(
295            InvalidProofReason::RangeCheck(4),
296            commitment.d.in_mult_group_of(data.key.nn()),
297        )?;
298
299        // Verify statement
300        {
301            let lhs = data
302                .key
303                .encrypt_with(&proof.z1, &proof.z2)
304                .map_err(|_| InvalidProofReason::PaillierEnc)?;
305            let rhs = {
306                let e_at_c = data
307                    .key
308                    .omul(challenge, data.ciphertext)
309                    .map_err(|_| InvalidProofReason::PaillierOp)?;
310                data.key
311                    .oadd(&commitment.d, &e_at_c)
312                    .map_err(|_| InvalidProofReason::PaillierOp)?
313            };
314            fail_if_ne(InvalidProofReason::EqualityCheck(5), lhs, rhs)?;
315        }
316        {
317            let lhs = data.a * proof.w + Point::<E>::generator() * proof.z1.to_scalar();
318            let rhs = commitment.y + data.x * challenge.to_scalar();
319            fail_if_ne(InvalidProofReason::EqualityCheck(6), lhs, rhs)?;
320        }
321        {
322            let lhs = Point::<E>::generator() * proof.w;
323            let rhs = commitment.z + data.b * challenge.to_scalar();
324            fail_if_ne(InvalidProofReason::EqualityCheck(7), lhs, rhs)?;
325        }
326        {
327            let lhs = aux.combine(&proof.z1, &proof.z3)?;
328            let rhs = {
329                let s_to_e = aux.pow_mod(&commitment.s, challenge)?;
330                (&commitment.t * s_to_e).modulo(&aux.rsa_modulo)
331            };
332            fail_if_ne(InvalidProofReason::EqualityCheck(8), lhs, rhs)?;
333        }
334
335        fail_if(
336            InvalidProofReason::RangeCheck(9),
337            proof
338                .z1
339                .is_in_half_pm(&(Integer::one() << (security.l + security.epsilon))),
340        )?;
341
342        Ok(())
343    }
344
345    /// Generate random challenge
346    ///
347    /// `security` parameter is used to generate challenge in correct range
348    pub fn challenge<E: Curve>(rng: &mut impl RngCore) -> Challenge {
349        Integer::from_rng_half_pm(rng, &Integer::curve_order::<E>())
350    }
351}
352
353/// The non-interactive version of proof. Completed in one round, for example
354/// see the documentation of parent module.
355pub mod non_interactive {
356    use digest::Digest;
357    use generic_ec::Curve;
358
359    use crate::{Error, InvalidProof};
360
361    use super::{Aux, Challenge, Commitment, Data, NiProof, PrivateData, SecurityParams};
362
363    /// Compute proof for the given data, producing random commitment and
364    /// deriving deterministic challenge.
365    ///
366    /// Obtained from the above interactive proof via Fiat-Shamir heuristic.
367    pub fn prove<E: Curve, D: Digest>(
368        shared_state: &impl udigest::Digestable,
369        aux: &Aux,
370        data: Data<E>,
371        pdata: PrivateData<E>,
372        security: &SecurityParams,
373        rng: &mut impl rand_core::RngCore,
374    ) -> Result<NiProof<E>, Error> {
375        let (commitment, pcomm) = super::interactive::commit(aux, data, pdata, security, rng)?;
376        let challenge = challenge::<E, D>(shared_state, aux, data, &commitment, security);
377        let proof = super::interactive::prove(data, pdata, &pcomm, &challenge)?;
378        Ok(NiProof { commitment, proof })
379    }
380
381    /// Verify the proof, deriving challenge independently from same data
382    pub fn verify<E: Curve, D: Digest>(
383        shared_state: &impl udigest::Digestable,
384        aux: &Aux,
385        data: Data<E>,
386        proof: &NiProof<E>,
387        security: &SecurityParams,
388    ) -> Result<(), InvalidProof> {
389        let challenge = challenge::<E, D>(shared_state, aux, data, &proof.commitment, security);
390        super::interactive::verify(
391            aux,
392            data,
393            &proof.commitment,
394            security,
395            &challenge,
396            &proof.proof,
397        )
398    }
399
400    /// Deterministically compute challenge based on prior known values in protocol
401    pub fn challenge<E: Curve, D: Digest>(
402        shared_state: &impl udigest::Digestable,
403        aux: &Aux,
404        data: Data<E>,
405        commitment: &Commitment<E>,
406        security: &SecurityParams,
407    ) -> Challenge {
408        let tag = "paillier_zk.encryption_in_range_with_el_gamal.ni_challenge";
409        let seed = udigest::inline_struct!(tag {
410            shared_state,
411            aux: aux.digest_public_data(),
412            security,
413            data,
414            commitment,
415        });
416        let mut rng = rand_hash::HashRng::<D, _>::from_seed(seed);
417        super::interactive::challenge::<E>(&mut rng)
418    }
419}
420
421#[cfg(test)]
422mod test {
423    use fast_paillier::backend::Integer;
424    use generic_ec::{Curve, Point, Scalar};
425    use sha2::Digest;
426
427    use crate::common::{IntegerExt, InvalidProofReason};
428
429    fn run_with<E: Curve, D: Digest>(
430        mut rng: &mut impl rand_core::CryptoRngCore,
431        security: super::SecurityParams,
432        plaintext: Integer,
433    ) -> Result<(), crate::common::InvalidProof> {
434        let aux = crate::common::test::aux(&mut rng);
435
436        let private_key = crate::common::test::random_key(&mut rng).unwrap();
437        let a = Scalar::random(rng);
438        let pdata = super::PrivateData {
439            plaintext: &plaintext,
440            nonce: &Integer::sample_in_mult_group_of(rng, private_key.n()),
441            b: &Scalar::random(rng),
442        };
443
444        let data = super::Data {
445            key: private_key.encryption_key(),
446            ciphertext: &private_key
447                .encrypt_with(pdata.plaintext, pdata.nonce)
448                .unwrap(),
449            a: &(Point::generator() * a),
450            b: &(Point::generator() * pdata.b),
451            x: &(Point::generator() * (a * pdata.b + pdata.plaintext.to_scalar())),
452        };
453
454        let shared_state = "shared state";
455        let proof =
456            super::non_interactive::prove::<E, D>(&shared_state, &aux, data, pdata, &security, rng)
457                .unwrap();
458        super::non_interactive::verify::<E, D>(&shared_state, &aux, data, &proof, &security)
459    }
460
461    fn passing_test<C: Curve, D: Digest>() {
462        let mut rng = rand_dev::DevRng::new();
463        let security = super::SecurityParams {
464            l: 256,
465            epsilon: 512,
466        };
467        let plaintext = Integer::from_rng_half_pm(&mut rng, &(Integer::one() << security.l));
468        run_with::<C, D>(&mut rng, security, plaintext).expect("proof failed");
469    }
470
471    fn failing_test<C: Curve, D: Digest>() {
472        let mut rng = rand_dev::DevRng::new();
473        let security = super::SecurityParams {
474            l: 256,
475            epsilon: 512,
476        };
477        let plaintext = (Integer::one() << (security.l + security.epsilon - 1)) + 1;
478        let r = run_with::<C, D>(&mut rng, security, plaintext).expect_err("proof should not pass");
479        match r.reason() {
480            InvalidProofReason::RangeCheck(9) => (),
481            e => panic!("proof should not fail with: {e:?}"),
482        }
483    }
484
485    #[test]
486    fn passing_p256() {
487        passing_test::<generic_ec::curves::Secp256r1, sha2::Sha256>()
488    }
489    #[test]
490    fn failing_p256_add() {
491        failing_test::<generic_ec::curves::Secp256r1, sha2::Sha256>()
492    }
493
494    #[test]
495    fn passing_million() {
496        passing_test::<crate::curve::C, sha2::Sha256>()
497    }
498    #[test]
499    fn failing_million_add() {
500        failing_test::<crate::curve::C, sha2::Sha256>()
501    }
502}
paillier_zk/paillier_encryption_in_range_with_el_gamal.rs

paillier_zk/
paillier_encryption_in_range_with_el_gamal.rs
