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};
10pub use unauthenticated::*;
11use wincode::{SchemaRead, SchemaWrite};
12
13use crate::{
14    algebra::ops::transpose::transpose,
15    errors::PrimitiveError,
16    types::PeerIndex,
17    utils::TakeExact,
18};
19
20// ------------------------- //
21// ---- Reconstructible ---- //
22// ------------------------- //
23/// Reconstructs a secret-shared value from a collection of openings and a local share.
24pub trait Reconstructible: Sized {
25    /// The type of the reconstructed value.
26    type Value: Serialize
27        + DeserializeOwned
28        + for<'de> SchemaRead<'de, Dst = Self::Value>
29        + SchemaWrite<Src = Self::Value>
30        + Clone
31        + PartialEq
32        + Send
33        + Sync
34        + 'static;
35    /// The type that is sent to / received from other peers.
36    type Opening: Serialize
37        + DeserializeOwned
38        + for<'de> SchemaRead<'de, Dst = Self::Opening>
39        + SchemaWrite<Src = Self::Opening>
40        + Clone
41        + Send
42        + Sync
43        + 'static;
44
45    /// Open the share towards another peer.
46    fn open_to(&self, peer_index: PeerIndex) -> Result<Self::Opening, PrimitiveError>;
47
48    /// Open the share towards all other peers. Returns an iterator with either one opening for
49    /// each peer or a single opening for all peers.
50    fn open_to_all_others(&self) -> impl ExactSizeIterator<Item = Self::Opening>;
51
52    /// Reconstruct a secret from openings coming from all other parties.
53    fn reconstruct(&self, openings: Vec<Self::Opening>) -> Result<Self::Value, PrimitiveError>;
54
55    /// Reconstruct a secret from a collection of shares, by opening each share
56    /// towards all other peers, reconstructing `n` secrets from the openings and
57    /// checking that they are all equal.
58    fn reconstruct_all<T: Borrow<Self>>(shares: Vec<T>) -> Result<Self::Value, PrimitiveError> {
59        let n_parties = shares.len();
60        if n_parties < 2 {
61            return Err(PrimitiveError::MinimumLength(2, n_parties));
62        }
63        // Open each share to all other peers.
64        let mut all_openings = shares
65            .iter()
66            .map(|share| share.borrow().open_to_all_others())
67            .collect::<Vec<_>>();
68        // Reconstruct each secret.
69        enumerate(shares.iter())
70            .map(|(i, share)| {
71                let my_openings = enumerate(all_openings.iter_mut())
72                    .take_exact(n_parties)
73                    .filter(|(j, _)| i != *j)
74                    .map(|(_, opening)| opening.next())
75                    .collect::<Option<Vec<_>>>()
76                    .ok_or_else(|| PrimitiveError::InvalidPeerIndex(i, shares.len() - 1))?;
77                share.borrow().reconstruct(my_openings)
78            })
79            // Check that all reconstructed secrets are equal.
80            .reduce(|previous, current| match (previous, current) {
81                (Ok(prev), Ok(curr)) => match prev == curr {
82                    true => Ok(prev),
83                    false => Err(PrimitiveError::WrongOpening(
84                        serde_json::to_string(&prev).unwrap(),
85                        serde_json::to_string(&curr).unwrap(),
86                    )),
87                },
88                (Err(e), _) | (_, Err(e)) => Err(e),
89            })
90            .unwrap() // Safe because `shares.len() >= 2`
91    }
92}
93
94impl<T: Reconstructible<Opening: Clone>> Reconstructible for Vec<T> {
95    type Opening = Vec<T::Opening>;
96    type Value = Vec<T::Value>;
97
98    fn open_to(&self, peer_index: PeerIndex) -> Result<Self::Opening, PrimitiveError> {
99        self.iter().map(|share| share.open_to(peer_index)).collect()
100    }
101
102    fn open_to_all_others(&self) -> impl ExactSizeIterator<Item = Self::Opening> {
103        let all_openings: Vec<Vec<_>> = self
104            .iter()
105            .map(|share| share.open_to_all_others().collect())
106            .collect();
107
108        transpose(all_openings).into_iter()
109    }
110
111    fn reconstruct(&self, openings: Vec<Self::Opening>) -> Result<Self::Value, PrimitiveError> {
112        if openings.is_empty() {
113            return Err(PrimitiveError::MinimumLength(1, 0));
114        }
115
116        if openings[0].len() != self.len() {
117            return Err(PrimitiveError::InvalidParameters(
118                "Number of openings must match number of shares.".to_string(),
119            ));
120        }
121
122        // Iterate over all the i-th elements of each entry of openings
123        let mut reconstructed = Vec::with_capacity(self.len());
124        for (i, share) in self.iter().enumerate() {
125            let my_openings: Vec<_> = openings
126                .iter()
127                .map(|opening| opening.get(i).cloned())
128                .collect::<Option<Vec<_>>>()
129                .ok_or_else(|| {
130                    PrimitiveError::InvalidParameters(
131                        "Opening is missing for some share.".to_string(),
132                    )
133                })?;
134            reconstructed.push(share.reconstruct(my_openings)?);
135        }
136        Ok(reconstructed)
137    }
138}
139
140impl<T: Reconstructible<Opening: Clone>> Reconstructible for Arc<[T]> {
141    type Opening = Arc<[T::Opening]>;
142    type Value = Arc<[T::Value]>;
143
144    fn open_to(&self, peer_index: PeerIndex) -> Result<Self::Opening, PrimitiveError> {
145        self.iter().map(|share| share.open_to(peer_index)).collect()
146    }
147
148    fn open_to_all_others(&self) -> impl ExactSizeIterator<Item = Self::Opening> {
149        let all_openings: Vec<Vec<_>> = self
150            .iter()
151            .map(|share| share.open_to_all_others().collect())
152            .collect();
153
154        transpose(all_openings)
155            .into_iter()
156            .map(Arc::from)
157            .collect::<Vec<_>>()
158            .into_iter()
159    }
160
161    fn reconstruct(&self, openings: Vec<Self::Opening>) -> Result<Self::Value, PrimitiveError> {
162        if openings.is_empty() {
163            return Err(PrimitiveError::MinimumLength(1, 0));
164        }
165
166        if openings[0].len() != self.len() {
167            return Err(PrimitiveError::InvalidParameters(
168                "Number of openings must match number of shares.".to_string(),
169            ));
170        }
171
172        // Iterate over all the i-th elements of each entry of openings
173        let mut reconstructed = Vec::with_capacity(self.len());
174        for (i, share) in self.iter().enumerate() {
175            let my_openings: Vec<_> = openings
176                .iter()
177                .map(|opening| opening.get(i).cloned())
178                .collect::<Option<Vec<_>>>()
179                .ok_or_else(|| {
180                    PrimitiveError::InvalidParameters(
181                        "Opening is missing for some share.".to_string(),
182                    )
183                })?;
184            reconstructed.push(share.reconstruct(my_openings)?);
185        }
186
187        Ok(reconstructed.into())
188    }
189}
190
191impl<T: Reconstructible, S: Reconstructible> Reconstructible for (T, S) {
192    type Opening = (T::Opening, S::Opening);
193    type Value = (T::Value, S::Value);
194
195    fn open_to(&self, peer_index: PeerIndex) -> Result<Self::Opening, PrimitiveError> {
196        Ok((self.0.open_to(peer_index)?, self.1.open_to(peer_index)?))
197    }
198
199    fn open_to_all_others(&self) -> impl ExactSizeIterator<Item = Self::Opening> {
200        let all_openings_t: Vec<_> = self.0.open_to_all_others().collect();
201        let all_openings_s: Vec<_> = self.1.open_to_all_others().collect();
202        izip!(all_openings_t, all_openings_s).map(|(o1, o2)| (o1, o2))
203    }
204
205    fn reconstruct(&self, openings: Vec<Self::Opening>) -> Result<Self::Value, PrimitiveError> {
206        let (openings_t, openings_s): (Vec<_>, Vec<_>) = openings.into_iter().unzip();
207        Ok((
208            self.0.reconstruct(openings_t)?,
209            self.1.reconstruct(openings_s)?,
210        ))
211    }
212}
213
214/// A trait used to add a plaintext to a certain type. Commonly used to correct
215/// shares after a masked opening, or to add a public constant
216///
217/// The `Plaintext` type defaults to [`Self::Value`], but batched shares additionally
218/// implement it with `Plaintext` set to the *non-batched* element type, which broadcasts
219/// the single plaintext to every column of the batch.
220pub trait PlaintextOps<Plaintext = <Self as Reconstructible>::Value>:
221    Reconstructible + Clone
222{
223    /// Add a plaintext to the share, consuming the share and returning a new one.
224    fn add_plaintext(self, ptx: &Plaintext, is_first_peer: bool) -> Self;
225
226    /// Subtract a plaintext from the share, consuming the share and returning a new one.
227    fn sub_plaintext(self, ptx: &Plaintext, is_first_peer: bool) -> Self;
228}
229
230#[cfg(test)]
231mod tests {
232    use super::*;
233    use crate::{
234        algebra::elliptic_curve::Curve25519Ristretto,
235        random::Random,
236        sharing::ScalarShares,
237    };
238
239    #[test]
240    fn test_reconstruct_vec() {
241        let n_parties = 3;
242        let mut rng = crate::random::test_rng();
243
244        let scalar_shares: Vec<_> =
245            ScalarShares::<Curve25519Ristretto, typenum::U5>::random_n(&mut rng, n_parties);
246        let scalar_shares = scalar_shares
247            .into_iter()
248            .map(|s| s.into_iter().collect::<Vec<_>>())
249            .collect::<Vec<_>>();
250
251        let reconstructed =
252            Vec::<ScalarShare<Curve25519Ristretto>>::reconstruct_all(scalar_shares.clone())
253                .unwrap();
254        let expected = (0..5)
255            .map(|i| {
256                ScalarShare::<Curve25519Ristretto>::reconstruct_all(
257                    scalar_shares.iter().map(|v| v[i].clone()).collect(),
258                )
259                .unwrap()
260            })
261            .collect::<Vec<_>>();
262        assert_eq!(reconstructed, expected);
263    }
264
265    #[test]
266    fn test_reconstruct_tuple() {
267        let n_parties = 3;
268        let mut rng = crate::random::test_rng();
269
270        let scalar_shares: Vec<_> =
271            ScalarShare::<Curve25519Ristretto>::random_n(&mut rng, n_parties);
272        let base_field_shares: Vec<_> =
273            BaseFieldShare::<Curve25519Ristretto>::random_n(&mut rng, n_parties);
274
275        let shares: Vec<(
276            ScalarShare<Curve25519Ristretto>,
277            BaseFieldShare<Curve25519Ristretto>,
278        )> = izip!(&scalar_shares, &base_field_shares)
279            .map(|(s, b)| (s.clone(), b.clone()))
280            .collect();
281
282        let reconstructed = <(
283            ScalarShare<Curve25519Ristretto>,
284            BaseFieldShare<Curve25519Ristretto>,
285        )>::reconstruct_all(shares)
286        .unwrap();
287
288        assert_eq!(
289            reconstructed.0,
290            ScalarShare::<Curve25519Ristretto>::reconstruct_all(scalar_shares).unwrap()
291        );
292        assert_eq!(
293            reconstructed.1,
294            BaseFieldShare::<Curve25519Ristretto>::reconstruct_all(base_field_shares).unwrap()
295        );
296    }
297}
primitives/sharing/mod.rs

primitives/sharing/
mod.rs
