delegatable_credentials/
mercurial_sig.rs

1//! Mercurial signatures as defined in section 3 of [this paper](https://eprint.iacr.org/2018/923.pdf).
2//! Implements 2 variations of the algorithms, one where signature is in group G1 and public key in group G2
3//! and the other where signature is in group G2 and public key in group G1
4
5use ark_ec::{pairing::Pairing, AffineRepr, CurveGroup, Group, VariableBaseMSM};
6use ark_ff::{
7    field_hashers::{DefaultFieldHasher, HashToField},
8    Field, PrimeField, Zero,
9};
10use ark_serialize::{CanonicalDeserialize, CanonicalSerialize};
11use ark_std::{cfg_iter, fmt::Debug, rand::RngCore, vec::Vec, UniformRand};
12use digest::DynDigest;
13
14use zeroize::{Zeroize, ZeroizeOnDrop};
15
16use dock_crypto_utils::serde_utils::*;
17
18use serde::{Deserialize, Serialize};
19use serde_with::serde_as;
20
21use dock_crypto_utils::msm::WindowTable;
22
23#[cfg(feature = "parallel")]
24use rayon::prelude::*;
25
26use crate::error::DelegationError;
27
28/// Secret key used by the signer to sign messages
29#[serde_as]
30#[derive(
31    Clone,
32    PartialEq,
33    Eq,
34    Debug,
35    CanonicalSerialize,
36    CanonicalDeserialize,
37    Serialize,
38    Deserialize,
39    Zeroize,
40    ZeroizeOnDrop,
41)]
42pub struct SecretKey<E: Pairing>(#[serde_as(as = "Vec<ArkObjectBytes>")] pub Vec<E::ScalarField>);
43
44/// Public key used to verify `Signature`
45#[serde_as]
46#[derive(
47    Clone, PartialEq, Eq, Debug, CanonicalSerialize, CanonicalDeserialize, Serialize, Deserialize,
48)]
49pub struct PublicKey<E: Pairing>(#[serde_as(as = "Vec<ArkObjectBytes>")] pub Vec<E::G2Affine>);
50
51/// Public key used to verify `SignatureG2`
52#[serde_as]
53#[derive(
54    Clone, PartialEq, Eq, Debug, CanonicalSerialize, CanonicalDeserialize, Serialize, Deserialize,
55)]
56pub struct PublicKeyG1<E: Pairing>(#[serde_as(as = "Vec<ArkObjectBytes>")] pub Vec<E::G1Affine>);
57
58/// Prepared version of `PublicKey` for faster pairing checks
59#[derive(Clone, Debug)]
60pub struct PreparedPublicKey<E: Pairing>(pub Vec<E::G2Prepared>);
61
62/// Signature with 2 elements in group G1 and 1 element in G2
63#[serde_as]
64#[derive(
65    Clone,
66    PartialEq,
67    Eq,
68    Debug,
69    CanonicalSerialize,
70    CanonicalDeserialize,
71    Serialize,
72    Deserialize,
73    Zeroize,
74)]
75pub struct Signature<E: Pairing> {
76    #[serde_as(as = "ArkObjectBytes")]
77    pub Z: E::G1Affine,
78    #[serde_as(as = "ArkObjectBytes")]
79    pub Y: E::G1Affine,
80    #[serde_as(as = "ArkObjectBytes")]
81    pub Y_tilde: E::G2Affine,
82}
83
84/// Signature with 2 elements in group G2 and 1 element in G1
85#[serde_as]
86#[derive(
87    Clone,
88    PartialEq,
89    Eq,
90    Debug,
91    CanonicalSerialize,
92    CanonicalDeserialize,
93    Serialize,
94    Deserialize,
95    Zeroize,
96    ZeroizeOnDrop,
97)]
98pub struct SignatureG2<E: Pairing> {
99    #[serde_as(as = "ArkObjectBytes")]
100    pub Z: E::G2Affine,
101    #[serde_as(as = "ArkObjectBytes")]
102    pub Y: E::G2Affine,
103    #[serde_as(as = "ArkObjectBytes")]
104    pub Y_tilde: E::G1Affine,
105}
106
107impl<E: Pairing> SecretKey<E> {
108    pub fn new<R: RngCore>(rng: &mut R, size: u32) -> Result<Self, DelegationError> {
109        if size == 0 {
110            return Err(DelegationError::NeedNonZeroSize);
111        }
112        Ok(Self(
113            (0..size)
114                .map(|_| E::ScalarField::rand(rng))
115                .collect::<Vec<_>>(),
116        ))
117    }
118
119    pub fn generate_using_seed<D>(seed: &[u8], size: u32) -> Result<Self, DelegationError>
120    where
121        D: DynDigest + Default + Clone,
122    {
123        if size == 0 {
124            return Err(DelegationError::NeedNonZeroSize);
125        }
126        let hasher = <DefaultFieldHasher<D> as HashToField<E::ScalarField>>::new(
127            b"MERCURIAL-SIG-KEYGEN-SALT",
128        );
129        Ok(Self(hasher.hash_to_field(seed, size as usize)))
130    }
131
132    /// ConvertSK from the paper.
133    pub fn convert(&self, r: &E::ScalarField) -> Self {
134        Self(cfg_iter!(self.0).map(|s| *s * r).collect::<Vec<_>>())
135    }
136
137    pub fn size(&self) -> usize {
138        self.0.len()
139    }
140}
141
142macro_rules! impl_pubkey {
143    ($gen: ty) => {
144        pub fn new(secret_key: &SecretKey<E>, g2: &$gen) -> Self {
145            let P_tilde_table = WindowTable::new(secret_key.size(), g2.into_group());
146            Self(<$gen as AffineRepr>::Group::normalize_batch(
147                &P_tilde_table.multiply_many(&secret_key.0),
148            ))
149        }
150
151        /// ConvertPK from the paper
152        pub fn convert(&self, rho: &E::ScalarField) -> Self {
153            let r_repr = rho.into_bigint();
154            let new_pk = cfg_iter!(self.0)
155                .map(|s| s.mul_bigint(r_repr))
156                .collect::<Vec<_>>();
157            Self(<$gen as AffineRepr>::Group::normalize_batch(&new_pk))
158        }
159
160        pub fn size(&self) -> usize {
161            self.0.len()
162        }
163    };
164}
165
166impl<E: Pairing> PublicKey<E> {
167    impl_pubkey!(E::G2Affine);
168}
169
170impl<E: Pairing> PublicKeyG1<E> {
171    impl_pubkey!(E::G1Affine);
172}
173
174impl<E: Pairing> From<PublicKey<E>> for PreparedPublicKey<E> {
175    fn from(pk: PublicKey<E>) -> Self {
176        Self(
177            cfg_iter!(pk.0)
178                .map(|e| E::G2Prepared::from(*e))
179                .collect::<Vec<_>>(),
180        )
181    }
182}
183
184impl<E: Pairing> PreparedPublicKey<E> {
185    pub fn size(&self) -> usize {
186        self.0.len()
187    }
188}
189
190macro_rules! impl_signature_struct {
191    ( $msg_group: ty, $pkg: ty ) => {
192        pub fn new<R: RngCore>(
193            rng: &mut R,
194            messages: &[$msg_group],
195            secret_key: &SecretKey<E>,
196            sig_grp_gen: &$msg_group,
197            pk_grp_gen: &$pkg,
198        ) -> Result<Self, DelegationError> {
199            let y = E::ScalarField::rand(rng);
200            Self::new_with_given_randomness(&y, messages, secret_key, sig_grp_gen, pk_grp_gen)
201        }
202
203        pub fn new_with_given_randomness(
204            y: &E::ScalarField,
205            messages: &[$msg_group],
206            secret_key: &SecretKey<E>,
207            sig_grp_gen: &$msg_group,
208            pk_grp_gen: &$pkg,
209        ) -> Result<Self, DelegationError> {
210            if messages.len() > secret_key.size() {
211                return Err(DelegationError::MessageCountIncompatibleWithKey(
212                    messages.len(),
213                    secret_key.size(),
214                ));
215            }
216            // Z = \sum_{i}(m_i * sk_i)*y
217            // Y = sig_grp_gen * 1/y
218            // Y_tilde = pk_grp_gen * 1/y
219            let Z = <$msg_group as AffineRepr>::Group::msm_unchecked(messages, &secret_key.0)
220                .mul_bigint(y.into_bigint())
221                .into_affine();
222            let y_inv = y.inverse().unwrap().into_bigint();
223            Ok(Self {
224                Z,
225                Y: sig_grp_gen.mul_bigint(y_inv).into_affine(),
226                Y_tilde: pk_grp_gen.mul_bigint(y_inv).into_affine(),
227            })
228        }
229
230        /// ConvertSig from the paper
231        pub fn convert<R: RngCore>(&self, rng: &mut R, converter: &E::ScalarField) -> Self {
232            let psi = E::ScalarField::rand(rng);
233            self.convert_with_given_randomness(converter, &psi)
234        }
235
236        /// ChangRep from the paper
237        pub fn change_rep<R: RngCore>(
238            &self,
239            rng: &mut R,
240            message_converter: &E::ScalarField,
241            messages: &[$msg_group],
242        ) -> (Self, Vec<$msg_group>) {
243            let psi = E::ScalarField::rand(rng);
244            self.change_rep_with_given_randomness(message_converter, &psi, messages)
245        }
246
247        /// Similar to `Self::change_rep` but the randomizer for signature's `Z` is passed as an argument
248        /// rather than generated randomly
249        pub fn change_rep_with_given_sig_converter<R: RngCore>(
250            &self,
251            rng: &mut R,
252            message_converter: &E::ScalarField,
253            sig_converter: &E::ScalarField,
254            messages: &[$msg_group],
255        ) -> (Self, Vec<$msg_group>) {
256            let psi = E::ScalarField::rand(rng);
257            self.change_rep_with_given_sig_converter_and_randomness(
258                message_converter,
259                sig_converter,
260                &psi,
261                messages,
262            )
263        }
264
265        /// ConvertSig from the paper with the randomness provided externally
266        pub fn convert_with_given_randomness(
267            &self,
268            converter: &E::ScalarField,
269            psi: &E::ScalarField,
270        ) -> Self {
271            let psi_inv_repr = psi.inverse().unwrap().into_bigint();
272            // Z = Z * converter * psi
273            // Y = Y * 1/psi
274            // Y_tilde = Y_tilde * 1/psi
275            Self {
276                Z: self
277                    .Z
278                    .mul_bigint((*converter * psi).into_bigint())
279                    .into_affine(),
280                Y: self.Y.mul_bigint(psi_inv_repr).into_affine(),
281                Y_tilde: self.Y_tilde.mul_bigint(psi_inv_repr).into_affine(),
282            }
283        }
284
285        /// ChangRep from the paper with the randomness provided externally
286        pub fn change_rep_with_given_randomness(
287            &self,
288            message_converter: &E::ScalarField,
289            psi: &E::ScalarField,
290            messages: &[$msg_group],
291        ) -> (Self, Vec<$msg_group>) {
292            let mu_repr = message_converter.into_bigint();
293            // new_msgs_i = messages_i * message_converter
294            let new_msgs = cfg_iter!(messages)
295                .map(|m| m.mul_bigint(mu_repr))
296                .collect::<Vec<_>>();
297            let new_sig = self.convert_with_given_randomness(message_converter, psi);
298            (
299                new_sig,
300                <$msg_group as AffineRepr>::Group::normalize_batch(&new_msgs),
301            )
302        }
303
304        pub fn change_rep_with_given_sig_converter_and_randomness(
305            &self,
306            message_converter: &E::ScalarField,
307            sig_converter: &E::ScalarField,
308            psi: &E::ScalarField,
309            messages: &[$msg_group],
310        ) -> (Self, Vec<$msg_group>) {
311            let mu_repr = message_converter.into_bigint();
312            let new_msgs = cfg_iter!(messages)
313                .map(|m| m.mul_bigint(mu_repr))
314                .collect::<Vec<_>>();
315            let new_sig =
316                self.convert_with_given_randomness(&(*message_converter * *sig_converter), psi);
317            (
318                new_sig,
319                <$msg_group as AffineRepr>::Group::normalize_batch(&new_msgs),
320            )
321        }
322    };
323}
324
325impl<E: Pairing> Signature<E> {
326    impl_signature_struct!(E::G1Affine, E::G2Affine);
327
328    pub fn verify(
329        &self,
330        messages: &[E::G1Affine],
331        public_key: impl Into<PreparedPublicKey<E>>,
332        sig_grp_gen: &E::G1Affine,
333        pk_grp_gen: impl Into<E::G2Prepared>,
334    ) -> Result<(), DelegationError> {
335        let public_key = public_key.into();
336
337        if messages.len() > public_key.size() {
338            return Err(DelegationError::MessageCountIncompatibleWithKey(
339                messages.len(),
340                public_key.size(),
341            ));
342        }
343
344        let y_tilde_prep = E::G2Prepared::from(self.Y_tilde);
345
346        let mut a = cfg_iter!(messages)
347            .map(|e| E::G1Prepared::from(*e))
348            .collect::<Vec<_>>();
349        let mut b = public_key.0[..messages.len()].to_vec();
350        a.push(E::G1Prepared::from(-self.Z.into_group()));
351        b.push(y_tilde_prep.clone());
352        if !E::multi_pairing(a, b).is_zero() {
353            return Err(DelegationError::InvalidSignature);
354        }
355
356        if !E::multi_pairing(
357            [
358                E::G1Prepared::from(self.Y),
359                E::G1Prepared::from(-sig_grp_gen.into_group()),
360            ],
361            [pk_grp_gen.into(), y_tilde_prep],
362        )
363        .is_zero()
364        {
365            return Err(DelegationError::InvalidSignature);
366        }
367        Ok(())
368    }
369}
370
371impl<E: Pairing> SignatureG2<E> {
372    impl_signature_struct!(E::G2Affine, E::G1Affine);
373
374    pub fn verify(
375        &self,
376        messages: &[E::G2Affine],
377        public_key: &PublicKeyG1<E>,
378        sig_grp_gen: impl Into<E::G2Prepared>,
379        pk_grp_gen: &E::G1Affine,
380    ) -> Result<(), DelegationError> {
381        if messages.len() > public_key.size() {
382            return Err(DelegationError::MessageCountIncompatibleWithKey(
383                messages.len(),
384                public_key.size(),
385            ));
386        }
387
388        let mut a = cfg_iter!(public_key.0)
389            .map(|e| E::G1Prepared::from(*e))
390            .collect::<Vec<_>>();
391        let mut b = cfg_iter!(messages)
392            .map(|e| E::G2Prepared::from(*e))
393            .collect::<Vec<_>>();
394        a.push(E::G1Prepared::from(
395            (-self.Y_tilde.into_group()).into_affine(),
396        ));
397        b.push(E::G2Prepared::from(self.Z));
398        if !E::multi_pairing(a, b).is_zero() {
399            return Err(DelegationError::InvalidSignature);
400        }
401
402        if !E::multi_pairing(
403            [
404                E::G1Prepared::from(*pk_grp_gen),
405                E::G1Prepared::from((-self.Y_tilde.into_group()).into_affine()),
406            ],
407            [E::G2Prepared::from(self.Y), sig_grp_gen.into()],
408        )
409        .is_zero()
410        {
411            return Err(DelegationError::InvalidSignature);
412        }
413        Ok(())
414    }
415}
416
417#[cfg(test)]
418mod tests {
419    use super::*;
420    use crate::util::generator_pair;
421    use ark_bls12_381::Bls12_381;
422    use ark_std::rand::{rngs::StdRng, SeedableRng};
423
424    type Fr = <Bls12_381 as Pairing>::ScalarField;
425    type G2Prepared = <Bls12_381 as Pairing>::G2Prepared;
426
427    #[test]
428    fn sign_verify() {
429        let mut rng = StdRng::seed_from_u64(0u64);
430
431        let (P1, P2) = generator_pair::<Bls12_381, StdRng>(&mut rng);
432        let prep_P2 = G2Prepared::from(P2);
433
434        let count = 5;
435        let sk = SecretKey::new(&mut rng, count).unwrap();
436        let pk = PublicKey::<Bls12_381>::new(&sk, &P2);
437        let prep_pk = PreparedPublicKey::from(pk.clone());
438        assert!(
439            count as usize == sk.size() && sk.size() == pk.size() && pk.size() == prep_pk.size()
440        );
441
442        let msgs = (0..count)
443            .map(|_| <Bls12_381 as Pairing>::G1Affine::rand(&mut rng))
444            .collect::<Vec<_>>();
445
446        let sig = Signature::new(&mut rng, &msgs, &sk, &P1, &P2).unwrap();
447        sig.verify(&msgs, prep_pk.clone(), &P1, prep_P2.clone())
448            .unwrap();
449
450        let r1 = Fr::rand(&mut rng);
451        let pk1 = pk.convert(&r1);
452        let prep_pk1 = PreparedPublicKey::from(pk1.clone());
453        assert_eq!(pk1.size(), prep_pk1.size());
454
455        // Original messages with converted signature and public key
456        let sig1 = sig.convert(&mut rng, &r1);
457        sig1.verify(&msgs, prep_pk1.clone(), &P1, prep_P2.clone())
458            .unwrap();
459
460        // Converted messages and signature with original public key
461        let r2 = Fr::rand(&mut rng);
462        let (sig2, msgs1) = sig.change_rep(&mut rng, &r2, &msgs);
463        sig2.verify(&msgs1, prep_pk, &P1, prep_P2.clone()).unwrap();
464
465        let (sig3, msgs2) = sig1.change_rep(&mut rng, &r2, &msgs);
466        sig3.verify(&msgs2, prep_pk1.clone(), &P1, prep_P2.clone())
467            .unwrap();
468
469        // Messages, signature and public key, all converted
470        let (sig4, msgs3) = sig.change_rep_with_given_sig_converter(&mut rng, &r2, &r1, &msgs);
471        sig4.verify(&msgs3, prep_pk1, &P1, prep_P2.clone()).unwrap();
472
473        // Switch group for messages and public key
474
475        let pk = PublicKeyG1::<Bls12_381>::new(&sk, &P1);
476        let msgs = (0..count)
477            .map(|_| <Bls12_381 as Pairing>::G2Affine::rand(&mut rng))
478            .collect::<Vec<_>>();
479
480        let sig = SignatureG2::new(&mut rng, &msgs, &sk, &P2, &P1).unwrap();
481        sig.verify(&msgs, &pk, prep_P2.clone(), &P1).unwrap();
482
483        // Converted messages and signature with original public key
484        let (sig2, msgs1) = sig.change_rep(&mut rng, &r2, &msgs);
485        sig2.verify(&msgs1, &pk, prep_P2, &P1).unwrap();
486    }
487}
delegatable_credentials/mercurial_sig.rs

delegatable_credentials/
mercurial_sig.rs
