elastic_elgamal/proofs/
possession.rs

1//! [`ProofOfPossession`] and related logic.
2
3use elliptic_curve::rand_core::{CryptoRng, RngCore};
4use merlin::Transcript;
5#[cfg(feature = "serde")]
6use serde::{Deserialize, Serialize};
7
8#[cfg(feature = "serde")]
9use crate::serde::{ScalarHelper, VecHelper};
10use crate::{
11    Keypair, PublicKey, SecretKey,
12    alloc::Vec,
13    group::Group,
14    proofs::{TranscriptForGroup, VerificationError},
15};
16
17/// Zero-knowledge proof of possession of one or more secret scalars.
18///
19/// # Construction
20///
21/// The proof is a generalization of the standard Schnorr protocol for proving knowledge
22/// of a discrete log. The difference with the combination of several concurrent Schnorr
23/// protocol instances is that the challenge is shared among all instances (which yields a
24/// ~2x proof size reduction).
25///
26/// # Implementation notes
27///
28/// - Proof generation is constant-time. Verification is **not** constant-time.
29///
30/// # Examples
31///
32/// ```
33/// # use elastic_elgamal::{group::Ristretto, Keypair, ProofOfPossession};
34/// # use merlin::Transcript;
35/// # fn main() -> Result<(), Box<dyn std::error::Error>> {
36/// let mut rng = rand::rng();
37/// let keypairs: Vec<_> =
38///     (0..5).map(|_| Keypair::<Ristretto>::generate(&mut rng)).collect();
39///
40/// // Prove possession of the generated key pairs.
41/// let proof = ProofOfPossession::new(
42///     &keypairs,
43///     &mut Transcript::new(b"custom_proof"),
44///     &mut rng,
45/// );
46/// proof.verify(
47///     keypairs.iter().map(Keypair::public),
48///     &mut Transcript::new(b"custom_proof"),
49/// )?;
50///
51/// // If we change the context of the `Transcript`, the proof will not verify.
52/// assert!(proof
53///     .verify(
54///         keypairs.iter().map(Keypair::public),
55///         &mut Transcript::new(b"other_proof"),
56///     )
57///     .is_err());
58/// // Likewise if the public keys are reordered.
59/// assert!(proof
60///     .verify(
61///         keypairs.iter().rev().map(Keypair::public),
62///         &mut Transcript::new(b"custom_proof"),
63///     )
64///     .is_err());
65/// # Ok(())
66/// # }
67/// ```
68#[derive(Debug, Clone)]
69#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
70#[cfg_attr(feature = "serde", serde(bound = ""))]
71pub struct ProofOfPossession<G: Group> {
72    #[cfg_attr(feature = "serde", serde(with = "ScalarHelper::<G>"))]
73    challenge: G::Scalar,
74    #[cfg_attr(feature = "serde", serde(with = "VecHelper::<ScalarHelper<G>, 1>"))]
75    responses: Vec<G::Scalar>,
76}
77
78impl<G: Group> ProofOfPossession<G> {
79    /// Creates a proof of possession with the specified `keypairs`.
80    pub fn new<R: CryptoRng + RngCore>(
81        keypairs: &[Keypair<G>],
82        transcript: &mut Transcript,
83        rng: &mut R,
84    ) -> Self {
85        Self::from_keys(
86            keypairs.iter().map(Keypair::secret),
87            keypairs.iter().map(Keypair::public),
88            transcript,
89            rng,
90        )
91    }
92
93    pub(crate) fn from_keys<'a, R: CryptoRng + RngCore>(
94        secrets: impl Iterator<Item = &'a SecretKey<G>>,
95        public_keys: impl Iterator<Item = &'a PublicKey<G>>,
96        transcript: &mut Transcript,
97        rng: &mut R,
98    ) -> Self {
99        transcript.start_proof(b"multi_pop");
100        let mut key_count = 0;
101        for public_key in public_keys {
102            transcript.append_element_bytes(b"K", public_key.as_bytes());
103            key_count += 1;
104        }
105
106        let random_scalars: Vec<_> = (0..key_count)
107            .map(|_| {
108                let randomness = SecretKey::<G>::generate(rng);
109                let random_element = G::mul_generator(randomness.expose_scalar());
110                transcript.append_element::<G>(b"R", &random_element);
111                randomness
112            })
113            .collect();
114
115        let challenge = transcript.challenge_scalar::<G>(b"c");
116        let responses = secrets
117            .zip(random_scalars)
118            .map(|(log, mut randomness)| {
119                randomness += log * &challenge;
120                *randomness.expose_scalar()
121            })
122            .collect();
123
124        Self {
125            challenge,
126            responses,
127        }
128    }
129
130    /// Verifies this proof against the provided `public_keys`.
131    ///
132    /// # Errors
133    ///
134    /// Returns an error if this proof does not verify.
135    pub fn verify<'a>(
136        &self,
137        public_keys: impl Iterator<Item = &'a PublicKey<G>> + Clone,
138        transcript: &mut Transcript,
139    ) -> Result<(), VerificationError> {
140        let mut key_count = 0;
141        transcript.start_proof(b"multi_pop");
142        for public_key in public_keys.clone() {
143            transcript.append_element_bytes(b"K", public_key.as_bytes());
144            key_count += 1;
145        }
146        VerificationError::check_lengths("public keys", self.responses.len(), key_count)?;
147
148        for (public_key, response) in public_keys.zip(&self.responses) {
149            let random_element = G::vartime_double_mul_generator(
150                &-self.challenge,
151                public_key.as_element(),
152                response,
153            );
154            transcript.append_element::<G>(b"R", &random_element);
155        }
156
157        let expected_challenge = transcript.challenge_scalar::<G>(b"c");
158        if expected_challenge == self.challenge {
159            Ok(())
160        } else {
161            Err(VerificationError::ChallengeMismatch)
162        }
163    }
164}
165
166#[cfg(test)]
167mod tests {
168    use super::*;
169    use crate::group::Ristretto;
170
171    type Keypair = crate::Keypair<Ristretto>;
172
173    #[test]
174    fn proof_of_possession_basics() {
175        let mut rng = rand::rng();
176        let poly: Vec<_> = (0..5).map(|_| Keypair::generate(&mut rng)).collect();
177
178        ProofOfPossession::new(&poly, &mut Transcript::new(b"test_multi_PoP"), &mut rng)
179            .verify(
180                poly.iter().map(Keypair::public),
181                &mut Transcript::new(b"test_multi_PoP"),
182            )
183            .unwrap();
184    }
185}
elastic_elgamal/proofs/possession.rs

elastic_elgamal/proofs/
possession.rs
