paillier_zk/
dlog_with_el_gamal_commitment.rs

1//! ZK-proof of discrete log with El-Gamal commitment.
2//! Called Пelog or Relog in the CGGMP24 papers.
3//!
4//! ## Description
5//!
6//! Common inputs:
7//! - Curve `E` with generator $G$ of prime subgroup of size $q$
8//! - $L, M, X, Y, H$ are points on curve `E`
9//!
10//! Prover has secret inputs $y, \lambda$ (scalars modulo $q$) such that $L = \lambda G,
11//! M = \lambda X + y G, Y = y H$
12//!
13//! ## Example
14//!
15//! ```rust
16//! use paillier_zk::{dlog_with_el_gamal_commitment as p};
17//! use generic_ec::{Point, Scalar, curves::Secp256k1 as E};
18//!
19//! # fn main() -> Result<(), Box<dyn std::error::Error>> {
20//! // Prover and verifier have a shared protocol state
21//! let shared_state = "some shared state";
22//!
23//! let mut rng = rand_core::OsRng;
24//! # let mut rng = rand_dev::DevRng::new();
25//!
26//! // Prover knows lambda, y
27//!
28//! let pdata = p::PrivateData {
29//!     lambda: &Scalar::random(&mut rng),
30//!     y: &Scalar::random(&mut rng),
31//! };
32//!
33//! // Common data known by both prover and verifier:
34//!
35//! let x = Point::generator() * Scalar::random(&mut rng);
36//! let h = Point::generator() * Scalar::random(&mut rng);
37//!
38//! let data = p::Data {
39//!     l: &(Point::generator() * pdata.lambda),
40//!     m: &(Point::generator() * pdata.y + x * pdata.lambda),
41//!     x: &x,
42//!     y: &(h * pdata.y),
43//!     h: &h,
44//! };
45//!
46//! // Generate non-interactive proof
47//! let proof =
48//!     p::non_interactive::prove::<E, sha2::Sha256>(
49//!         &shared_state,
50//!         data,
51//!         pdata,
52//!         &mut rng,
53//!     )?;
54//!
55//! // Proof and the data are sent to the verifier
56//!
57//! # use generic_ec::Curve;
58//! # fn send<E: Curve>(_: &p::Data<E>, _: &p::NiProof<E>) {  }
59//! send(&data, &proof);
60//!
61//! // Verifier receives the data and the proof and verifies them
62//!
63//! # let recv = || (data, proof);
64//! let (data, proof) = recv();
65//! let r = p::non_interactive::verify::<E, sha2::Sha256>(
66//!     &shared_state,
67//!     data,
68//!     &proof,
69//! )?;
70//! #
71//! # Ok(()) }
72//! ```
73//!
74//! If the verification succeeded, verifier can continue communication with prover
75
76use generic_ec::{Curve, Point, Scalar};
77
78#[cfg(feature = "serde")]
79use serde::{Deserialize, Serialize};
80
81pub use crate::common::{Aux, InvalidProof};
82
83/// Public data that both parties know
84#[derive(Debug, Clone, Copy, udigest::Digestable)]
85#[udigest(bound = "")]
86pub struct Data<'a, E: Curve> {
87    /// L in paper, obtained as g^\lambda
88    pub l: &'a Point<E>,
89    /// M in paper, obtained as g^y X^\lambda
90    pub m: &'a Point<E>,
91    /// X in paper
92    pub x: &'a Point<E>,
93    /// Y in paper, obtained as h^y
94    pub y: &'a Point<E>,
95    /// h in paper
96    pub h: &'a Point<E>,
97}
98
99/// Private data of prover
100#[derive(Clone, Copy)]
101pub struct PrivateData<'a, E: Curve> {
102    /// y or epsilon in paper, log of Y base h
103    pub y: &'a Scalar<E>,
104    /// lambda in paper, preimage of L
105    pub lambda: &'a Scalar<E>,
106}
107
108/// Prover's first message, obtained by [`interactive::commit`]
109#[derive(Debug, Clone, udigest::Digestable)]
110#[udigest(bound = "")]
111#[cfg_attr(feature = "serde", derive(Serialize, Deserialize), serde(bound = ""))]
112pub struct Commitment<E: Curve> {
113    pub a: Point<E>,
114    pub n: Point<E>,
115    pub b: Point<E>,
116}
117
118/// Prover's data accompanying the commitment. Kept as state between rounds in
119/// the interactive protocol.
120#[derive(Clone)]
121pub struct PrivateCommitment<E: Curve> {
122    pub alpha: Scalar<E>,
123    pub m: Scalar<E>,
124}
125
126/// Verifier's challenge to prover. Can be obtained deterministically by
127/// [`non_interactive::challenge`] or randomly by [`interactive::challenge`]
128pub type Challenge<E> = Scalar<E>;
129
130/// The ZK proof. Computed by [`interactive::prove`].
131#[derive(Debug, Clone)]
132#[cfg_attr(feature = "serde", derive(Serialize, Deserialize), serde(bound = ""))]
133pub struct Proof<E: Curve> {
134    pub z: Scalar<E>,
135    pub u: Scalar<E>,
136}
137
138/// The non-interactive ZK proof. Computed by [`non_interactive::prove`].
139#[derive(Debug, Clone)]
140#[cfg_attr(feature = "serde", derive(Serialize, Deserialize), serde(bound = ""))]
141pub struct NiProof<E: Curve> {
142    pub commitment: Commitment<E>,
143    pub proof: Proof<E>,
144}
145
146/// The interactive version of the ZK proof. Should be completed in 3 rounds:
147/// prover commits to data, verifier responds with a random challenge, and
148/// prover gives proof with commitment and challenge.
149pub mod interactive {
150    use generic_ec::{Curve, Point, Scalar};
151    use rand_core::RngCore;
152
153    use crate::common::{fail_if_ne, InvalidProof, InvalidProofReason};
154    use crate::Error;
155
156    use super::*;
157
158    /// Create random commitment
159    pub fn commit<E: Curve>(
160        data: Data<E>,
161        rng: &mut impl RngCore,
162    ) -> Result<(Commitment<E>, PrivateCommitment<E>), Error> {
163        let alpha = Scalar::random(rng);
164        let m = Scalar::random(rng);
165
166        let a = Point::<E>::generator() * alpha;
167        let n = Point::<E>::generator() * m + data.x * alpha;
168        let b = data.h * m;
169
170        let commitment = Commitment { a, n, b };
171        let private_commitment = PrivateCommitment { alpha, m };
172        Ok((commitment, private_commitment))
173    }
174
175    /// Compute proof for given data and prior protocol values
176    pub fn prove<E: Curve>(
177        pdata: PrivateData<E>,
178        pcomm: &PrivateCommitment<E>,
179        challenge: &Challenge<E>,
180    ) -> Result<Proof<E>, Error> {
181        let z = pcomm.alpha + challenge * pdata.lambda;
182        let u = pcomm.m + challenge * pdata.y;
183        Ok(Proof { z, u })
184    }
185
186    /// Verify the proof
187    pub fn verify<E: Curve>(
188        data: Data<E>,
189        commitment: &Commitment<E>,
190        challenge: &Challenge<E>,
191        proof: &Proof<E>,
192    ) -> Result<(), InvalidProof> {
193        // Three equality checks
194        {
195            let lhs = Point::<E>::generator() * proof.z;
196            let rhs = commitment.a + data.l * challenge;
197            fail_if_ne(InvalidProofReason::EqualityCheck(1), lhs, rhs)?;
198        }
199        {
200            let lhs = Point::<E>::generator() * proof.u + data.x * proof.z;
201            let rhs = commitment.n + data.m * challenge;
202            fail_if_ne(InvalidProofReason::EqualityCheck(2), lhs, rhs)?;
203        }
204        {
205            let lhs = data.h * proof.u;
206            let rhs = commitment.b + data.y * challenge;
207            fail_if_ne(InvalidProofReason::EqualityCheck(3), lhs, rhs)?;
208        }
209
210        Ok(())
211    }
212
213    /// Generate random challenge
214    pub fn challenge<E: Curve>(rng: &mut impl RngCore) -> Challenge<E> {
215        Scalar::random(rng)
216    }
217}
218
219/// The non-interactive version of proof. Completed in one round, for example
220/// see the documentation of parent module.
221pub mod non_interactive {
222    use digest::Digest;
223    use generic_ec::Curve;
224
225    use crate::{Error, InvalidProof};
226
227    use super::{Challenge, Commitment, Data, NiProof, PrivateData};
228
229    /// Compute proof for the given data, producing random commitment and
230    /// deriving deterministic challenge.
231    ///
232    /// Obtained from the above interactive proof via Fiat-Shamir heuristic.
233    pub fn prove<E: Curve, D: Digest>(
234        shared_state: &impl udigest::Digestable,
235        data: Data<E>,
236        pdata: PrivateData<E>,
237        rng: &mut impl rand_core::RngCore,
238    ) -> Result<NiProof<E>, Error> {
239        let (commitment, pcomm) = super::interactive::commit(data, rng)?;
240        let challenge = challenge::<E, D>(shared_state, data, &commitment);
241        let proof = super::interactive::prove::<E>(pdata, &pcomm, &challenge)?;
242        Ok(NiProof { commitment, proof })
243    }
244
245    /// Verify the proof, deriving challenge independently from same data
246    pub fn verify<E: Curve, D: Digest>(
247        shared_state: &impl udigest::Digestable,
248        data: Data<E>,
249        proof: &NiProof<E>,
250    ) -> Result<(), InvalidProof> {
251        let challenge = challenge::<E, D>(shared_state, data, &proof.commitment);
252        super::interactive::verify::<E>(data, &proof.commitment, &challenge, &proof.proof)
253    }
254
255    /// Deterministically compute challenge based on prior known values in protocol
256    pub fn challenge<E: Curve, D: Digest>(
257        shared_state: &impl udigest::Digestable,
258        data: Data<E>,
259        commitment: &Commitment<E>,
260    ) -> Challenge<E> {
261        let tag = "paillier_zk.dlog_with_el_gamal.ni_challenge";
262        let seed = udigest::inline_struct!(tag {
263            shared_state,
264            data,
265            commitment,
266        });
267        let mut rng = rand_hash::HashRng::<D, _>::from_seed(seed);
268        super::interactive::challenge(&mut rng)
269    }
270}
271
272#[cfg(test)]
273mod test {
274    use generic_ec::{Curve, Point, Scalar};
275    use sha2::Digest;
276
277    use crate::common::InvalidProofReason;
278
279    fn run<E: Curve, D: Digest>(
280        rng: &mut impl rand_core::CryptoRngCore,
281        data: super::Data<E>,
282        pdata: super::PrivateData<E>,
283    ) -> Result<(), crate::common::InvalidProof> {
284        let shared_state = "shared state";
285
286        let proof = super::non_interactive::prove::<E, D>(&shared_state, data, pdata, rng).unwrap();
287        super::non_interactive::verify::<E, D>(&shared_state, data, &proof)
288    }
289
290    fn passing_test<E: Curve, D: Digest>() {
291        let mut rng = rand_dev::DevRng::new();
292
293        let pdata = super::PrivateData {
294            y: &Scalar::random(&mut rng),
295            lambda: &Scalar::random(&mut rng),
296        };
297
298        let h = Point::<E>::generator() * Scalar::random(&mut rng);
299        let x = Point::<E>::generator() * Scalar::random(&mut rng);
300
301        let data = super::Data {
302            l: &(Point::<E>::generator() * pdata.lambda),
303            m: &(Point::<E>::generator() * pdata.y + x * pdata.lambda),
304            x: &x,
305            y: &(h * pdata.y),
306            h: &h,
307        };
308        run::<E, D>(&mut rng, data, pdata).expect("proof failed");
309    }
310
311    fn failing_check_lambda_<E: Curve, D: Digest>() {
312        // Scenario where the prover P does not know lambda
313        let mut rng = rand_dev::DevRng::new();
314
315        let mut pdata = super::PrivateData {
316            y: &Scalar::random(&mut rng),
317            lambda: &Scalar::random(&mut rng),
318        };
319
320        let h = Point::<E>::generator() * Scalar::random(&mut rng);
321        let x = Point::<E>::generator() * Scalar::random(&mut rng);
322
323        let data = super::Data {
324            l: &(Point::<E>::generator() * pdata.lambda),
325            m: &(Point::<E>::generator() * pdata.y + x * pdata.lambda),
326            x: &x,
327            y: &(h * pdata.y),
328            h: &h,
329        };
330
331        // Replace lambda with another value
332        let fake_lambda = Scalar::random(&mut rng);
333        pdata.lambda = &fake_lambda;
334
335        let err = run::<E, D>(&mut rng, data, pdata).expect_err("proof should not pass");
336        match err.reason() {
337            InvalidProofReason::EqualityCheck(1) => (),
338            e => panic!("proof should not fail with {e:?}"),
339        }
340    }
341
342    fn failing_check_y_<E: Curve, D: Digest>() {
343        // Scenario where the prover P does not know y
344        let mut rng = rand_dev::DevRng::new();
345
346        let mut pdata = super::PrivateData {
347            y: &Scalar::random(&mut rng),
348            lambda: &Scalar::random(&mut rng),
349        };
350
351        let h = Point::<E>::generator() * Scalar::random(&mut rng);
352        let x = Point::<E>::generator() * Scalar::random(&mut rng);
353
354        let data = super::Data {
355            l: &(Point::<E>::generator() * pdata.lambda),
356            m: &(Point::<E>::generator() * pdata.y + x * pdata.lambda),
357            x: &x,
358            y: &(h * pdata.y),
359            h: &h,
360        };
361
362        // Replace y with another value
363        let fake_y = Scalar::random(&mut rng);
364        pdata.y = &fake_y;
365
366        let r = run::<E, D>(&mut rng, data, pdata).expect_err("proof should not pass");
367        match r.reason() {
368            InvalidProofReason::EqualityCheck(2) => (),
369            e => panic!("proof should not fail with {e:?}"),
370        }
371    }
372
373    #[test]
374    fn passing_p256() {
375        passing_test::<generic_ec::curves::Secp256r1, sha2::Sha256>()
376    }
377
378    #[test]
379    fn passing_million() {
380        passing_test::<crate::curve::C, sha2::Sha256>()
381    }
382    #[test]
383    fn failing_check_1_p256() {
384        failing_check_lambda_::<generic_ec::curves::Secp256r1, sha2::Sha256>()
385    }
386
387    #[test]
388    fn failing_check_1_million() {
389        failing_check_lambda_::<crate::curve::C, sha2::Sha256>()
390    }
391    #[test]
392    fn failing_check_2_p256() {
393        failing_check_y_::<generic_ec::curves::Secp256r1, sha2::Sha256>()
394    }
395
396    #[test]
397    fn failing_check_2_million() {
398        failing_check_y_::<crate::curve::C, sha2::Sha256>()
399    }
400}
paillier_zk/dlog_with_el_gamal_commitment.rs

paillier_zk/
dlog_with_el_gamal_commitment.rs
