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

primitives/sharing/
mod.rs
