primitives/sharing/
mod.rs

1// Secret sharing schemes.
2pub mod authenticated;
3pub mod unauthenticated;
4
5use std::{borrow::Borrow, sync::Arc};
6
7pub use authenticated::*;
8use itertools::{enumerate, izip};
9use serde::{de::DeserializeOwned, Serialize};
10
11use crate::{
12    algebra::{field::FieldExtension, ops::transpose::transpose},
13    errors::{PrimitiveError, VerificationError},
14    random::{CryptoRngCore, RandomWith},
15    types::PeerIndex,
16    utils::TakeExact,
17};
18
19// ------------------------- //
20// ---- Reconstructible ---- //
21// ------------------------- //
22/// Reconstructs a secret from a collection of openings and a local share.
23pub trait Reconstructible: Sized {
24    /// The type that is sent to / received from other peers.
25    type Opening: Serialize + DeserializeOwned + Clone + Send + Sync + 'static;
26    /// The type of the reconstructed value.
27    type Secret: Serialize + DeserializeOwned + Clone + PartialEq + Send + Sync + 'static;
28
29    /// Open the share towards another peer.
30    fn open_to(&self, peer_index: PeerIndex) -> Result<Self::Opening, PrimitiveError>;
31
32    /// Open the share towards all other peers. Returns an iterator with either one opening for
33    /// each peer or a single opening for all peers.
34    fn open_to_all_others(&self) -> impl ExactSizeIterator<Item = Self::Opening>;
35
36    /// Reconstruct a secret from openings coming from all other parties.
37    fn reconstruct(&self, openings: &[Self::Opening]) -> Result<Self::Secret, PrimitiveError>;
38
39    /// Reconstruct a secret from a collection of shares, by opening each share
40    /// towards all other peers, reconstructing `n` secrets from the openings and
41    /// checking that they are all equal.
42    fn reconstruct_all<T: Borrow<Self>>(shares: &[T]) -> Result<Self::Secret, PrimitiveError> {
43        let n_parties = shares.len();
44        if n_parties < 2 {
45            return Err(PrimitiveError::InvalidParameters(
46                "At least two shares are required for reconstruction.".to_string(),
47            ));
48        }
49        // Open each share to all other peers.
50        let mut all_openings = shares
51            .iter()
52            .map(|share| share.borrow().open_to_all_others())
53            .collect::<Vec<_>>();
54        // Reconstruct each secret.
55        enumerate(shares.iter())
56            .map(|(i, share)| {
57                let my_openings = enumerate(all_openings.iter_mut())
58                    .take_exact(n_parties)
59                    .filter(|(j, _)| i != *j)
60                    .map(|(_, opening)| opening.next())
61                    .collect::<Option<Vec<_>>>()
62                    .ok_or(PrimitiveError::WrongPeerIndex(i, shares.len() - 1))?;
63                share.borrow().reconstruct(my_openings.as_slice())
64            })
65            // Check that all reconstructed secrets are equal.
66            .reduce(|previous, current| match (previous, current) {
67                (Ok(prev), Ok(curr)) => match prev == curr {
68                    true => Ok(prev),
69                    false => Err(VerificationError::OpeningMismatch(
70                        serde_json::to_string(&prev).unwrap(),
71                        serde_json::to_string(&curr).unwrap(),
72                    )
73                    .into()),
74                },
75                (Err(e), _) | (_, Err(e)) => Err(e),
76            })
77            .unwrap() // Safe because `shares.len() >= 2`
78    }
79}
80
81impl<T: Reconstructible<Opening: Clone>> Reconstructible for Vec<T> {
82    type Opening = Vec<T::Opening>;
83    type Secret = Vec<T::Secret>;
84
85    fn open_to(&self, peer_index: PeerIndex) -> Result<Self::Opening, PrimitiveError> {
86        self.iter().map(|share| share.open_to(peer_index)).collect()
87    }
88
89    fn open_to_all_others(&self) -> impl ExactSizeIterator<Item = Self::Opening> {
90        let all_openings: Vec<Vec<_>> = self
91            .iter()
92            .map(|share| share.open_to_all_others().collect())
93            .collect();
94
95        transpose(all_openings).into_iter()
96    }
97
98    fn reconstruct(&self, openings: &[Self::Opening]) -> Result<Self::Secret, PrimitiveError> {
99        if openings.is_empty() {
100            return Err(PrimitiveError::InvalidParameters(
101                "At least one opening is required for reconstruction.".to_string(),
102            ));
103        }
104
105        if openings[0].len() != self.len() {
106            return Err(PrimitiveError::InvalidParameters(
107                "Number of openings must match number of shares.".to_string(),
108            ));
109        }
110
111        // Iterate over all the i-th elements of each entry of openings
112        let mut reconstructed = Vec::with_capacity(self.len());
113        for (i, share) in self.iter().enumerate() {
114            let my_openings: Vec<_> = openings
115                .iter()
116                .map(|opening| opening.get(i).cloned())
117                .collect::<Option<Vec<_>>>()
118                .ok_or(PrimitiveError::InvalidParameters(
119                    "Opening is missing for some share.".to_string(),
120                ))?;
121            reconstructed.push(share.reconstruct(my_openings.as_slice())?);
122        }
123        Ok(reconstructed)
124    }
125}
126
127impl<T: Reconstructible<Opening: Clone>> Reconstructible for Arc<[T]> {
128    type Opening = Arc<[T::Opening]>;
129    type Secret = Arc<[T::Secret]>;
130
131    fn open_to(&self, peer_index: PeerIndex) -> Result<Self::Opening, PrimitiveError> {
132        self.iter().map(|share| share.open_to(peer_index)).collect()
133    }
134
135    fn open_to_all_others(&self) -> impl ExactSizeIterator<Item = Self::Opening> {
136        let all_openings: Vec<Vec<_>> = self
137            .iter()
138            .map(|share| share.open_to_all_others().collect())
139            .collect();
140
141        transpose(all_openings)
142            .into_iter()
143            .map(Arc::from)
144            .collect::<Vec<_>>()
145            .into_iter()
146    }
147
148    fn reconstruct(&self, openings: &[Self::Opening]) -> Result<Self::Secret, PrimitiveError> {
149        if openings.is_empty() {
150            return Err(PrimitiveError::InvalidParameters(
151                "At least one opening is required for reconstruction.".to_string(),
152            ));
153        }
154
155        if openings[0].len() != self.len() {
156            return Err(PrimitiveError::InvalidParameters(
157                "Number of openings must match number of shares.".to_string(),
158            ));
159        }
160
161        // Iterate over all the i-th elements of each entry of openings
162        let mut reconstructed = Vec::with_capacity(self.len());
163        for (i, share) in self.iter().enumerate() {
164            let my_openings: Vec<_> = openings
165                .iter()
166                .map(|opening| opening.get(i).cloned())
167                .collect::<Option<Vec<_>>>()
168                .ok_or(PrimitiveError::InvalidParameters(
169                    "Opening is missing for some share.".to_string(),
170                ))?;
171            reconstructed.push(share.reconstruct(my_openings.as_slice())?);
172        }
173
174        Ok(reconstructed.into())
175    }
176}
177
178impl<T: Reconstructible, S: Reconstructible> Reconstructible for (T, S) {
179    type Opening = (T::Opening, S::Opening);
180    type Secret = (T::Secret, S::Secret);
181
182    fn open_to(&self, peer_index: PeerIndex) -> Result<Self::Opening, PrimitiveError> {
183        Ok((self.0.open_to(peer_index)?, self.1.open_to(peer_index)?))
184    }
185
186    fn open_to_all_others(&self) -> impl ExactSizeIterator<Item = Self::Opening> {
187        let all_openings_t: Vec<_> = self.0.open_to_all_others().collect();
188        let all_openings_s: Vec<_> = self.1.open_to_all_others().collect();
189        izip!(all_openings_t, all_openings_s).map(|(o1, o2)| (o1, o2))
190    }
191
192    fn reconstruct(&self, openings: &[Self::Opening]) -> Result<Self::Secret, PrimitiveError> {
193        let (openings_t, openings_s): (Vec<_>, Vec<_>) = openings.iter().cloned().unzip();
194        Ok((
195            self.0.reconstruct(&openings_t)?,
196            self.1.reconstruct(&openings_s)?,
197        ))
198    }
199}
200
201// ---------------------------- //
202// ---- Random for N Peers ---- //
203// ---------------------------- //
204pub trait RandomAuthenticatedForNPeers<F: FieldExtension>:
205    RandomWith<Vec<Vec<GlobalFieldKey<F>>>>
206{
207    fn random_for_n_peers_with_alphas<Container: FromIterator<Self>>(
208        mut rng: impl CryptoRngCore,
209        n_parties: usize,
210        all_alphas: Vec<Vec<GlobalFieldKey<F>>>,
211    ) -> Container {
212        Self::random_n_with(&mut rng, n_parties, all_alphas)
213    }
214}
215
216impl<F: FieldExtension, S: RandomWith<Vec<Vec<GlobalFieldKey<F>>>>> RandomAuthenticatedForNPeers<F>
217    for S
218{
219}
220
221pub trait RandomAuthenticatedForNPeersWith<F: FieldExtension, T: Clone>:
222    RandomWith<(T, Vec<Vec<GlobalFieldKey<F>>>)>
223{
224    fn random_authenticated_for_n_peers_with<Container: FromIterator<Self>>(
225        mut rng: impl CryptoRngCore,
226        n_parties: usize,
227        value: T,
228        all_alphas: Vec<Vec<GlobalFieldKey<F>>>,
229    ) -> Container {
230        Self::random_n_with(&mut rng, n_parties, (value, all_alphas))
231    }
232}
233
234impl<F: FieldExtension, T: Clone, S: RandomWith<(T, Vec<Vec<GlobalFieldKey<F>>>)>>
235    RandomAuthenticatedForNPeersWith<F, T> for S
236{
237}
238
239/// A trait used to add a plaintext secret to its secret-shared (reconstructible) form.
240pub trait AddPlaintext: Reconstructible {
241    /// Helper information to be used when adding a constant to the share. For example in BDOZ
242    /// shares, you need to know whether the local peer is the first peer or not.
243    type AssociatedInformation: Clone + Send + Sync;
244    /// Add a constant to the share.
245    fn add_plaintext(&self, plaintext: &Self::Secret, assoc: Self::AssociatedInformation) -> Self;
246
247    /// Add a constant to the share, consuming the share and returning a new one.
248    fn add_plaintext_owned(
249        self,
250        plaintext: &Self::Secret,
251        assoc: Self::AssociatedInformation,
252    ) -> Self {
253        self.add_plaintext(plaintext, assoc)
254    }
255}
256
257#[cfg(test)]
258mod tests {
259    use super::*;
260    use crate::{
261        algebra::elliptic_curve::Curve25519Ristretto,
262        random::Random,
263        sharing::ScalarShares,
264    };
265
266    #[test]
267    fn test_transpose_empty_matrix() {
268        let matrix: Vec<Vec<i32>> = vec![];
269        let result = transpose(matrix.clone());
270        assert_eq!(result, matrix);
271    }
272
273    #[test]
274    fn test_transpose_empty_rows() {
275        let matrix: Vec<Vec<i32>> = vec![];
276        let result = transpose(matrix.clone());
277        assert_eq!(result, matrix);
278    }
279
280    #[test]
281    fn test_transpose_single_element() {
282        let matrix = vec![vec![1]];
283        let result = transpose(matrix);
284        assert_eq!(result, vec![vec![1]]);
285    }
286
287    #[test]
288    fn test_transpose_single_row() {
289        let matrix = vec![vec![1, 2, 3]];
290        let result = transpose(matrix);
291        assert_eq!(result, vec![vec![1], vec![2], vec![3]]);
292    }
293
294    #[test]
295    fn test_transpose_single_column() {
296        let matrix = vec![vec![1], vec![2], vec![3]];
297        let result = transpose(matrix);
298        assert_eq!(result, vec![vec![1, 2, 3]]);
299    }
300
301    #[test]
302    fn test_transpose_square_matrix() {
303        let matrix = vec![vec![1, 2, 3], vec![4, 5, 6], vec![7, 8, 9]];
304        let result = transpose(matrix);
305        let expected = vec![vec![1, 4, 7], vec![2, 5, 8], vec![3, 6, 9]];
306        assert_eq!(result, expected);
307    }
308
309    #[test]
310    fn test_transpose_rectangular_matrix() {
311        let matrix = vec![vec![1, 2, 3, 4], vec![5, 6, 7, 8]];
312        let result = transpose(matrix);
313        let expected = vec![vec![1, 5], vec![2, 6], vec![3, 7], vec![4, 8]];
314        assert_eq!(result, expected);
315    }
316
317    #[test]
318    fn test_transpose_with_strings() {
319        let matrix = vec![vec!["a", "b"], vec!["c", "d"], vec!["e", "f"]];
320        let result = transpose(matrix);
321        let expected = vec![vec!["a", "c", "e"], vec!["b", "d", "f"]];
322        assert_eq!(result, expected);
323    }
324
325    #[test]
326    fn test_transpose_double_transpose() {
327        let matrix = vec![vec![1, 2, 3], vec![4, 5, 6]];
328        let result = transpose(transpose(matrix.clone()));
329        assert_eq!(result, matrix);
330    }
331
332    #[test]
333    fn test_reconstruct_vec() {
334        let n_parties = 3;
335        let mut rng = crate::random::test_rng();
336
337        let scalar_shares: Vec<_> =
338            ScalarShares::<Curve25519Ristretto, typenum::U5>::random_n(&mut rng, n_parties);
339        let scalar_shares = scalar_shares
340            .into_iter()
341            .map(|s| s.into_iter().collect::<Vec<_>>())
342            .collect::<Vec<_>>();
343
344        let reconstructed =
345            Vec::<ScalarShare<Curve25519Ristretto>>::reconstruct_all(&scalar_shares).unwrap();
346        let expected = (0..5)
347            .map(|i| {
348                ScalarShare::<Curve25519Ristretto>::reconstruct_all(
349                    &scalar_shares.iter().map(|v| &v[i]).collect::<Vec<_>>(),
350                )
351                .unwrap()
352            })
353            .collect::<Vec<_>>();
354        assert_eq!(reconstructed, expected);
355    }
356
357    #[test]
358    fn test_reconstruct_tuple() {
359        let n_parties = 3;
360        let mut rng = crate::random::test_rng();
361
362        let scalar_shares: Vec<_> =
363            ScalarShare::<Curve25519Ristretto>::random_n(&mut rng, n_parties);
364        let base_field_shares: Vec<_> =
365            BaseFieldShare::<Curve25519Ristretto>::random_n(&mut rng, n_parties);
366
367        let shares: Vec<(
368            ScalarShare<Curve25519Ristretto>,
369            BaseFieldShare<Curve25519Ristretto>,
370        )> = izip!(&scalar_shares, &base_field_shares)
371            .map(|(s, b)| (s.clone(), b.clone()))
372            .collect();
373
374        let reconstructed = <(
375            ScalarShare<Curve25519Ristretto>,
376            BaseFieldShare<Curve25519Ristretto>,
377        )>::reconstruct_all(&shares)
378        .unwrap();
379
380        assert_eq!(
381            reconstructed.0,
382            ScalarShare::<Curve25519Ristretto>::reconstruct_all(&scalar_shares).unwrap()
383        );
384        assert_eq!(
385            reconstructed.1,
386            BaseFieldShare::<Curve25519Ristretto>::reconstruct_all(&base_field_shares).unwrap()
387        );
388    }
389}
primitives/sharing/mod.rs

primitives/sharing/
mod.rs
