elastic_elgamal/proofs/
commitment.rs

1//! Zero-knowledge proof of ElGamal encryption and Pedersen commitment equivalence.
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;
10use crate::{
11    Ciphertext, CiphertextWithValue, PublicKey, SecretKey,
12    group::Group,
13    proofs::{TranscriptForGroup, VerificationError},
14};
15
16/// Zero-knowledge proof that an ElGamal ciphertext encrypts the same value as a Pedersen
17/// commitment.
18///
19/// This proof can be used to switch from frameworks applicable to ElGamal ciphertexts, to ones
20/// applicable to Pedersen commitments (e.g., [Bulletproofs] for range proofs).
21///
22/// [Bulletproofs]: https://crypto.stanford.edu/bulletproofs/
23///
24/// # Construction
25///
26/// We want to prove in zero knowledge the knowledge of scalars `r_e`, `v`, `r_c` such as
27///
28/// ```text
29/// R = [r_e]G; B = [v]G + [r_e]K;
30/// // (R, B) is ElGamal ciphertext of `v` for public key `K`
31/// C = [v]G + [r_c]H;
32/// // C is Pedersen commitment to `v`
33/// ```
34///
35/// Here, we assume that the conventional group generator `G` is shared between encryption and
36/// commitment protocols.
37///
38/// An interactive version of the proof can be built as a sigma protocol:
39///
40/// 1. **Commitment.** The prover generates 3 random scalars `e_r`, `e_v` and `e_c` and commits
41///    to them via `E_r = [e_r]G`, `E_b = [e_v]G + [e_r]K`, and `E_c = [e_v]G + [e_c]H`.
42/// 2. **Challenge.** The verifier sends to the prover random scalar `c`.
43/// 3. **Response.** The prover computes the following scalars and sends them to the verifier.
44///
45/// ```text
46/// s_r = e_r + c * r_e;
47/// s_v = e_v + c * v;
48/// s_c = e_c + c * r_c;
49/// ```
50///
51/// The verification equations are
52///
53/// ```text
54/// [s_r]G ?= E_r + [c]R;
55/// [s_v]G + [s_r]K ?= E_b + [c]B;
56/// [s_v]G + [s_c]H ?= E_c + [c]C;
57/// ```
58///
59/// A non-interactive version of the proof is obtained by applying [Fiat–Shamir transform][fst].
60/// As with other proofs, it is more efficient to represent a proof as the challenge
61/// and responses (i.e., 4 scalars in total).
62///
63/// [fst]: https://en.wikipedia.org/wiki/Fiat%E2%80%93Shamir_heuristic
64///
65/// # Examples
66///
67/// ```
68/// # use elastic_elgamal::{
69/// #     group::{ElementOps, ScalarOps, Group, Ristretto},
70/// #     Keypair, SecretKey, CommitmentEquivalenceProof, CiphertextWithValue,
71/// # };
72/// # use merlin::Transcript;
73/// #
74/// # const BLINDING_BASE: &[u8] = &[
75/// #     140, 146, 64, 180, 86, 169, 230, 220, 101, 195, 119, 161, 4,
76/// #     141, 116, 95, 148, 160, 140, 219, 127, 68, 203, 205, 123, 70,
77/// #     243, 64, 72, 135, 17, 52,
78/// # ];
79/// # fn main() -> Result<(), Box<dyn std::error::Error>> {
80/// let blinding_base = // Blinding base for Pedersen commitments
81///                     // (e.g., from Bulletproofs)
82/// #    Ristretto::deserialize_element(BLINDING_BASE).unwrap();
83/// let mut rng = rand::rng();
84/// let (receiver, _) = Keypair::<Ristretto>::generate(&mut rng).into_tuple();
85///
86/// // Create an ElGamal ciphertext of `value` for `receiver`.
87/// let value = 424242_u64;
88/// let ciphertext = CiphertextWithValue::new(value, &receiver, &mut rng)
89///     .generalize();
90/// // Create a blinding factor for the Pedersen commitment of the same value.
91/// let blinding = SecretKey::generate(&mut rng);
92/// let (proof, commitment) = CommitmentEquivalenceProof::new(
93///     &ciphertext,
94///     &receiver,
95///     &blinding,
96///     blinding_base,
97///     &mut Transcript::new(b"custom_proof"),
98///     &mut rng,
99/// );
100/// // Use `commitment` and `blinding` in other proofs...
101///
102/// proof.verify(
103///     &ciphertext.into(),
104///     &receiver,
105///     commitment,
106///     blinding_base,
107///     &mut Transcript::new(b"custom_proof"),
108/// )?;
109/// # Ok(())
110/// # }
111/// ```
112#[derive(Debug, Clone)]
113#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
114#[cfg_attr(feature = "serde", serde(bound = ""))]
115pub struct CommitmentEquivalenceProof<G: Group> {
116    #[cfg_attr(feature = "serde", serde(with = "ScalarHelper::<G>"))]
117    challenge: G::Scalar,
118    #[cfg_attr(feature = "serde", serde(with = "ScalarHelper::<G>"))]
119    randomness_response: G::Scalar,
120    #[cfg_attr(feature = "serde", serde(with = "ScalarHelper::<G>"))]
121    value_response: G::Scalar,
122    #[cfg_attr(feature = "serde", serde(with = "ScalarHelper::<G>"))]
123    commitment_response: G::Scalar,
124}
125
126impl<G: Group> CommitmentEquivalenceProof<G> {
127    /// Creates a proof based on the `ciphertext` for `receiver` and `commitment_blinding`
128    /// with `commitment_blinding_base` for a Pedersen commitment. (The latter two args
129    /// correspond to `r_c` and `H` in the [*Construction*](#construction) section, respectively.)
130    ///
131    /// # Return value
132    ///
133    /// Returns a proof together with the Pedersen commitment.
134    pub fn new<R: RngCore + CryptoRng>(
135        ciphertext: &CiphertextWithValue<G>,
136        receiver: &PublicKey<G>,
137        commitment_blinding: &SecretKey<G>,
138        commitment_blinding_base: G::Element,
139        transcript: &mut Transcript,
140        rng: &mut R,
141    ) -> (Self, G::Element) {
142        let commitment = G::multi_mul(
143            [ciphertext.value(), commitment_blinding.expose_scalar()],
144            [G::generator(), commitment_blinding_base],
145        );
146
147        transcript.start_proof(b"commitment_equivalence");
148        transcript.append_element_bytes(b"K", receiver.as_bytes());
149        transcript.append_element::<G>(b"R", &ciphertext.inner().random_element);
150        transcript.append_element::<G>(b"B", &ciphertext.inner().blinded_element);
151        transcript.append_element::<G>(b"C", &commitment);
152
153        let random_scalar = SecretKey::<G>::generate(rng);
154        let value_scalar = SecretKey::<G>::generate(rng);
155        let commitment_scalar = SecretKey::<G>::generate(rng);
156        let random_commitment = G::mul_generator(random_scalar.expose_scalar());
157        transcript.append_element::<G>(b"[e_r]G", &random_commitment);
158
159        let value_element = G::mul_generator(value_scalar.expose_scalar());
160        let enc_blinding_commitment =
161            value_element + receiver.as_element() * random_scalar.expose_scalar();
162        transcript.append_element::<G>(b"[e_v]G + [e_r]K", &enc_blinding_commitment);
163        let commitment_commitment =
164            value_element + commitment_blinding_base * commitment_scalar.expose_scalar();
165        transcript.append_element::<G>(b"[e_v]G + [e_c]H", &commitment_commitment);
166
167        let challenge = transcript.challenge_scalar::<G>(b"c");
168        let randomness_response =
169            challenge * ciphertext.randomness().expose_scalar() + random_scalar.expose_scalar();
170        let value_response = challenge * ciphertext.value() + value_scalar.expose_scalar();
171        let commitment_response =
172            challenge * commitment_blinding.expose_scalar() + commitment_scalar.expose_scalar();
173
174        let proof = Self {
175            challenge,
176            randomness_response,
177            value_response,
178            commitment_response,
179        };
180        (proof, commitment)
181    }
182
183    /// # Errors
184    ///
185    /// Returns an error if this proof does not verify.
186    pub fn verify(
187        &self,
188        ciphertext: &Ciphertext<G>,
189        receiver: &PublicKey<G>,
190        commitment: G::Element,
191        commitment_blinding_base: G::Element,
192        transcript: &mut Transcript,
193    ) -> Result<(), VerificationError> {
194        transcript.start_proof(b"commitment_equivalence");
195        transcript.append_element_bytes(b"K", receiver.as_bytes());
196        transcript.append_element::<G>(b"R", &ciphertext.random_element);
197        transcript.append_element::<G>(b"B", &ciphertext.blinded_element);
198        transcript.append_element::<G>(b"C", &commitment);
199
200        let neg_challenge = -self.challenge;
201        let random_commitment = G::vartime_double_mul_generator(
202            &neg_challenge,
203            ciphertext.random_element,
204            &self.randomness_response,
205        );
206        transcript.append_element::<G>(b"[e_r]G", &random_commitment);
207
208        let enc_blinding_commitment = G::vartime_multi_mul(
209            [
210                &self.value_response,
211                &self.randomness_response,
212                &neg_challenge,
213            ],
214            [
215                G::generator(),
216                receiver.as_element(),
217                ciphertext.blinded_element,
218            ],
219        );
220        transcript.append_element::<G>(b"[e_v]G + [e_r]K", &enc_blinding_commitment);
221
222        let commitment_commitment = G::vartime_multi_mul(
223            [
224                &self.value_response,
225                &self.commitment_response,
226                &neg_challenge,
227            ],
228            [G::generator(), commitment_blinding_base, commitment],
229        );
230        transcript.append_element::<G>(b"[e_v]G + [e_c]H", &commitment_commitment);
231
232        let expected_challenge = transcript.challenge_scalar::<G>(b"c");
233        if expected_challenge == self.challenge {
234            Ok(())
235        } else {
236            Err(VerificationError::ChallengeMismatch)
237        }
238    }
239}
240
241#[cfg(all(test, feature = "curve25519-dalek"))]
242mod tests {
243    use bulletproofs::PedersenGens;
244
245    use super::*;
246    use crate::{
247        Keypair,
248        group::{ElementOps, Ristretto},
249    };
250
251    fn downgrade_scalar(x: curve25519_dalek::Scalar) -> bulletproofs_curve::Scalar {
252        bulletproofs_curve::Scalar::from_bytes_mod_order(x.to_bytes())
253    }
254
255    fn upgrade_point(x: bulletproofs_curve::RistrettoPoint) -> curve25519_dalek::RistrettoPoint {
256        let compressed = curve25519_dalek::ristretto::CompressedRistretto(x.compress().0);
257        compressed.decompress().unwrap()
258    }
259
260    #[test]
261    fn equivalence_proof_basics() {
262        let mut rng = rand::rng();
263        let (receiver, _) = Keypair::<Ristretto>::generate(&mut rng).into_tuple();
264        let value = 1234_u64;
265        let ciphertext = CiphertextWithValue::new(value, &receiver, &mut rng).generalize();
266
267        let commitment_gens = PedersenGens::default();
268        assert_eq!(upgrade_point(commitment_gens.B), Ristretto::generator());
269        let blinding = SecretKey::generate(&mut rng);
270
271        let (proof, commitment) = CommitmentEquivalenceProof::new(
272            &ciphertext,
273            &receiver,
274            &blinding,
275            upgrade_point(commitment_gens.B_blinding),
276            &mut Transcript::new(b"test"),
277            &mut rng,
278        );
279        assert_eq!(
280            commitment,
281            upgrade_point(commitment_gens.commit(
282                downgrade_scalar(*ciphertext.value()),
283                downgrade_scalar(*blinding.expose_scalar()),
284            ))
285        );
286
287        let ciphertext = ciphertext.into();
288        proof
289            .verify(
290                &ciphertext,
291                &receiver,
292                commitment,
293                upgrade_point(commitment_gens.B_blinding),
294                &mut Transcript::new(b"test"),
295            )
296            .unwrap();
297
298        let other_ciphertext = receiver.encrypt(8_u64, &mut rng);
299        let err = proof
300            .verify(
301                &other_ciphertext,
302                &receiver,
303                commitment,
304                upgrade_point(commitment_gens.B_blinding),
305                &mut Transcript::new(b"test"),
306            )
307            .unwrap_err();
308        assert!(matches!(err, VerificationError::ChallengeMismatch));
309
310        let err = proof
311            .verify(
312                &ciphertext,
313                &receiver,
314                commitment + Ristretto::generator(),
315                upgrade_point(commitment_gens.B_blinding),
316                &mut Transcript::new(b"test"),
317            )
318            .unwrap_err();
319        assert!(matches!(err, VerificationError::ChallengeMismatch));
320
321        let err = proof
322            .verify(
323                &ciphertext,
324                &receiver,
325                commitment,
326                upgrade_point(commitment_gens.B_blinding),
327                &mut Transcript::new(b"other_test"),
328            )
329            .unwrap_err();
330        assert!(matches!(err, VerificationError::ChallengeMismatch));
331    }
332}
elastic_elgamal/proofs/commitment.rs

elastic_elgamal/proofs/
commitment.rs
