kyber_rs/sign/dss/
dss_sig.rs

1use core::fmt::{Debug, Display, Formatter};
2/// module dss implements the Distributed Schnorr Signature protocol from the
3/// paper "Provably Secure Distributed Schnorr Signatures and a (t, n)
4/// Threshold Scheme for Implicit Certificates".
5/// https://dl.acm.org/citation.cfm?id=678297
6/// To generate a distributed signature from a group of participants, the group
7/// must first generate one longterm distributed secret with the dkg module
8/// and then one random secret to be used only once.
9/// Each participant then creates a DSS struct, that can issue partial signatures
10/// with `partial_sig()`. These partial signatures can be broadcasted to
11/// the whole group or to a trusted combiner. Once one has collected enough
12/// partial signatures, it is possible to compute the distributed signature with
13/// the `signature` method.
14/// The resulting signature is compatible with the EdDSA verification function.
15/// against the longterm distributed key.
16use digest::Digest;
17use serde::{Deserialize, Serialize};
18use sha2::Sha512;
19use std::collections::HashMap;
20
21use crate::{
22    encoding::Marshaling,
23    group::{HashFactory, PointCanCheckCanonicalAndSmallOrder, ScalarCanCheckCanonical},
24    share::poly::{self, PolyError, PriShare, PubPoly},
25    sign::{eddsa, error::SignatureError, schnorr},
26    Group, Point, Random, Scalar,
27};
28
29use thiserror::Error;
30
31/// [`Suite`] represents the functionalities needed by the dss module
32pub trait Suite: Group + HashFactory + Random + Clone {}
33
34/// [`DistKeyShare`] is an abstraction to allow one to use distributed key share
35/// from different schemes easily into this distributed threshold Schnorr
36/// signature framework.
37pub trait DistKeyShare<GROUP: Group>: Clone {
38    fn pri_share(&self) -> PriShare<<GROUP::POINT as Point>::SCALAR>;
39    fn commitments(&self) -> Vec<GROUP::POINT>;
40}
41
42/// [`DSS`] holds the information used to issue partial signatures as well as to
43/// compute the distributed schnorr signature.
44#[derive(Clone, Default, PartialEq, Eq, Serialize, Deserialize)]
45pub struct DSS<SUITE: Suite, DKS: DistKeyShare<SUITE>> {
46    suite: SUITE,
47    pub(crate) secret: <SUITE::POINT as Point>::SCALAR,
48    pub public: SUITE::POINT,
49    pub index: usize,
50    pub participants: Vec<SUITE::POINT>,
51    pub t: usize,
52    long: DKS,
53    random: DKS,
54    long_poly: PubPoly<SUITE>,
55    random_poly: PubPoly<SUITE>,
56    pub msg: Vec<u8>,
57    pub partials: Vec<Option<PriShare<<SUITE::POINT as Point>::SCALAR>>>,
58    partials_idx: HashMap<usize, bool>,
59    signed: bool,
60    pub session_id: Vec<u8>,
61}
62
63impl<SUITE: Suite, DKS: DistKeyShare<SUITE> + Debug> Debug for DSS<SUITE, DKS> {
64    fn fmt(&self, f: &mut Formatter<'_>) -> core::fmt::Result {
65        f.debug_struct("DSS")
66            .field("suite", &self.suite)
67            .field("public", &self.public)
68            .field("index", &self.index)
69            .field("participants", &self.participants)
70            .field("t", &self.t)
71            .field("long_poly", &self.long_poly)
72            .field("random_poly", &self.random_poly)
73            .field("msg", &self.msg)
74            .field("partials", &self.partials)
75            .field("partials_idx", &self.partials_idx)
76            .field("signed", &self.signed)
77            .field("session_id", &self.session_id)
78            .finish()
79    }
80}
81
82impl<SUITE: Suite, DKS: DistKeyShare<SUITE> + Display> Display for DSS<SUITE, DKS> {
83    fn fmt(&self, f: &mut Formatter<'_>) -> core::fmt::Result {
84        write!(
85            f,
86            "DSS( suite: {}, public_key: {}, index: {},",
87            self.suite, self.public, self.index
88        )?;
89
90        write!(f, " participants: [")?;
91        let participants = self
92            .participants
93            .iter()
94            .map(|c| c.to_string())
95            .collect::<Vec<_>>()
96            .join(",");
97        write!(f, "{}],", participants)?;
98
99        write!(
100            f,
101            "threshold: {}, long_polynomial: {}, random_polynomial: {}, message: 0x{},",
102            self.t,
103            self.long_poly,
104            self.random_poly,
105            hex::encode(&self.msg)
106        )?;
107
108        write!(f, " partials: [")?;
109        let partials = self
110            .partials
111            .iter()
112            .map(|c| match c {
113                Some(p) => "Some(".to_string() + &p.to_string() + ")",
114                None => "None".to_string(),
115            })
116            .collect::<Vec<_>>()
117            .join(",");
118        write!(f, "{}],", partials)?;
119
120        write!(f, " partials_indexes: [")?;
121        let partials_indexes = self
122            .partials_idx
123            .iter()
124            .map(|c| "(".to_string() + &c.0.to_string() + ", " + &c.1.to_string() + ")")
125            .collect::<Vec<_>>()
126            .join(", ");
127        write!(f, "{}],", partials_indexes)?;
128
129        write!(
130            f,
131            "signed: {}, session_id: 0x{} )",
132            self.signed,
133            hex::encode(&self.session_id)
134        )
135    }
136}
137
138/// [`PartialSig`] is partial representation of the final distributed signature. It
139/// must be sent to each of the other participants.
140#[derive(Clone, Serialize, Deserialize, Debug, Default)]
141pub struct PartialSig<SUITE: Suite> {
142    pub partial: PriShare<<SUITE::POINT as Point>::SCALAR>,
143    pub session_id: Vec<u8>,
144    pub signature: Vec<u8>,
145}
146
147impl<SUITE: Suite> PartialSig<SUITE> {
148    /// [`hash()`] returns the hash representation of this [`PartialSig`] to be used in a
149    /// signature.
150    pub fn hash(&self, s: SUITE) -> Result<Vec<u8>, DSSError> {
151        let mut h = s.hash();
152        h.update(
153            &self
154                .partial
155                .hash(s)
156                .map_err(DSSError::PartialSignatureHash)?,
157        );
158        h.update(&self.session_id);
159        Ok(h.finalize().to_vec())
160    }
161}
162
163/// [`new_dss`] returns a [`DSS`] struct out of the [`Suite`], the `longterm secret` of this
164/// node, the `list of participants`, the `longterm` and `random` distributed key
165/// (generated by the dkg module), the `message` to sign and finally the `T
166/// threshold`. It returns an [`Error`](DSSError) if the public key of the secret can't be found
167/// in the list of participants.
168pub fn new_dss<SUITE: Suite, DKS: DistKeyShare<SUITE>>(
169    suite: SUITE,
170    secret: &<SUITE::POINT as Point>::SCALAR,
171    participants: &[SUITE::POINT],
172    long: &DKS,
173    random: &DKS,
174    msg: &[u8],
175    t: usize,
176) -> Result<DSS<SUITE, DKS>, DSSError> {
177    let public = suite.point().mul(secret, None);
178    let mut i = 0;
179    let mut found = false;
180    for (j, p) in participants.iter().enumerate() {
181        if p.eq(&public) {
182            found = true;
183            i = j;
184            break;
185        }
186    }
187    if !found {
188        return Err(DSSError::PublicKeyNotInParticipants);
189    }
190
191    Ok(DSS::<SUITE, DKS> {
192        suite: suite.clone(),
193        secret: secret.clone(),
194        public,
195        index: i,
196        participants: participants.to_vec(),
197        long: long.clone(),
198        long_poly: PubPoly::new(&suite, Some(suite.point().base()), &long.commitments()),
199        random: random.clone(),
200        random_poly: PubPoly::new(&suite, Some(suite.point().base()), &random.commitments()),
201        msg: msg.to_vec(),
202        t,
203        partials_idx: HashMap::new(),
204        session_id: session_id(suite, long, random)?,
205        partials: Vec::new(),
206        signed: false,
207    })
208}
209
210impl<SUITE: Suite, DKS: DistKeyShare<SUITE>> DSS<SUITE, DKS> {
211    /// [`partial_sig()`] generates the partial signature related to this [`DSS`]. This
212    /// [`PartialSig`] can be broadcasted to every other participant or only to a
213    /// trusted combiner as described in the paper.
214    /// The signature format is compatible with EdDSA verification implementations.
215    pub fn partial_sig(&mut self) -> Result<PartialSig<SUITE>, DSSError> {
216        // following the notations from the paper
217        let alpha = self.long.pri_share().v;
218        let beta = self.random.pri_share().v;
219        let hash = self.hash_sig()?;
220        let right = hash * alpha;
221        let mut ps = PartialSig {
222            partial: PriShare {
223                v: right + beta,
224                i: self.index,
225            },
226            session_id: self.session_id.clone(),
227            signature: Vec::new(),
228        };
229        let msg = ps.hash(self.suite.clone())?;
230        ps.signature = schnorr::sign(&self.suite, &self.secret, &msg)?;
231        if !self.signed {
232            self.partials_idx.insert(self.index, true);
233            self.partials.push(Some(ps.partial.clone()));
234            self.signed = true
235        }
236        Ok(ps)
237    }
238
239    /// [`process_partial_sig()`] takes a [`PartialSig`] from another participant and stores it
240    /// for generating the distributed signature. It returns an [`Error`](DSSError) if the index is
241    /// wrong, or the signature is invalid or if a partial signature has already been
242    /// received by the same peer. To know whether the distributed signature can be
243    /// computed after this call, one can use the [`enough_partial_sig()`] method.
244    pub fn process_partial_sig(&mut self, ps: PartialSig<SUITE>) -> Result<(), DSSError>
245    where
246        <SUITE::POINT as Point>::SCALAR: ScalarCanCheckCanonical,
247        SUITE::POINT: PointCanCheckCanonicalAndSmallOrder,
248    {
249        let public = find_pub(&self.participants, ps.partial.i)?;
250
251        let msg = ps.hash(self.suite.clone())?;
252        schnorr::verify(self.suite.clone(), &public, &msg, &ps.signature)?;
253
254        // nothing secret here
255        if ps.session_id != self.session_id {
256            return Err(DSSError::InvalidSessionId);
257        }
258
259        if self.partials_idx.contains_key(&ps.partial.i) {
260            return Err(DSSError::PartialAlreadyReceived);
261        }
262
263        let hash = self.hash_sig()?;
264        let idx = ps.partial.i;
265        let rand_share = self.random_poly.eval(idx);
266        let long_share = self.long_poly.eval(idx);
267        let mut right = self.suite.point().mul(&hash, Some(&long_share.v));
268        let right_clone = right.clone();
269        right = right.add(&rand_share.v, &right_clone);
270        let left = self.suite.point().mul(&ps.partial.v, None);
271        if !left.eq(&right) {
272            return Err(DSSError::InvalidPartialSignature);
273        }
274        self.partials_idx.insert(ps.partial.i, true);
275        self.partials.push(Some(ps.partial));
276        Ok(())
277    }
278
279    /// [`enough_partial_sig()`] returns `true` if there are enough partial signature to compute
280    /// the distributed signature. It returns `false` otherwise. If there are enough
281    /// partial signatures, one can issue the signature with [`signature()`].
282    pub fn enough_partial_sig(&self) -> bool {
283        self.partials.len() >= self.t
284    }
285
286    /// [`signature()`] computes the distributed signature from the `list of partial
287    /// signatures` received. It returns an [`Error`](DSSError) if there are not enough partial
288    /// signatures. The signature is compatible with the EdDSA verification
289    /// alrogithm.
290    pub fn signature(&self) -> Result<Vec<u8>, DSSError> {
291        if !self.enough_partial_sig() {
292            return Err(DSSError::NotEnoughPartials);
293        }
294        let gamma = poly::recover_secret(
295            self.suite.clone(),
296            &self.partials,
297            self.t,
298            self.participants.len(),
299        )
300        .map_err(DSSError::RecoverSecretError)?;
301        // RandomPublic || gamma
302        let mut buff = Vec::new();
303        self.random.commitments()[0]
304            .marshal_to(&mut buff)
305            .map_err(SignatureError::MarshallingError)?;
306        gamma
307            .marshal_to(&mut buff)
308            .map_err(SignatureError::MarshallingError)?;
309        Ok(buff)
310    }
311
312    fn hash_sig(&self) -> Result<<SUITE::POINT as Point>::SCALAR, DSSError> {
313        // H(R || A || msg) with
314        //  * R = distributed random "key"
315        //  * A = distributed public key
316        //  * msg = msg to sign
317        let mut h = Sha512::new();
318        self.random.commitments()[0]
319            .marshal_to(&mut h)
320            .map_err(SignatureError::MarshallingError)?;
321        self.long.commitments()[0]
322            .marshal_to(&mut h)
323            .map_err(SignatureError::MarshallingError)?;
324        h.update(self.msg.clone());
325        Ok(self.suite.scalar().set_bytes(&h.finalize()))
326    }
327}
328
329/// [`verify()`] takes a `public key`, a `message` and a `signature` and returns an [`Error`](SignatureError) if
330/// the signature is invalid.
331pub fn verify<POINT: Point>(public: &POINT, msg: &[u8], sig: &[u8]) -> Result<(), SignatureError> {
332    eddsa::verify(public, msg, sig)
333}
334
335fn find_pub<POINT: Point>(list: &[POINT], i: usize) -> Result<POINT, DSSError> {
336    if i >= list.len() {
337        return Err(DSSError::InvalidIndex);
338    }
339    Ok(list[i].clone())
340}
341
342fn session_id<SUITE: Suite, DKS: DistKeyShare<SUITE>>(
343    s: SUITE,
344    a: &DKS,
345    b: &DKS,
346) -> Result<Vec<u8>, DSSError> {
347    let mut h = s.hash();
348    for p in a.commitments() {
349        p.marshal_to(&mut h)
350            .map_err(SignatureError::MarshallingError)?;
351    }
352
353    for p in b.commitments() {
354        p.marshal_to(&mut h)
355            .map_err(SignatureError::MarshallingError)?;
356    }
357
358    Ok(h.finalize().to_vec())
359}
360
361#[derive(Error, Debug)]
362pub enum DSSError {
363    #[error("signature error")]
364    SignatureError(#[from] SignatureError),
365    #[error("public key not found in the list of participants")]
366    PublicKeyNotInParticipants,
367    #[error("invalid index")]
368    InvalidIndex,
369    #[error("not enough partial signature to sign")]
370    NotEnoughPartials,
371    #[error("could not recover secret")]
372    RecoverSecretError(PolyError),
373    #[error("could not hash partial signature")]
374    PartialSignatureHash(PolyError),
375    #[error("session id do not match")]
376    InvalidSessionId,
377    #[error("partial signature already received from peer")]
378    PartialAlreadyReceived,
379    #[error("partial signature not valid")]
380    InvalidPartialSignature,
381}
kyber_rs/sign/dss/dss_sig.rs

kyber_rs/sign/dss/
dss_sig.rs
