primitives/sharing/authenticated/

field_share.rs

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

use itertools::enumerate;
use num_traits::Zero;
use serde::{Deserialize, Serialize};
use subtle::{Choice, ConstantTimeEq};

use super::{FieldShareKey, GlobalFieldKey};
use crate::{
    algebra::field::{FieldElement, FieldExtension, SubfieldElement},
    errors::PrimitiveError,
    izip_eq,
    random::{CryptoRngCore, Random, RandomWith},
    sharing::{
        authenticated::NParties,
        unauthenticated::AdditiveShares,
        AddPlaintext,
        IsFirstPeer,
        Reconstructible,
        VerifiableWith,
    },
    types::{CollectAll, ConditionallySelectable, PeerIndex},
    utils::IntoExactSizeIterator,
};
#[derive(Debug, Copy, Clone, Default, PartialEq, Eq, Serialize, Deserialize)]
#[serde(bound = "F: FieldExtension")]
pub struct OpenFieldShare<F: FieldExtension> {
    pub(crate) value: SubfieldElement<F>,
    pub(crate) mac: FieldElement<F>,
}

impl<F: FieldExtension> OpenFieldShare<F> {
    pub fn new(value: SubfieldElement<F>, mac: FieldElement<F>) -> Self {
        Self { value, mac }
    }

    pub fn get_value(&self) -> &SubfieldElement<F> {
        &self.value
    }

    pub fn get_mac(&self) -> &FieldElement<F> {
        &self.mac
    }
}

/// Authenticated share <x_i> of secret shared <x> held by `P_i` (this party).
///
/// They are composed of:
/// - `x_i`, the unauthenticated share value (s.t. `x = Σ x_i`)
/// - `{MAC(x_i)_j} ∀j∈[1..n]∖{i}`, the MACs of `x_i` for each of the other n-1 parties.
/// - `{β_ij} ∀j∈[1..n]∖{i}` and `{α_ij} ∀j∈[1..n]∖{i}`, the (local and global) keys tied to the
///   values&MACs of the other n-1 parties.
///
/// The authenticated shares fulfill this relation:
///
/// ```MAC(x_i)_j = α_ji · x_i + β_ji  ∀i∈[1..n]  ∀j∈[1..n]∖{i}```
///     
/// where `β_ji` and `α_ji` are the (local and global) keys of x_i held by P_j.
#[derive(Debug, Clone, Default, PartialEq, Eq, Serialize, Deserialize)]
#[serde(bound = "F: FieldExtension")]
pub struct FieldShare<F>
where
    F: FieldExtension,
{
    pub(crate) value: SubfieldElement<F>,     // x_i
    pub(crate) macs: Box<[FieldElement<F>]>,  // {MAC(x_i)_j} ∀j∈[1..n]∖{i}
    pub(crate) keys: Box<[FieldShareKey<F>]>, // {(α_ij, β_ij)} ∀j∈[1..n]∖{i}
}

impl<F: FieldExtension> FieldShare<F> {
    pub fn try_new(
        value: SubfieldElement<F>,
        macs: Box<[FieldElement<F>]>,
        keys: Box<[FieldShareKey<F>]>,
    ) -> 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 })
    }

    pub(super) fn new(
        value: SubfieldElement<F>,
        macs: Box<[FieldElement<F>]>,
        keys: Box<[FieldShareKey<F>]>,
    ) -> Self {
        Self { value, macs, keys }
    }

    pub fn zero_from_alphas(alphas: impl ExactSizeIterator<Item = GlobalFieldKey<F>>) -> Self {
        let n_peers = alphas.len();
        FieldShare {
            value: SubfieldElement::zero(),
            macs: vec![FieldElement::<F>::zero(); n_peers].into_boxed_slice(),
            keys: alphas
                .map(|alpha| FieldShareKey::<F>::new(alpha, FieldElement::zero()))
                .collect(),
        }
    }

    #[inline]
    pub fn get_value(&self) -> &SubfieldElement<F> {
        &self.value
    }

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

    #[inline]
    pub fn get_macs(&self) -> &[FieldElement<F>] {
        &self.macs
    }

    #[inline]
    pub fn get_mac(&self, peer_index: PeerIndex) -> Option<&FieldElement<F>> {
        self.macs.get(peer_index)
    }

    #[inline]
    pub fn get_keys(&self) -> &[FieldShareKey<F>] {
        &self.keys
    }

    #[inline]
    pub fn get_key(&self, peer_index: PeerIndex) -> Option<&FieldShareKey<F>> {
        self.keys.get(peer_index)
    }

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

    #[inline]
    pub fn n_parties(&self) -> usize {
        self.macs.len() + 1 // +1 for the local share
    }
}

// --------------------
// |   Verification   |
// --------------------
impl<F: FieldExtension> VerifiableWith for FieldShare<F> {
    type VerificationData = ();

    /// Check the MACs of the share received from another peer.
    #[inline]
    fn verify_from_peer_with(
        &self,
        open_share: &OpenFieldShare<F>,
        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: &[OpenFieldShare<F>],
        _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<F: FieldExtension> Reconstructible for FieldShare<F> {
    type Opening = OpenFieldShare<F>;
    type Secret = SubfieldElement<F>;

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

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

    /// Reconstruct a secret from openings coming from all other parties.
    fn reconstruct(&self, openings: &[OpenFieldShare<F>]) -> 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<F: FieldExtension>(
    all_unauth_shares: &[SubfieldElement<F>],
    all_keys: &[Box<[FieldShareKey<F>]>],
) -> Vec<Box<[FieldElement<F>]>> {
    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<F: FieldExtension> Random for FieldShare<F> {
    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: usize,
    ) -> Container {
        let all_unauth_shares: Vec<_> = SubfieldElement::random_n(&mut rng, n_parties);
        let all_keys = (0..n_parties)
            .map(|_| FieldShareKey::<F>::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)| FieldShare { value, macs, keys })
            .collect()
    }
}

impl<F: FieldExtension> RandomWith<NParties> for FieldShare<F> {
    /// 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 {
        FieldShare {
            value: SubfieldElement::random(&mut rng),
            macs: FieldElement::<F>::random_n(&mut rng, n_parties - 1),
            keys: FieldShareKey::<F>::random_n(&mut rng, n_parties - 1),
        }
    }
}

impl<F: FieldExtension> RandomWith<(NParties, SubfieldElement<F>)> for FieldShare<F> {
    /// Generate a random field share, with Macs and keys for all the other parties.
    fn random_with(
        mut rng: impl CryptoRngCore,
        n_parties_and_value: (NParties, SubfieldElement<F>),
    ) -> Self {
        let (n_parties, value) = n_parties_and_value;
        FieldShare {
            value,
            macs: FieldElement::<F>::random_n(&mut rng, n_parties - 1),
            keys: FieldShareKey::<F>::random_n(&mut rng, n_parties - 1),
        }
    }
}

impl<F: FieldExtension> RandomWith<SubfieldElement<F>> for FieldShare<F> {
    fn random_with(_rng: impl CryptoRngCore, _data: SubfieldElement<F>) -> 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: usize,
        value: SubfieldElement<F>,
    ) -> Container {
        let all_unauth_shares = value.to_additive_shares(n_parties, &mut rng);
        let all_keys = (0..n_parties)
            .map(|_| FieldShareKey::<F>::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)| FieldShare { value, macs, keys })
            .collect()
    }
}

impl<F: FieldExtension> RandomWith<Vec<GlobalFieldKey<F>>> for FieldShare<F> {
    /// Generate a random field share from its global keys (alphas).
    fn random_with(mut rng: impl CryptoRngCore, alphas: Vec<GlobalFieldKey<F>>) -> Self {
        let n_other_parties = alphas.len();
        FieldShare {
            value: SubfieldElement::random(&mut rng),
            macs: FieldElement::<F>::random_n(&mut rng, n_other_parties),
            keys: FieldShareKey::<F>::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<GlobalFieldKey<F>>>,
    ) -> Container {
        let all_alphas = all_alphas.into_iter();
        let all_unauth_shares: Vec<_> = SubfieldElement::random_n(&mut rng, all_alphas.len());
        let all_keys = all_alphas
            .into_iter()
            .map(|my_alphas| FieldShareKey::<F>::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)| FieldShare { value, macs, keys })
            .collect()
    }
}

impl<F: FieldExtension> RandomWith<(SubfieldElement<F>, Vec<GlobalFieldKey<F>>)> for FieldShare<F> {
    /// Generate a random field share from its global keys (alphas) and its share
    fn random_with(
        mut rng: impl CryptoRngCore,
        value_alphas: (SubfieldElement<F>, Vec<GlobalFieldKey<F>>),
    ) -> Self {
        let (value, alphas) = value_alphas;
        let n_other_parties = alphas.len();
        FieldShare {
            value,
            macs: FieldElement::<F>::random_n(&mut rng, n_other_parties),
            keys: FieldShareKey::<F>::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 IntoExactSizeIterator<
            Item = (SubfieldElement<F>, Vec<GlobalFieldKey<F>>),
        >,
    ) -> Container {
        let (all_unauth_shares, all_keys): (Vec<_>, Vec<_>) = unauth_shares_and_alphas
            .into_iter()
            .map(|(value, my_alphas)| {
                (
                    value,
                    FieldShareKey::<F>::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)| FieldShare { value, macs, keys })
            .collect()
    }
}

impl<F: FieldExtension> RandomWith<(SubfieldElement<F>, Vec<Vec<GlobalFieldKey<F>>>)>
    for FieldShare<F>
{
    fn random_with(
        _source: impl CryptoRngCore,
        _data: (SubfieldElement<F>, Vec<Vec<GlobalFieldKey<F>>>),
    ) -> Self {
        unimplemented!(
            "Cannot discern what alpha/global key 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, all_alphas): (SubfieldElement<F>, Vec<Vec<GlobalFieldKey<F>>>),
    ) -> Container {
        if n_parties != all_alphas.len() {
            panic!("n_parties does not match the number of alphas provided");
        }

        let all_unauth_shares = secret_value.to_additive_shares(all_alphas.len(), &mut rng);
        let all_keys = all_alphas
            .into_iter()
            .map(|my_alphas| FieldShareKey::<F>::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)| FieldShare { value, macs, keys })
            .collect()
    }
}

// --------------
// | Arithmetic |
// --------------

// === Addition === //

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

    #[inline]
    fn add(mut self, other: &'a FieldShare<F>) -> Self::Output {
        self.value += &other.value;
        izip_eq!(&mut self.macs, &other.macs).for_each(|(mac_i, mac_j)| *mac_i += mac_j);
        izip_eq!(&mut self.keys, &other.keys).for_each(|(key_i, key_j)| *key_i += key_j);
        self
    }
}

#[macros::op_variants(owned)]
impl<'a, F: FieldExtension> AddAssign<&'a FieldShare<F>> for FieldShare<F> {
    #[inline]
    fn add_assign(&mut self, other: &'a FieldShare<F>) {
        self.value += &other.value;
        izip_eq!(&mut self.macs, &other.macs).for_each(|(mac_i, mac_j)| *mac_i += mac_j);
        izip_eq!(&mut self.keys, &other.keys).for_each(|(key_i, key_j)| *key_i += key_j);
    }
}

// === Subtraction === //

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

    #[inline]
    fn sub(mut self, other: &'a FieldShare<F>) -> Self::Output {
        self.value -= &other.value;
        izip_eq!(&mut self.macs, &other.macs).for_each(|(mac_i, mac_j)| *mac_i -= mac_j);
        izip_eq!(&mut self.keys, &other.keys).for_each(|(key_i, key_j)| *key_i -= key_j);
        self
    }
}

#[macros::op_variants(owned)]
impl<'a, F: FieldExtension> SubAssign<&'a FieldShare<F>> for FieldShare<F> {
    #[inline]
    fn sub_assign(&mut self, other: &'a FieldShare<F>) {
        self.value -= &other.value;
        izip_eq!(&mut self.keys, &other.keys).for_each(|(key_i, key_j)| *key_i -= key_j);
        izip_eq!(&mut self.macs, &other.macs).for_each(|(mac_i, mac_j)| *mac_i -= mac_j);
    }
}

// === Constant multiplication === //

#[macros::op_variants(owned, borrowed, flipped)]
impl<'a, F: FieldExtension> Mul<&'a SubfieldElement<F>> for FieldShare<F> {
    type Output = FieldShare<F>;

    #[inline]
    fn mul(mut self, other: &'a SubfieldElement<F>) -> FieldShare<F> {
        self.value *= other;
        izip_eq!(&mut self.keys).for_each(|key_i| *key_i *= other);
        izip_eq!(&mut self.macs).for_each(|mac_i| *mac_i *= other);
        self
    }
}

// === MulAssign === //

#[macros::op_variants(owned)]
impl<'a, F: FieldExtension> MulAssign<&'a SubfieldElement<F>> for FieldShare<F> {
    #[inline]
    fn mul_assign(&mut self, other: &'a SubfieldElement<F>) {
        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<F: FieldExtension> Neg for FieldShare<F> {
    type Output = FieldShare<F>;

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

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

impl<F: FieldExtension> AddPlaintext for FieldShare<F> {
    type AssociatedInformation = IsFirstPeer;
    /// Adds a plaintext 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, plaintext: &SubfieldElement<F>, is_peer_zero: IsFirstPeer) -> Self {
        let result = self.clone();
        result.add_plaintext_owned(plaintext, is_peer_zero)
    }

    /// Adds a plaintext 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,
        plaintext: &SubfieldElement<F>,
        is_peer_zero: IsFirstPeer,
    ) -> Self {
        if is_peer_zero {
            self.value += plaintext;
        } else {
            let key0 = self.keys.get_mut(0).expect("Missing key 0");
            key0.beta -= *key0.alpha * plaintext;
        }
        self
    }
}

// ---------------------------------------
// |  Constant time Selection / Equality |
// ---------------------------------------

impl<F: FieldExtension> ConstantTimeEq for FieldShare<F> {
    #[inline]
    fn ct_eq(&self, other: &Self) -> Choice {
        self.value.ct_eq(&other.value) & self.keys.ct_eq(&other.keys) & self.macs.ct_eq(&other.macs)
    }
}

impl<F: FieldExtension> ConditionallySelectable for FieldShare<F> {
    #[inline]
    fn conditional_select(a: &Self, b: &Self, choice: Choice) -> Self {
        FieldShare {
            value: SubfieldElement::conditional_select(&a.value, &b.value, choice),
            macs: izip_eq!(&a.macs, &b.macs)
                .map(|(a_mac, b_mac)| FieldElement::conditional_select(a_mac, b_mac, choice))
                .collect(),
            keys: izip_eq!(&a.keys, &b.keys)
                .map(|(a_key, b_key)| FieldShareKey::conditional_select(a_key, b_key, choice))
                .collect(),
        }
    }
}

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

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

    // TODO: Generalize once PairwiseAuthenticatedShare trait is implemented.

    //////////////////////////////////////////////////
    // CHANGE ONLY THESE TO TEST ANOTHER SHARE TYPE //
    pub type Value = Scalar<C>;
    pub type Constant = Scalar<C>;
    pub type Share = ScalarShare<C>;
    pub type GlobalKey = GlobalScalarKey<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);
        }
        let _ = Share::reconstruct_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 = &Constant::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)));
    }
}