primitives/sharing/authenticated/

curve_share.rs

use std::ops::{Add, AddAssign, Mul, MulAssign, Neg, Sub, SubAssign};

use itertools::enumerate;
use serde::{Deserialize, Serialize};
use subtle::{Choice, ConstantTimeEq};
use wincode::{SchemaRead, SchemaWrite};

use super::GlobalCurveKey;
use crate::{
    algebra::elliptic_curve::{Curve, Point, Scalar, ScalarAsExtension},
    errors::PrimitiveError,
    izip_eq,
    random::{CryptoRngCore, Random, RandomWith},
    sharing::{
        authenticated::NParties,
        unauthenticated::AdditiveShares,
        AddPlaintext,
        CurveKey,
        GlobalFieldKey,
        IsFirstPeer,
        Reconstructible,
        VerifiableWith,
    },
    types::{CollectAll, ConditionallySelectable, PeerIndex},
    utils::IntoExactSizeIterator,
};

#[derive(
    Debug, Copy, Clone, Default, PartialEq, Eq, Serialize, Deserialize, SchemaRead, SchemaWrite,
)]
#[serde(bound = "C: Curve")]
#[repr(C)]
pub struct OpenPointShare<C: Curve> {
    pub(crate) value: Point<C>,
    pub(crate) mac: Point<C>,
}

impl<C: Curve> OpenPointShare<C> {
    pub fn new(value: Point<C>, mac: Point<C>) -> Self {
        Self { value, mac }
    }

    pub fn get_value(&self) -> &Point<C> {
        &self.value
    }

    pub fn get_mac(&self) -> &Point<C> {
        &self.mac
    }
}

/// A share of a point on a curve, with its associated MACs and the keys for all
/// other parties' shares.
#[derive(Debug, Clone, Default, PartialEq, Eq, Serialize, Deserialize)]
#[serde(bound = "C: Curve")]
pub struct PointShare<C: Curve> {
    pub(crate) value: Point<C>,          // X_i
    pub(crate) macs: Box<[Point<C>]>,    // {MAC(x_i)_j} ∀j∈[1..n]∖{i}
    pub(crate) keys: Box<[CurveKey<C>]>, // {(α_ij, β_ij)} ∀j∈[1..n]∖{i}
}

impl<C: Curve> PointShare<C> {
    pub fn try_new(
        value: Point<C>,
        macs: Box<[Point<C>]>,
        keys: Box<[CurveKey<C>]>,
    ) -> Result<Self, PrimitiveError> {
        if macs.is_empty() {
            return Err(PrimitiveError::MinimumLength(2, 0));
        }
        if macs.len() != keys.len() {
            return Err(PrimitiveError::InvalidSize(keys.len(), macs.len()));
        }
        /* NOTE: We assume length equality for macs & keys from this point on */
        Ok(Self { value, macs, keys })
    }

    fn new(value: Point<C>, macs: Box<[Point<C>]>, keys: Box<[CurveKey<C>]>) -> Self {
        Self { value, macs, keys }
    }

    pub fn zero_from_alphas(
        alphas: impl ExactSizeIterator<Item = GlobalFieldKey<C::Scalar>>,
    ) -> Self {
        let n_peers = alphas.len();

        let value = Point::identity();
        let macs = vec![Point::<C>::identity(); n_peers].into_boxed_slice();
        let keys = alphas
            .map(|alpha| CurveKey::new(alpha, Point::identity()))
            .collect();
        PointShare::new(value, macs, keys)
    }

    pub fn get_value(&self) -> &Point<C> {
        &self.value
    }

    #[inline]
    pub fn value(self) -> Point<C> {
        self.value
    }

    pub fn get_keys(&self) -> &[CurveKey<C>] {
        &self.keys
    }

    pub fn get_key(&self, index: PeerIndex) -> Option<&CurveKey<C>> {
        self.keys.get(index)
    }

    pub fn get_macs(&self) -> &[Point<C>] {
        &self.macs
    }

    pub fn get_mac(&self, index: PeerIndex) -> Option<&Point<C>> {
        self.macs.get(index)
    }

    #[inline]
    pub fn get_alphas(&self) -> impl ExactSizeIterator<Item = GlobalCurveKey<C>> + '_ {
        self.keys.iter().map(|key| key.get_alpha())
    }
}

// --------------------
// |   Verification   |
// --------------------
impl<C: Curve> VerifiableWith for PointShare<C> {
    type VerificationData = ();
    /// Check the MACs of the share received from another peer.
    #[inline]
    fn verify_from_peer_with(
        &self,
        open_share: &OpenPointShare<C>,
        peer: PeerIndex,
        _verification_data: (),
    ) -> Result<(), PrimitiveError> {
        self.get_key(peer)
            .ok_or(PrimitiveError::InvalidPeerIndex(peer, self.keys.len()))?
            .verify_mac(open_share)
            .map_err(|e| e.blame(peer))
    }

    /// Check the MACs of each share received from all other peers.
    #[inline]
    fn verify_with(
        &self,
        open_shares: &[OpenPointShare<C>],
        _verification_data: (),
    ) -> Result<(), PrimitiveError> {
        enumerate(izip_eq!(open_shares, &self.keys))
            .map(|(from_peer, (open_share, key))| {
                key.verify_mac(open_share).map_err(|e| e.blame(from_peer))
            })
            .collect_errors()?;
        Ok(())
    }
}

// --------------------------------
// |   Opening & Reconstruction   |
// --------------------------------

impl<C: Curve> Reconstructible for PointShare<C> {
    type Opening = OpenPointShare<C>;
    type Secret = Point<C>;

    /// Open the share towards another peer.
    fn open_to(&self, for_peer: PeerIndex) -> Result<OpenPointShare<C>, PrimitiveError> {
        let mac = self
            .get_mac(for_peer)
            .ok_or(PrimitiveError::InvalidPeerIndex(for_peer, self.macs.len()))?
            .to_owned();
        Ok(OpenPointShare::new(self.get_value().to_owned(), mac))
    }

    /// Open the share towards all other peers.
    fn open_to_all_others(&self) -> impl ExactSizeIterator<Item = OpenPointShare<C>> {
        self.get_macs()
            .iter()
            .map(|mac| OpenPointShare::new(self.get_value().to_owned(), mac.to_owned()))
    }

    /// Reconstruct a secret from openings coming from all other parties.
    fn reconstruct(&self, openings: &[OpenPointShare<C>]) -> Result<Self::Secret, PrimitiveError> {
        if openings.len() != self.get_keys().len() {
            return Err(PrimitiveError::InvalidSize(
                self.get_keys().len(),
                openings.len(),
            ));
        }
        self.verify_with(openings, ())?;
        Ok(openings
            .iter()
            .fold(self.get_value().to_owned(), |acc, open_share| {
                acc + open_share.get_value()
            }))
    }
}

// -------------------------
// |   Random Generation   |
// -------------------------

fn compute_macs<C: Curve>(
    all_unauth_shares: &[Point<C>],
    all_keys: &[Box<[CurveKey<C>]>],
) -> Vec<Box<[Point<C>]>> {
    let mut all_key_iters = all_keys.iter().map(|k| k.iter()).collect::<Vec<_>>();
    enumerate(all_unauth_shares.iter())
        .map(|(i, my_unauth_share)| {
            enumerate(all_key_iters.iter_mut())
                .filter(|(j, _)| *j != i)
                .map(|(_, keys_iter)| keys_iter.next().unwrap().compute_mac(my_unauth_share))
                .collect()
        })
        .collect()
}

impl<C: Curve> Random for PointShare<C> {
    fn random(_rng: impl CryptoRngCore) -> Self {
        unimplemented!(
            "Type {} does not support `random` since it needs to know `n_parties`. Use `random_with(..., n_parties)` instead.",
            std::any::type_name::<Self>()
        )
    }

    /// Generate one random field share per peer, with consistent MACs and keys across all peers.
    fn random_n<Container: FromIterator<Self>>(
        mut rng: impl CryptoRngCore,
        n_parties: NParties,
    ) -> Container {
        let all_unauth_shares: Vec<_> = Point::random_n(&mut rng, n_parties);
        let all_keys = (0..n_parties)
            .map(|_| CurveKey::<C>::random_n(&mut rng, n_parties - 1))
            .collect::<Vec<_>>();
        let all_macs = compute_macs(&all_unauth_shares, &all_keys);
        izip_eq!(all_unauth_shares, all_macs, all_keys)
            .map(|(value, macs, keys)| PointShare { value, macs, keys })
            .collect()
    }
}

impl<C: Curve> RandomWith<NParties> for PointShare<C> {
    /// Generate a random field share, with Macs and keys for all the other parties.
    fn random_with(mut rng: impl CryptoRngCore, n_parties: NParties) -> Self {
        PointShare {
            value: Point::random(&mut rng),
            macs: Point::<C>::random_n(&mut rng, n_parties - 1),
            keys: CurveKey::<C>::random_n(&mut rng, n_parties - 1),
        }
    }
}

impl<C: Curve> RandomWith<(NParties, Point<C>)> for PointShare<C> {
    /// Generate a random field share with a specific secret share as value and random macs & keys.
    fn random_with(mut rng: impl CryptoRngCore, n_parties_value: (NParties, Point<C>)) -> Self {
        let (n_parties, value) = n_parties_value;
        PointShare {
            value,
            macs: Point::<C>::random_n(&mut rng, n_parties - 1),
            keys: CurveKey::<C>::random_n(&mut rng, n_parties - 1),
        }
    }
}

impl<C: Curve> RandomWith<Point<C>> for PointShare<C> {
    fn random_with(_rng: impl CryptoRngCore, _data: Point<C>) -> Self {
        unimplemented!(
            "Type {} does not support `random_with` since it needs to know `n_parties`. Use `random_n_with` instead.",
            std::any::type_name::<Self>()
        )
    }

    /// Secret share a value among n parties, generating an authenticated share for each
    /// peer with consistent MACs and keys across all peers.
    fn random_n_with<Container: FromIterator<Self>>(
        mut rng: impl CryptoRngCore,
        n_parties: NParties,
        value: Point<C>,
    ) -> Container {
        let all_unauth_shares = value.to_additive_shares(n_parties, &mut rng);
        let all_keys = (0..n_parties)
            .map(|_| CurveKey::<C>::random_n(&mut rng, n_parties - 1))
            .collect::<Vec<_>>();
        let all_macs = compute_macs(&all_unauth_shares, &all_keys);
        izip_eq!(all_unauth_shares, all_macs, all_keys)
            .map(|(value, macs, keys)| PointShare { value, macs, keys })
            .collect()
    }

    /// Generate a random field share with a specific secret share as value,
    /// with consistent random MACs and keys across all peers.
    fn random_n_with_each<Container: FromIterator<Self>>(
        mut rng: impl CryptoRngCore,
        all_unauth_shares: impl IntoExactSizeIterator<Item = Point<C>>,
    ) -> Container {
        let all_unauth_shares = all_unauth_shares.into_iter().collect::<Vec<_>>();
        let n_parties = all_unauth_shares.len();
        let all_keys = (0..n_parties)
            .map(|_| CurveKey::<C>::random_n(&mut rng, n_parties - 1))
            .collect::<Vec<_>>();
        let all_macs = compute_macs(&all_unauth_shares, &all_keys);
        izip_eq!(all_unauth_shares, all_macs, all_keys)
            .map(|(value, macs, keys)| PointShare { value, macs, keys })
            .collect()
    }
}

impl<C: Curve> RandomWith<Vec<GlobalCurveKey<C>>> for PointShare<C> {
    /// Generate a random field share from its global keys (alphas).
    fn random_with(mut rng: impl CryptoRngCore, alphas: Vec<GlobalCurveKey<C>>) -> Self {
        let n_other_parties = alphas.len();
        PointShare {
            value: Point::random(&mut rng),
            macs: Point::<C>::random_n(&mut rng, n_other_parties),
            keys: CurveKey::<C>::random_n_with_each(&mut rng, alphas),
        }
    }

    /// Generate one random field share per peer from their global keys (alphas).
    fn random_n_with_each<Container: FromIterator<Self>>(
        mut rng: impl CryptoRngCore,
        all_alphas: impl IntoExactSizeIterator<Item = Vec<GlobalCurveKey<C>>>,
    ) -> Container {
        let all_alphas = all_alphas.into_iter();
        let all_unauth_shares: Vec<_> = Point::random_n(&mut rng, all_alphas.len());
        let all_keys = all_alphas
            .into_iter()
            .map(|my_alphas| CurveKey::<C>::random_n_with_each(&mut rng, my_alphas))
            .collect::<Vec<_>>();
        let all_macs = compute_macs(&all_unauth_shares, &all_keys);
        izip_eq!(all_unauth_shares, all_macs, all_keys)
            .map(|(value, macs, keys)| PointShare { value, macs, keys })
            .collect()
    }
}

impl<C: Curve> RandomWith<(Point<C>, Vec<GlobalCurveKey<C>>)> for PointShare<C> {
    /// Generate a random field share from its global keys (alphas) and its share
    fn random_with(
        mut rng: impl CryptoRngCore,
        value_alphas: (Point<C>, Vec<GlobalCurveKey<C>>),
    ) -> Self {
        let (value, alphas) = value_alphas;
        let n_other_parties = alphas.len();
        PointShare {
            value,
            macs: Point::<C>::random_n(&mut rng, n_other_parties),
            keys: CurveKey::<C>::random_n_with_each(&mut rng, alphas),
        }
    }

    /// Generate one random field share per peer from their global keys (alphas).
    fn random_n_with_each<Container: FromIterator<Self>>(
        mut rng: impl CryptoRngCore,
        unauth_shares_and_alphas: impl IntoIterator<Item = (Point<C>, Vec<GlobalCurveKey<C>>)>,
    ) -> Container {
        let (all_unauth_shares, all_keys): (Vec<_>, Vec<_>) = unauth_shares_and_alphas
            .into_iter()
            .map(|(value, my_alphas)| {
                (
                    value,
                    CurveKey::<C>::random_n_with_each(&mut rng, my_alphas),
                )
            })
            .unzip();
        let all_macs = compute_macs(&all_unauth_shares, &all_keys);
        izip_eq!(all_unauth_shares, all_macs, all_keys)
            .map(|(value, macs, keys)| PointShare::new(value, macs, keys))
            .collect()
    }
}

impl<C: Curve> RandomWith<(Point<C>, Vec<Vec<GlobalCurveKey<C>>>)> for PointShare<C> {
    fn random_with(
        _source: impl CryptoRngCore,
        _data: (Point<C>, Vec<Vec<GlobalCurveKey<C>>>),
    ) -> Self {
        unimplemented!(
            "Cannot discern what alpha to use for this peer. Use `random_n_with` instead."
        );
    }

    /// Generate a random field share per peer from a value to secret share and global keys
    /// (alphas).
    fn random_n_with<Container: FromIterator<Self>>(
        mut rng: impl CryptoRngCore,
        n_parties: usize,
        secret_value_and_alphas: (Point<C>, Vec<Vec<GlobalCurveKey<C>>>),
    ) -> Container {
        let (secret_value, all_alphas) = secret_value_and_alphas;
        assert_eq!(
            all_alphas.len(),
            n_parties,
            "Number of alphas must match the number of parties"
        );
        let all_unauth_shares = secret_value.to_additive_shares(all_alphas.len(), &mut rng);
        let all_keys = all_alphas
            .into_iter()
            .map(|my_alphas| CurveKey::<C>::random_n_with_each(&mut rng, my_alphas))
            .collect::<Vec<_>>();
        let all_macs = compute_macs(&all_unauth_shares, &all_keys);
        izip_eq!(all_unauth_shares, all_macs, all_keys)
            .map(|(value, macs, keys)| PointShare::new(value, macs, keys))
            .collect()
    }
}

// ------------------------------------
// | Curve Arithmetic Implementations |
// ------------------------------------

// === Addition === //

#[macros::op_variants(owned, borrowed, flipped_commutative)]
impl<'a, C: Curve> Add<&'a PointShare<C>> for PointShare<C> {
    type Output = PointShare<C>;

    #[inline]
    fn add(self, other: &'a PointShare<C>) -> Self::Output {
        PointShare {
            value: self.value + other.value,
            macs: izip_eq!(self.macs, &other.macs)
                .map(|(a, b)| a + b)
                .collect(),
            keys: izip_eq!(self.keys, &other.keys)
                .map(|(a, b)| a + b)
                .collect(),
        }
    }
}

#[macros::op_variants(owned)]
impl<'a, C: Curve> AddAssign<&'a PointShare<C>> for PointShare<C> {
    #[inline]
    fn add_assign(&mut self, other: &'a PointShare<C>) {
        self.value += other.value;
        izip_eq!(&mut self.keys, &other.keys).for_each(|(a, b)| *a += b);
        izip_eq!(&mut self.macs, &other.macs).for_each(|(a, b)| *a += b);
    }
}

// === Subtraction === //

#[macros::op_variants(owned, borrowed, flipped)]
impl<'a, C: Curve> Sub<&'a PointShare<C>> for PointShare<C> {
    type Output = PointShare<C>;

    #[inline]
    fn sub(self, other: &'a PointShare<C>) -> Self::Output {
        PointShare {
            value: self.value - other.value,
            macs: izip_eq!(self.macs, &other.macs)
                .map(|(a, b)| a - b)
                .collect(),
            keys: izip_eq!(self.keys, &other.keys)
                .map(|(a, b)| a - b)
                .collect(),
        }
    }
}

#[macros::op_variants(owned)]
impl<'a, C: Curve> SubAssign<&'a PointShare<C>> for PointShare<C> {
    #[inline]
    fn sub_assign(&mut self, other: &'a PointShare<C>) {
        self.value -= other.value;
        izip_eq!(&mut self.keys, &other.keys).for_each(|(a, b)| *a -= b);
        izip_eq!(&mut self.macs, &other.macs).for_each(|(a, b)| *a -= b);
    }
}

// === Broadcast multiplication === //

#[macros::op_variants(owned, borrowed, flipped)]
impl<'a, C: Curve> Mul<&'a ScalarAsExtension<C>> for PointShare<C> {
    type Output = PointShare<C>;

    #[inline]
    fn mul(mut self, other: &'a ScalarAsExtension<C>) -> Self::Output {
        self.value *= other;
        izip_eq!(&mut self.keys).for_each(|key| *key *= other);
        izip_eq!(&mut self.macs).for_each(|mac| *mac *= other);
        self
    }
}

#[macros::op_variants(owned, borrowed, flipped)]
impl<'a, C: Curve> Mul<&'a Scalar<C>> for PointShare<C> {
    type Output = PointShare<C>;

    #[inline]
    fn mul(mut self, other: &'a Scalar<C>) -> Self::Output {
        self.value *= other;
        izip_eq!(&mut self.keys).for_each(|key| *key *= other);
        izip_eq!(&mut self.macs).for_each(|mac| *mac *= other);
        self
    }
}

// === MulAssign === //

#[macros::op_variants(owned)]
impl<'a, C: Curve> MulAssign<&'a ScalarAsExtension<C>> for PointShare<C> {
    #[inline]
    fn mul_assign(&mut self, other: &'a ScalarAsExtension<C>) {
        self.value *= other;
        izip_eq!(&mut self.keys).for_each(|key| *key *= other);
        izip_eq!(&mut self.macs).for_each(|mac| *mac *= other);
    }
}

#[macros::op_variants(owned)]
impl<'a, C: Curve> MulAssign<&'a Scalar<C>> for PointShare<C> {
    #[inline]
    fn mul_assign(&mut self, other: &'a Scalar<C>) {
        self.value *= other;
        izip_eq!(&mut self.keys).for_each(|key| *key *= other);
        izip_eq!(&mut self.macs).for_each(|mac| *mac *= other);
    }
}

// === Negation === //

#[macros::op_variants(borrowed)]
impl<C: Curve> Neg for PointShare<C> {
    type Output = PointShare<C>;

    #[inline]
    fn neg(self) -> Self::Output {
        PointShare {
            value: -self.value,
            keys: self.keys.iter().map(|key| -key).collect(),
            macs: self.macs.iter().map(|mac| -mac).collect(),
        }
    }
}

// === Constant addition / subtraction === //

impl<C: Curve> AddPlaintext for PointShare<C> {
    type AssociatedInformation = IsFirstPeer;

    /// Adds a public constant to the secret shared value, updating the keys accordingly.
    /// A designated peer (P_0) will modify its value, while the other peers will update their keys.
    #[inline]
    fn add_plaintext(&self, constant: &Point<C>, is_peer_zero: IsFirstPeer) -> Self {
        let result = self.clone();
        result.add_plaintext_owned(constant, is_peer_zero)
    }

    /// Adds a public constant to the secret shared value, updating the keys accordingly.
    /// A designated peer (P_0) will modify its value, while the other peers will update their keys.
    #[inline]
    fn add_plaintext_owned(mut self, constant: &Point<C>, is_peer_zero: IsFirstPeer) -> Self {
        if is_peer_zero {
            self.value += constant;
        } else {
            let key0 = self.keys.get_mut(0).expect("Missing key 0");
            key0.beta -= *key0.alpha * constant;
        }
        self
    }
}

// === Constant time equality / select === //

impl<C: Curve> ConditionallySelectable for PointShare<C> {
    fn conditional_select(a: &Self, b: &Self, choice: Choice) -> Self {
        PointShare {
            value: Point::conditional_select(&a.value, &b.value, choice),
            keys: izip_eq!(&a.keys, &b.keys)
                .map(|(a, b)| CurveKey::conditional_select(a, b, choice))
                .collect(),
            macs: izip_eq!(&a.macs, &b.macs)
                .map(|(a, b)| Point::conditional_select(a, b, choice))
                .collect(),
        }
    }
}

impl<C: Curve> ConstantTimeEq for PointShare<C> {
    #[inline]
    fn ct_eq(&self, other: &Self) -> Choice {
        self.value.ct_eq(&other.value)
            & izip_eq!(&self.keys, &other.keys).fold(1.into(), |acc, (self_key, other_key)| {
                acc & self_key.ct_eq(other_key)
            })
            & self.macs.ct_eq(&other.macs)
    }
}

#[cfg(test)]
mod tests {
    use itertools::enumerate;

    use super::*;
    use crate::{
        algebra::elliptic_curve::Curve25519Ristretto as C,
        random::{self},
        sharing::Verifiable,
    };

    // TODO: Generalize once PairwiseAuthenticatedShare trait is implemented.

    //////////////////////////////////////////////////
    // CHANGE ONLY THESE TO TEST ANOTHER SHARE TYPE //
    pub type Value = Point<C>;
    pub type Constant = Scalar<C>;
    pub type Share = PointShare<C>;
    pub type GlobalKey = GlobalCurveKey<C>;
    //////////////////////////////////////////////////

    pub const N_PARTIES: usize = 3;

    #[test]
    fn test_open_to() {
        let mut rng = random::test_rng();
        let local_share = Share::random_with(&mut rng, N_PARTIES);

        for i in 0..N_PARTIES - 1 {
            let open_share = local_share.open_to(i).unwrap();
            assert_eq!(open_share.get_value(), &local_share.value);
            assert_eq!(open_share.get_mac(), &local_share.macs[i]);
        }
    }

    #[test]
    fn test_random() {
        let mut rng = random::test_rng();

        // Generate a completely random share
        let share = Share::random_with(&mut rng, N_PARTIES);
        assert_eq!(share.get_macs().len(), N_PARTIES - 1);
        assert_eq!(share.get_keys().len(), N_PARTIES - 1);

        // Generate a share with a specific value
        let value = &Value::random(&mut rng);
        let share_with_value = Share::random_with(&mut rng, (N_PARTIES, value.to_owned()));
        assert_eq!(share_with_value.get_value(), value);
        assert_eq!(share_with_value.get_macs().len(), N_PARTIES - 1);
        assert_eq!(share_with_value.get_keys().len(), N_PARTIES - 1);
    }

    #[test]
    fn test_random_vec_and_reconstruct() {
        let mut rng = random::test_rng();

        // Generate a vector of random shares, one per party
        let shares: Vec<_> = Share::random_n(&mut rng, N_PARTIES);
        assert_eq!(shares.len(), N_PARTIES);
        for share in &shares {
            assert_eq!(share.get_macs().len(), N_PARTIES - 1);
            assert_eq!(share.get_keys().len(), N_PARTIES - 1);
        }
        let unauthenticated_shares = shares
            .iter()
            .map(|s| s.get_value().to_owned())
            .collect::<Vec<_>>();
        let expected = Value::from_additive_shares(&unauthenticated_shares);
        let reconstructed = Share::reconstruct_all(&shares).unwrap();
        assert_eq!(reconstructed, expected);

        // Secret share a value among n parties
        let value = &Value::random(&mut rng);
        let shares: Vec<_> = Share::random_n_with(&mut rng, N_PARTIES, value.to_owned());
        assert_eq!(shares.len(), N_PARTIES);
        for share in &shares {
            assert_eq!(share.get_macs().len(), N_PARTIES - 1);
            assert_eq!(share.get_keys().len(), N_PARTIES - 1);
        }
        let reconstructed = Share::reconstruct_all(&shares).unwrap();
        assert_eq!(reconstructed, value.to_owned());
    }

    #[test]
    fn test_random_vec_with_global_key_and_reconstruct() {
        let mut rng = random::test_rng();

        // Generate n authenticated shares from n global keys (alphas)
        let alphas = Vec::<Vec<GlobalKey>>::random_with(&mut rng, N_PARTIES);
        let shares_from_alphas: Vec<_> = Share::random_n_with_each(&mut rng, alphas.clone());
        assert_eq!(shares_from_alphas.len(), N_PARTIES);
        for (share_a, my_alphas) in izip_eq!(&shares_from_alphas, alphas) {
            assert_eq!(share_a.get_macs().len(), N_PARTIES - 1);
            assert_eq!(share_a.get_keys().len(), N_PARTIES - 1);
            assert_eq!(share_a.get_alphas().collect::<Vec<_>>(), my_alphas);
        }
        Share::verify_all(&shares_from_alphas).unwrap(); // Verify all MACs

        // Generate n authenticated shares from a value and n global keys (alphas)
        let value = &Value::random(&mut rng);
        let alphas = Vec::<Vec<GlobalKey>>::random_with(&mut rng, N_PARTIES);
        let shares_from_value_and_alphas: Vec<_> =
            Share::random_n_with(&mut rng, N_PARTIES, (value.to_owned(), alphas.clone()));
        assert_eq!(shares_from_value_and_alphas.len(), N_PARTIES);
        for (share_a, my_alphas) in izip_eq!(&shares_from_value_and_alphas, alphas) {
            assert_eq!(share_a.get_macs().len(), N_PARTIES - 1);
            assert_eq!(share_a.get_keys().len(), N_PARTIES - 1);
            assert_eq!(share_a.get_alphas().collect::<Vec<_>>(), my_alphas);
        }
        let reconstructed = Share::reconstruct_all(&shares_from_value_and_alphas).unwrap();
        assert_eq!(&reconstructed, value);

        // Generate n authenticated shares from n unauthenticated shares and n global keys (alphas)
        let value = Value::random(&mut rng);
        let unauth_shares = value.to_additive_shares(N_PARTIES, &mut rng);
        let alphas = Vec::<Vec<GlobalKey>>::random_with(&mut rng, N_PARTIES);
        let shares_from_unauth_and_alphas: Vec<_> =
            Share::random_n_with_each(&mut rng, izip_eq!(unauth_shares.clone(), alphas.clone()));
        assert_eq!(shares_from_unauth_and_alphas.len(), N_PARTIES);
        for (share_a, my_alphas) in izip_eq!(&shares_from_unauth_and_alphas, alphas) {
            assert_eq!(share_a.get_macs().len(), N_PARTIES - 1);
            assert_eq!(share_a.get_keys().len(), N_PARTIES - 1);
            assert_eq!(share_a.get_alphas().collect::<Vec<_>>(), my_alphas);
        }
        let reconstructed = Share::reconstruct_all(&shares_from_unauth_and_alphas).unwrap();
        assert_eq!(reconstructed, value);
    }

    #[test]
    fn test_verify_mac() {
        let mut rng = random::test_rng();

        let shares: Vec<_> = Share::random_n(&mut rng, N_PARTIES);

        // Verify each open separately
        enumerate(shares.iter()).for_each(|(i, s_i)| {
            enumerate(shares.iter())
                .filter(|(j, _)| i != *j)
                .for_each(|(j, s_j)| {
                    let open_share = s_j.open_to(i - (i > j) as usize).unwrap();
                    s_i.verify_from(&open_share, j - (j > i) as usize).unwrap();
                });
        });

        // Verify all openings at once
        Share::verify_all(&shares).unwrap();
    }

    #[test]
    fn test_add() {
        let mut rng = random::test_rng();

        let alphas = Vec::<Vec<GlobalKey>>::random_with(&mut rng, N_PARTIES);
        let a = &Value::random(&mut rng);
        let b = &Value::random(&mut rng);

        let shares_a: Vec<_> =
            Share::random_n_with(&mut rng, N_PARTIES, (a.to_owned(), alphas.clone()));
        let shares_b: Vec<_> = Share::random_n_with(&mut rng, N_PARTIES, (b.to_owned(), alphas));

        // &a + &b
        let shares_a_ref_plus_b_ref = izip_eq!(&shares_a, &shares_b)
            .map(|(share_a, share_b)| share_a + share_b)
            .collect::<Vec<_>>();
        let reconstructed = Share::reconstruct_all(&shares_a_ref_plus_b_ref).unwrap();
        assert_eq!(reconstructed, a + b);

        // &a + b
        let shares_a_ref_plus_b = izip_eq!(&shares_a, shares_b.clone())
            .map(|(share_a, share_b)| share_a + share_b)
            .collect::<Vec<_>>();
        let reconstructed = Share::reconstruct_all(&shares_a_ref_plus_b).unwrap();
        assert_eq!(reconstructed, a + b);

        // a + &b
        let shares_a_plus_b_ref = izip_eq!(shares_a.clone(), &shares_b)
            .map(|(share_a, share_b)| share_a + share_b)
            .collect::<Vec<_>>();
        let reconstructed = Share::reconstruct_all(&shares_a_plus_b_ref).unwrap();
        assert_eq!(reconstructed, a + b);

        // a + b
        let shares_a_plus_b = izip_eq!(shares_a.clone(), shares_b.clone())
            .map(|(share_a, share_b)| share_a + share_b)
            .collect::<Vec<_>>();
        let reconstructed = Share::reconstruct_all(&shares_a_plus_b).unwrap();
        assert_eq!(reconstructed, a + b);

        // a += &b
        let mut shares_a_add_assign_b_ref = shares_a.clone();
        izip_eq!(&mut shares_a_add_assign_b_ref, &shares_b)
            .for_each(|(share_a, share_b)| *share_a += share_b);
        let reconstructed = Share::reconstruct_all(&shares_a_add_assign_b_ref).unwrap();
        assert_eq!(reconstructed, a + b);

        // a += b
        let mut shares_a_add_assign_b = shares_a.clone();
        izip_eq!(&mut shares_a_add_assign_b, shares_b)
            .for_each(|(share_a, share_b)| *share_a += share_b);
        let reconstructed = Share::reconstruct_all(&shares_a_add_assign_b).unwrap();
        assert_eq!(reconstructed, a + b);
    }

    #[test]
    fn test_add_secret() {
        let mut rng = random::test_rng();

        let a = &Value::random(&mut rng);
        let k = &Value::random(&mut rng);

        let shares_a: Vec<_> = Share::random_n_with(&mut rng, N_PARTIES, a.to_owned());

        // &a + k
        let shares_a_plus_k_ref = enumerate(shares_a.iter())
            .map(|(i, share_a)| share_a.add_plaintext(k, i == 0))
            .collect::<Vec<_>>();
        let reconstructed = Share::reconstruct_all(&shares_a_plus_k_ref).unwrap();
        assert_eq!(reconstructed, a + k);

        // a + k
        let shares_a_plus_k = enumerate(shares_a)
            .map(|(i, share_a)| share_a.add_plaintext_owned(k, i == 0))
            .collect::<Vec<_>>();
        let reconstructed = Share::reconstruct_all(&shares_a_plus_k).unwrap();
        assert_eq!(reconstructed, a + k);
    }

    #[test]
    fn test_mul_constant() {
        let mut rng = random::test_rng();

        let a = &Value::random(&mut rng);
        let k = &Constant::random(&mut rng);

        let shares_a: Vec<_> = Share::random_n_with(&mut rng, N_PARTIES, a.to_owned());

        // a * &k
        let shares_a_times_k = izip_eq!(shares_a.clone())
            .map(|share_a| share_a * k)
            .collect::<Vec<_>>();
        let reconstructed = Share::reconstruct_all(&shares_a_times_k).unwrap();
        assert_eq!(reconstructed, a * k);

        // a *= &k
        let mut shares_a_times_k_assign = shares_a.clone();
        izip_eq!(&mut shares_a_times_k_assign).for_each(|share_a| *share_a *= k);
        let reconstructed = Share::reconstruct_all(&shares_a_times_k_assign).unwrap();
        assert_eq!(reconstructed, a * k);
    }

    #[test]
    fn test_sub() {
        let mut rng = random::test_rng();
        let alphas = Vec::<Vec<GlobalKey>>::random_with(&mut rng, N_PARTIES);

        let a = &Value::random(&mut rng);
        let b = &Value::random(&mut rng);

        let shares_a: Vec<_> =
            Share::random_n_with(&mut rng, N_PARTIES, (a.to_owned(), alphas.clone()));
        let shares_b: Vec<_> = Share::random_n_with(&mut rng, N_PARTIES, (b.to_owned(), alphas));

        // &a - &b
        let shares_a_ref_minus_b_ref = izip_eq!(&shares_a, &shares_b)
            .map(|(share_a, share_b)| share_a - share_b)
            .collect::<Vec<_>>();

        let reconstructed = Share::reconstruct_all(&shares_a_ref_minus_b_ref).unwrap();
        assert_eq!(reconstructed, a - b);

        // &a - b
        let shares_a_ref_minus_b = izip_eq!(&shares_a, shares_b.clone())
            .map(|(share_a, share_b)| share_a - share_b)
            .collect::<Vec<_>>();
        let reconstructed = Share::reconstruct_all(&shares_a_ref_minus_b).unwrap();
        assert_eq!(reconstructed, a - b);

        // a - &b
        let shares_a_minus_b_ref = izip_eq!(shares_a.clone(), &shares_b)
            .map(|(share_a, share_b)| share_a - share_b)
            .collect::<Vec<_>>();
        let reconstructed = Share::reconstruct_all(&shares_a_minus_b_ref).unwrap();
        assert_eq!(reconstructed, a - b);

        // a - b
        let shares_a_minus_b = izip_eq!(shares_a.clone(), shares_b.clone())
            .map(|(share_a, share_b)| share_a - share_b)
            .collect::<Vec<_>>();
        let reconstructed = Share::reconstruct_all(&shares_a_minus_b).unwrap();
        assert_eq!(reconstructed, a - b);

        // a -= &b
        let mut shares_a_sub_assign_b_ref = shares_a.clone();
        izip_eq!(&mut shares_a_sub_assign_b_ref, &shares_b)
            .for_each(|(share_a, share_b)| *share_a -= share_b);
        let reconstructed = Share::reconstruct_all(&shares_a_sub_assign_b_ref).unwrap();
        assert_eq!(reconstructed, a - b);

        // a -= b
        let mut shares_a_sub_assign_b = shares_a.clone();
        izip_eq!(&mut shares_a_sub_assign_b, shares_b)
            .for_each(|(share_a, share_b)| *share_a -= share_b);
        let reconstructed = Share::reconstruct_all(&shares_a_sub_assign_b).unwrap();
        assert_eq!(reconstructed, a - b);
    }

    #[test]
    fn test_neg() {
        let mut rng = random::test_rng();

        let a = Value::random(&mut rng);

        let shares_a: Vec<_> = Share::random_n_with(&mut rng, N_PARTIES, a.to_owned());

        // - &a
        let shares_a_neg_ref = shares_a.iter().map(|share_a| -share_a).collect::<Vec<_>>();
        let reconstructed = Share::reconstruct_all(&shares_a_neg_ref).unwrap();
        assert_eq!(reconstructed, -a.to_owned());

        // - a
        let shares_a_neg = shares_a
            .into_iter()
            .map(|share_a| -share_a)
            .collect::<Vec<_>>();
        let reconstructed = Share::reconstruct_all(&shares_a_neg).unwrap();
        assert_eq!(reconstructed, -a.to_owned());
    }

    #[test]
    fn test_conditional_select() {
        let mut rng = random::test_rng();

        let shares_a = Share::random_with(&mut rng, N_PARTIES);
        let shares_b = Share::random_with(&mut rng, N_PARTIES);

        // Select shares_a
        let choice = Choice::from(0u8);
        let selected = Share::conditional_select(&shares_a, &shares_b, choice);
        assert_eq!(selected, shares_a);

        // Select shares_b
        let choice = Choice::from(1u8);
        let selected = Share::conditional_select(&shares_a, &shares_b, choice);
        assert_eq!(selected, shares_b);
    }

    #[test]
    fn test_ct_eq() {
        let mut rng = random::test_rng();

        let shares_a = Share::random_with(&mut rng, N_PARTIES);
        let shares_b = Share::random_with(&mut rng, N_PARTIES);

        // Check equality
        assert!(Into::<bool>::into(shares_a.ct_eq(&shares_a.clone())));
        assert!(Into::<bool>::into(shares_b.ct_eq(&shares_b.clone())));
        assert!(!Into::<bool>::into(shares_a.ct_eq(&shares_b)));
        assert!(!Into::<bool>::into(shares_b.ct_eq(&shares_a)));
    }
}