elastic_elgamal/proofs/
log_equality.rs

1//! [`LogEqualityProof`] and related logic.
2
3use merlin::Transcript;
4use rand_core::{CryptoRng, RngCore};
5#[cfg(feature = "serde")]
6use serde::{Deserialize, Serialize};
7
8#[cfg(feature = "serde")]
9use crate::serde::ScalarHelper;
10use crate::{
11    alloc::{vec, Vec},
12    group::Group,
13    proofs::{TranscriptForGroup, VerificationError},
14    PublicKey, SecretKey,
15};
16
17/// Zero-knowledge proof of equality of two discrete logarithms in different bases,
18/// aka Chaum–Pedersen protocol.
19///
20/// # Construction
21///
22/// This proof is a result of the [Fiat–Shamir transform][fst] applied to a standard
23/// ZKP of equality of the two discrete logs in different bases.
24///
25/// - Public parameters of the proof are the two bases `G` and `K` in a prime-order group
26///   in which discrete log problem is believed to be hard.
27/// - Prover and verifier both know group elements `R` and `B`, which presumably have
28///   the same discrete log in bases `G` and `K` respectively.
29/// - Prover additionally knows the discrete log in question: `r = dlog_G(R) = dlog_K(B)`.
30///
31/// The interactive proof is specified as a sigma protocol (see, e.g., [this course])
32/// as follows:
33///
34/// 1. **Commitment:** The prover generates random scalar `x`. The prover sends to the verifier
35///    `X_G = [x]G` and `X_K = [x]K`.
36/// 2. **Challenge:** The verifier sends to the prover random scalar `c`.
37/// 3. **Response:** The prover computes scalar `s = x + cr` and sends it to the verifier.
38///
39/// Verification equations are:
40///
41/// ```text
42/// [s]G ?= X_G + [c]R;
43/// [s]K ?= X_K + [c]B.
44/// ```
45///
46/// In the non-interactive version of the proof, challenge `c` is derived from `hash(M)`,
47/// where `hash()` is a cryptographically secure hash function, and `M` is an optional message
48/// verified together with the proof (cf. public-key digital signatures). If `M` is set, we
49/// use a proof as a *signature of knowledge*. This allows to tie the proof to the context,
50/// so it cannot be (re)used in other contexts.
51///
52/// To reduce the size of the proof, we use the trick underpinning ring signature constructions.
53/// Namely, we represent the proof as `(c, s)`; during verification, we restore `X_G`, `X_K`
54/// from the original verification equations above.
55///
56/// # Implementation details
57///
58/// - The proof is serialized as 2 scalars: `(c, s)`.
59/// - Proof generation is constant-time. Verification is **not** constant-time.
60/// - Challenge `c` is derived using [`Transcript`] API.
61///
62/// # Examples
63///
64/// ```
65/// # use elastic_elgamal::{group::Ristretto, Keypair, SecretKey, LogEqualityProof};
66/// # use merlin::Transcript;
67/// # fn main() -> Result<(), Box<dyn std::error::Error>> {
68/// let mut rng = rand::rng();
69/// let (log_base, _) =
70///     Keypair::<Ristretto>::generate(&mut rng).into_tuple();
71/// let (power_g, discrete_log) =
72///     Keypair::<Ristretto>::generate(&mut rng).into_tuple();
73/// let power_k = log_base.as_element() * discrete_log.expose_scalar();
74///
75/// let proof = LogEqualityProof::new(
76///     &log_base,
77///     &discrete_log,
78///     (power_g.as_element(), power_k),
79///     &mut Transcript::new(b"custom_proof"),
80///     &mut rng,
81/// );
82/// proof.verify(
83///     &log_base,
84///     (power_g.as_element(), power_k),
85///     &mut Transcript::new(b"custom_proof"),
86/// )?;
87/// # Ok(())
88/// # }
89/// ```
90///
91/// [fst]: https://en.wikipedia.org/wiki/Fiat%E2%80%93Shamir_heuristic
92/// [this course]: http://www.cs.au.dk/~ivan/Sigma.pdf
93#[derive(Debug, Clone, Copy)]
94#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
95#[cfg_attr(feature = "serde", serde(bound = ""))]
96pub struct LogEqualityProof<G: Group> {
97    #[cfg_attr(feature = "serde", serde(with = "ScalarHelper::<G>"))]
98    challenge: G::Scalar,
99    #[cfg_attr(feature = "serde", serde(with = "ScalarHelper::<G>"))]
100    response: G::Scalar,
101}
102
103impl<G: Group> LogEqualityProof<G> {
104    /// Creates a new proof.
105    ///
106    /// # Parameters
107    ///
108    /// - `log_base` is the second discrete log base (`K` in the notation above). The first
109    ///   log base is always the [`Group`] generator.
110    /// - `secret` is the discrete log (`r` in the notation above).
111    /// - `powers` are `[r]G` and `[r]K`, respectively. It is **not** checked whether `r`
112    ///   is a discrete log of these powers; if this is not the case, the constructed proof
113    ///   will not [`verify`](Self::verify()).
114    pub fn new<R: CryptoRng + RngCore>(
115        log_base: &PublicKey<G>,
116        secret: &SecretKey<G>,
117        powers: (G::Element, G::Element),
118        transcript: &mut Transcript,
119        rng: &mut R,
120    ) -> Self {
121        transcript.start_proof(b"log_eq");
122        transcript.append_element_bytes(b"K", log_base.as_bytes());
123        transcript.append_element::<G>(b"[r]G", &powers.0);
124        transcript.append_element::<G>(b"[r]K", &powers.1);
125
126        let random_scalar = SecretKey::<G>::generate(rng);
127        transcript.append_element::<G>(b"[x]G", &G::mul_generator(random_scalar.expose_scalar()));
128        transcript.append_element::<G>(
129            b"[x]K",
130            &(log_base.as_element() * random_scalar.expose_scalar()),
131        );
132        let challenge = transcript.challenge_scalar::<G>(b"c");
133        let response = challenge * secret.expose_scalar() + random_scalar.expose_scalar();
134
135        Self {
136            challenge,
137            response,
138        }
139    }
140
141    /// Verifies this proof.
142    ///
143    /// # Parameters
144    ///
145    /// - `log_base` is the second discrete log base (`K` in the notation above). The first
146    ///   log base is always the [`Group`] generator.
147    /// - `powers` are group elements presumably equal to `[r]G` and `[r]K` respectively,
148    ///   where `r` is a secret scalar.
149    ///
150    /// # Errors
151    ///
152    /// Returns an error if this proof does not verify.
153    pub fn verify(
154        &self,
155        log_base: &PublicKey<G>,
156        powers: (G::Element, G::Element),
157        transcript: &mut Transcript,
158    ) -> Result<(), VerificationError> {
159        let commitments = (
160            G::vartime_double_mul_generator(&-self.challenge, powers.0, &self.response),
161            G::vartime_multi_mul(
162                &[-self.challenge, self.response],
163                [powers.1, log_base.as_element()],
164            ),
165        );
166
167        transcript.start_proof(b"log_eq");
168        transcript.append_element_bytes(b"K", log_base.as_bytes());
169        transcript.append_element::<G>(b"[r]G", &powers.0);
170        transcript.append_element::<G>(b"[r]K", &powers.1);
171        transcript.append_element::<G>(b"[x]G", &commitments.0);
172        transcript.append_element::<G>(b"[x]K", &commitments.1);
173        let expected_challenge = transcript.challenge_scalar::<G>(b"c");
174
175        if expected_challenge == self.challenge {
176            Ok(())
177        } else {
178            Err(VerificationError::ChallengeMismatch)
179        }
180    }
181
182    /// Serializes this proof into bytes. As described [above](#implementation-details),
183    /// the is serialized as 2 scalars: `(c, s)`, i.e., challenge and response.
184    pub fn to_bytes(self) -> Vec<u8> {
185        let mut bytes = vec![0_u8; 2 * G::SCALAR_SIZE];
186        G::serialize_scalar(&self.challenge, &mut bytes[..G::SCALAR_SIZE]);
187        G::serialize_scalar(&self.response, &mut bytes[G::SCALAR_SIZE..]);
188        bytes
189    }
190
191    /// Attempts to parse the proof from `bytes`. Returns `None` if `bytes` do not represent
192    /// a well-formed proof.
193    pub fn from_bytes(bytes: &[u8]) -> Option<Self> {
194        if bytes.len() != 2 * G::SCALAR_SIZE {
195            return None;
196        }
197
198        let challenge = G::deserialize_scalar(&bytes[..G::SCALAR_SIZE])?;
199        let response = G::deserialize_scalar(&bytes[G::SCALAR_SIZE..])?;
200        Some(Self {
201            challenge,
202            response,
203        })
204    }
205}
206
207#[cfg(test)]
208mod tests {
209    use super::*;
210    use crate::group::Ristretto;
211
212    type Keypair = crate::Keypair<Ristretto>;
213
214    #[test]
215    fn log_equality_basics() {
216        let mut rng = rand::rng();
217        let log_base = Keypair::generate(&mut rng).public().clone();
218
219        for _ in 0..100 {
220            let (generator_val, secret) = Keypair::generate(&mut rng).into_tuple();
221            let key_val = log_base.as_element() * secret.expose_scalar();
222            let proof = LogEqualityProof::new(
223                &log_base,
224                &secret,
225                (generator_val.as_element(), key_val),
226                &mut Transcript::new(b"testing_log_equality"),
227                &mut rng,
228            );
229
230            proof
231                .verify(
232                    &log_base,
233                    (generator_val.as_element(), key_val),
234                    &mut Transcript::new(b"testing_log_equality"),
235                )
236                .unwrap();
237        }
238    }
239}
elastic_elgamal/proofs/log_equality.rs

elastic_elgamal/proofs/
log_equality.rs
