primitives/sharing/authenticated/batched/

field_shares.rs

use std::{
    fmt::Debug,
    iter::Sum as IterSum,
    ops::{Add, AddAssign, Mul, MulAssign, Neg, Sub, SubAssign},
};

use itertools::{enumerate, izip, Itertools};
use num_traits::Zero;
use rayon::prelude::IntoParallelIterator;
use serde::{Deserialize, Serialize};
use subtle::{Choice, ConstantTimeEq};
use typenum::{PartialDiv, Prod, Sum, U1, U2, U3};
use wincode::{SchemaRead, SchemaWrite};

use super::FieldShareKeys;
use crate::{
    algebra::{
        field::{FieldElement, FieldExtension, SubfieldElement},
        ops::transpose::transpose,
    },
    errors::PrimitiveError,
    izip_eq,
    random::{CryptoRngCore, Random, RandomWith},
    sharing::{
        authenticated::NParties,
        unauthenticated::AdditiveShares,
        FieldShare,
        FieldShareKey,
        GlobalFieldKey,
        Reconstructible,
        VerifiableWith,
    },
    types::{
        heap_array::{FieldElements, SubfieldElements},
        identifiers::PeerIndex,
        Batched,
        CollectAll,
        ConditionallySelectable,
        HeapArray,
        Positive,
    },
    utils::IntoExactSizeIterator,
};

#[derive(Clone, Default, PartialEq, Eq, Serialize, Deserialize, SchemaRead, SchemaWrite)]
#[serde(bound = "F: FieldExtension, M: Positive")]
#[repr(C)]
pub struct OpenFieldShares<F: FieldExtension, M: Positive> {
    pub(crate) value: SubfieldElements<F, M>,
    pub(crate) mac: FieldElements<F, M>,
}

impl<F: FieldExtension, M: Positive> OpenFieldShares<F, M> {
    pub fn new(value: SubfieldElements<F, M>, mac: FieldElements<F, M>) -> Self {
        Self { value, mac }
    }

    pub fn get_value(&self) -> &SubfieldElements<F, M> {
        &self.value
    }

    pub fn get_mac(&self) -> &FieldElements<F, M> {
        &self.mac
    }
}

impl<T: FieldExtension, M: Positive> Debug for OpenFieldShares<T, M> {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        f.debug_struct(format!("OpenFieldShares<{}>", M::USIZE).as_str())
            .field("value", &self.value)
            .field("mac", &self.mac)
            .finish()
    }
}

/// Authenticated share batch <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
///   value&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, SchemaRead, SchemaWrite)]
#[serde(bound = "F: FieldExtension, M: Positive")]
#[repr(C)]
pub struct FieldShares<F: FieldExtension, M: Positive> {
    /// x_i
    pub(crate) value: SubfieldElements<F, M>,
    /// {MAC_1(x_i), ..., MAC_{i-1}(x_i), MAC_{i+1}(x_i), ..., MAC_n(x_i)}
    pub(crate) macs: Box<[FieldElements<F, M>]>,
    /// {(α_i1, β_i1), ..., (α_i{i-1}, β_i{i-1}), (α_i{i+1}, β_i{i+1}), ..., (α_in, β_in)}
    pub(crate) keys: Box<[FieldShareKeys<F, M>]>,
}

impl<F: FieldExtension, M: Positive> FieldShares<F, M> {
    pub fn try_new(
        value: SubfieldElements<F, M>,
        macs: Box<[FieldElements<F, M>]>,
        keys: Box<[FieldShareKeys<F, M>]>,
    ) -> 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: SubfieldElements<F, M>,
        macs: Box<[FieldElements<F, M>]>,
        keys: Box<[FieldShareKeys<F, M>]>,
    ) -> Self {
        Self { value, macs, keys }
    }

    pub fn get_value(&self) -> &SubfieldElements<F, M> {
        &self.value
    }

    pub fn get_value_mut(&mut self) -> &mut SubfieldElements<F, M> {
        &mut self.value
    }

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

    pub fn get_keys(&self) -> &[FieldShareKeys<F, M>] {
        &self.keys
    }

    pub fn get_keys_mut(&mut self) -> &mut [FieldShareKeys<F, M>] {
        &mut self.keys
    }

    pub fn get_key(&self, peer: PeerIndex) -> Option<&FieldShareKeys<F, M>> {
        self.keys.get(peer)
    }

    pub fn get_macs(&self) -> &[FieldElements<F, M>] {
        &self.macs
    }

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

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

    pub fn n_parties(&self) -> usize {
        self.get_macs().len() + 1 // +1 for the local share
    }

    /// Number of distant peers (excludes the local party).
    #[inline]
    pub fn n_distant_peers(&self) -> usize {
        self.macs.len()
    }

    #[inline]
    pub fn value_at(&self, t: usize) -> SubfieldElement<F> {
        self.value[t]
    }

    #[inline]
    pub fn mac_at(&self, peer: usize, t: usize) -> FieldElement<F> {
        self.macs[peer][t]
    }

    #[inline]
    pub fn key_beta_at(&self, peer: usize, t: usize) -> FieldElement<F> {
        self.keys[peer].betas[t]
    }

    #[inline]
    pub fn sum_macs_at(&self, t: usize) -> FieldElement<F> {
        self.macs
            .iter()
            .fold(FieldElement::zero(), |acc, mac| acc + mac[t])
    }

    #[inline]
    pub fn sum_key_betas_at(&self, t: usize) -> FieldElement<F> {
        self.keys
            .iter()
            .fold(FieldElement::zero(), |acc, key| acc + key.betas[t])
    }

    pub fn iter(&self) -> FieldSharesIterator<F, M> {
        self.into_iter()
    }

    pub fn len(&self) -> usize {
        self.value.len()
    }

    pub fn is_empty(&self) -> bool {
        self.len() == 0
    }

    /// Swaps elements at positions `i` and `j` in-place across
    /// value, macs, and key betas arrays.
    pub fn swap(&mut self, i: usize, j: usize) {
        self.value.swap(i, j);
        for mac in self.macs.iter_mut() {
            mac.swap(i, j);
        }
        for key in self.keys.iter_mut() {
            key.betas.swap(i, j);
        }
    }

    /// Adds element at index `src` into element at index `dst` in-place:
    /// `self[dst] += self[src]`
    pub fn accumulate(&mut self, dst: usize, src: usize) {
        let src_val = self.value[src];
        self.value[dst] += src_val;
        for mac in self.macs.iter_mut() {
            let src_mac = mac[src];
            mac[dst] += src_mac;
        }
        for key in self.keys.iter_mut() {
            let src_beta = key.betas[src];
            key.betas[dst] += src_beta;
        }
    }

    /// Accumulates `other[src] * scalar` into `self[dst]`:
    /// `self[dst] += other[src] * scalar`
    pub fn accumulate_scaled_from(
        &mut self,
        dst: usize,
        other: &Self,
        src: usize,
        scalar: &SubfieldElement<F>,
    ) {
        self.value[dst] += other.value[src] * *scalar;
        for (mac, other_mac) in self.macs.iter_mut().zip(other.macs.iter()) {
            mac[dst] += other_mac[src] * *scalar;
        }
        for (key, other_key) in self.keys.iter_mut().zip(other.keys.iter()) {
            key.betas[dst] += other_key.betas[src] * *scalar;
        }
    }

    /// Returns a single FieldShare at the given index.
    pub fn get_share(&self, index: usize) -> FieldShare<F> {
        let value = self.value[index];
        let macs: Box<[_]> = self.macs.iter().map(|m| m[index]).collect();
        let keys: Box<[_]> = self
            .keys
            .iter()
            .map(|k| FieldShareKey::new(k.get_alpha(), k.betas[index]))
            .collect();
        FieldShare::new(value, macs, keys)
    }

    /// Selects elements at the given indices into a new FieldShares batch.
    pub fn select<OutM: Positive>(&self, indices: &[usize]) -> FieldShares<F, OutM> {
        let value = indices.iter().map(|&i| self.value[i]).collect();
        let macs: Box<[FieldElements<F, OutM>]> = self
            .macs
            .iter()
            .map(|mac| indices.iter().map(|&i| mac[i]).collect())
            .collect::<Vec<_>>()
            .into();
        let keys: Box<[FieldShareKeys<F, OutM>]> = self
            .keys
            .iter()
            .map(|key| {
                FieldShareKeys::new(
                    key.get_alpha(),
                    indices.iter().map(|&i| key.betas[i]).collect(),
                )
            })
            .collect::<Vec<_>>()
            .into();
        FieldShares::new(value, macs, keys)
    }
}

// --------------------
// |   Verification   |
// --------------------
impl<F: FieldExtension, M: Positive> VerifiableWith for FieldShares<F, M> {
    type VerificationData = ();
    /// Check the MACs of the share received from another peer.
    #[inline]
    fn verify_from_peer_with(
        &self,
        open_share: &OpenFieldShares<F, M>,
        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: &[OpenFieldShares<F, M>],
        _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, M: Positive> Reconstructible for FieldShares<F, M> {
    type Opening = OpenFieldShares<F, M>;
    type Secret = SubfieldElements<F, M>;

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

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

    /// Reconstruct a secret from openings coming from all other parties.
    fn reconstruct(
        &self,
        openings: &[OpenFieldShares<F, M>],
    ) -> 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()
            }))
    }
}

impl<F: FieldExtension, M: Positive, N: Positive> Reconstructible
    for HeapArray<FieldShares<F, M>, N>
{
    type Opening = HeapArray<OpenFieldShares<F, M>, N>;
    type Secret = HeapArray<SubfieldElements<F, M>, N>;

    /// Open the share towards another peer.
    fn open_to(&self, for_peer: PeerIndex) -> Result<Self::Opening, PrimitiveError> {
        self.into_iter()
            .map(|s| s.open_to(for_peer))
            .collect::<Result<_, _>>()
    }

    /// Open the share towards all other peers.
    fn open_to_all_others(&self) -> impl ExactSizeIterator<Item = Self::Opening> {
        let openings = self
            .into_iter()
            .map(|s| s.open_to_all_others().collect::<Vec<_>>())
            .collect::<Vec<Vec<OpenFieldShares<_, _>>>>();
        transpose(openings)
            .into_iter()
            .map(|o| o.try_into().unwrap())
    }

    /// Reconstruct a secret from openings coming from all other parties.
    fn reconstruct(&self, openings: &[Self::Opening]) -> Result<Self::Secret, PrimitiveError> {
        // Iterate over all the i-th elements of each entry of openings
        self.iter()
            .enumerate()
            .map(|(i, share)| {
                let my_openings: Vec<_> = openings
                    .iter()
                    .map(|opening: &HeapArray<OpenFieldShares<F, M>, N>| opening.get(i).cloned())
                    .collect::<Option<Vec<_>>>()
                    .ok_or_else(|| {
                        PrimitiveError::InvalidParameters(
                            "Opening is missing for some share.".to_string(),
                        )
                    })?;
                share.reconstruct(my_openings.as_slice())
            })
            .collect::<Result<Self::Secret, PrimitiveError>>()
    }
}

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

fn compute_macs<F: FieldExtension, M: Positive>(
    all_unauth_shares: &[SubfieldElements<F, M>],
    all_keys: &[Box<[FieldShareKeys<F, M>]>],
) -> Vec<Box<[FieldElements<F, M>]>> {
    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, M: Positive> Random for FieldShares<F, M> {
    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 a random field share, with Macs and keys for all the other parties.
    fn random_n<Container: FromIterator<Self>>(
        mut rng: impl CryptoRngCore,
        n_parties: NParties,
    ) -> Container {
        let all_unauth_shares: Vec<_> = SubfieldElements::random_n(&mut rng, n_parties);
        let all_keys = (0..n_parties)
            .map(|_| FieldShareKeys::<F, M>::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)| FieldShares::new(value, macs, keys))
            .collect()
    }
}

impl<F: FieldExtension, M: Positive> RandomWith<NParties> for FieldShares<F, M> {
    /// 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 {
        FieldShares::new(
            SubfieldElements::<F, M>::random(&mut rng),
            FieldElements::<F, M>::random_n(&mut rng, n_parties - 1),
            FieldShareKeys::<F, M>::random_n(&mut rng, n_parties - 1),
        )
    }
}

impl<F: FieldExtension, M: Positive> RandomWith<(NParties, SubfieldElements<F, M>)>
    for FieldShares<F, M>
{
    /// 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, SubfieldElements<F, M>),
    ) -> Self {
        let (n_parties, value) = n_parties_value;
        FieldShares::new(
            value,
            FieldElements::<F, M>::random_n(&mut rng, n_parties - 1),
            FieldShareKeys::<F, M>::random_n(&mut rng, n_parties - 1),
        )
    }
}

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

    /// Generate an authenticated share given for each peer given its additve share
    ///  with consistent MACs and keys across all peers.
    fn random_n_with_each<Container: FromIterator<Self>>(
        mut rng: impl CryptoRngCore,
        unauth_shares: impl IntoExactSizeIterator<Item = SubfieldElements<F, M>>,
    ) -> Container {
        let all_unauth_shares = unauth_shares.into_iter().collect::<Vec<_>>();
        let n_parties = all_unauth_shares.len();
        let all_keys = (0..n_parties)
            .map(|_| FieldShareKeys::<F, M>::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)| FieldShares::new(value, macs, keys))
            .collect()
    }
}

impl<F: FieldExtension, M: Positive> RandomWith<Vec<GlobalFieldKey<F>>> for FieldShares<F, M> {
    /// 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();
        FieldShares::new(
            SubfieldElements::random(&mut rng),
            FieldElements::<F, M>::random_n(&mut rng, n_other_parties),
            FieldShareKeys::<F, M>::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<_> = SubfieldElements::random_n(&mut rng, all_alphas.len());
        let all_keys = all_alphas
            .into_iter()
            .map(|my_alphas| FieldShareKeys::<F, M>::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)| FieldShares::new(value, macs, keys))
            .collect()
    }
}

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

impl<F: FieldExtension, M: Positive>
    RandomWith<(SubfieldElements<F, M>, Vec<Vec<GlobalFieldKey<F>>>)> for FieldShares<F, M>
{
    fn random_with(
        _rng: impl CryptoRngCore,
        _data: (SubfieldElements<F, M>, 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_and_alphas: (SubfieldElements<F, M>, Vec<Vec<GlobalFieldKey<F>>>),
    ) -> 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| FieldShareKeys::<F, M>::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)| FieldShares::new(value, macs, keys))
            .collect()
    }
}

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

// === Addition === //

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

    #[inline]
    fn add(mut self, other: &'a FieldShares<F, M>) -> 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, M: Positive> AddAssign<&'a FieldShares<F, M>> for FieldShares<F, M> {
    #[inline]
    fn add_assign(&mut self, other: &'a FieldShares<F, M>) {
        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, M: Positive> Sub<&'a FieldShares<F, M>> for FieldShares<F, M> {
    type Output = FieldShares<F, M>;

    #[inline]
    fn sub(mut self, other: &'a FieldShares<F, M>) -> 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, M: Positive> SubAssign<&'a FieldShares<F, M>> for FieldShares<F, M> {
    #[inline]
    fn sub_assign(&mut self, other: &'a FieldShares<F, M>) {
        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);
    }
}

// === Value multiplication === //

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

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

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

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

// === MulAssign === //

#[macros::op_variants(owned)]
impl<'a, F: FieldExtension, M: Positive> MulAssign<&'a SubfieldElement<F>> for FieldShares<F, M> {
    #[inline]
    fn mul_assign(&mut self, other: &'a SubfieldElement<F>) {
        self.value *= other;
        izip_eq!(&mut self.macs).for_each(|mac_i| *mac_i *= other);
        izip_eq!(&mut self.keys).for_each(|key_i| *key_i *= other);
    }
}

#[macros::op_variants(owned)]
impl<'a, F: FieldExtension, M: Positive> MulAssign<&'a SubfieldElements<F, M>>
    for FieldShares<F, M>
{
    #[inline]
    fn mul_assign(&mut self, other: &'a SubfieldElements<F, M>) {
        self.value *= other;
        izip_eq!(&mut self.macs).for_each(|mac_i| *mac_i *= other);
        izip_eq!(&mut self.keys).for_each(|key_i| *key_i *= other);
    }
}

// === Negation === //

#[macros::op_variants(borrowed)]
impl<F: FieldExtension, M: Positive> Neg for FieldShares<F, M> {
    type Output = FieldShares<F, M>;

    #[inline]
    fn neg(self) -> Self::Output {
        FieldShares {
            value: -self.value,
            macs: izip_eq!(&self.macs).map(|mac_i| -mac_i).collect(),
            keys: izip_eq!(&self.keys).map(|key_i| -key_i).collect(),
        }
    }
}

// === Sum === //

impl<F: FieldExtension, M: Positive> IterSum for FieldShares<F, M> {
    fn sum<I: Iterator<Item = Self>>(mut iter: I) -> Self {
        let first = iter.next().unwrap_or_default();
        iter.fold(first, |acc, x| acc + x)
    }
}

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

impl<F: FieldExtension, M: Positive> FieldShares<F, M> {
    /// 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]
    pub fn add_secret_owned(
        mut self,
        constant: &SubfieldElements<F, M>,
        is_peer_zero: bool,
    ) -> Self {
        if is_peer_zero {
            self.value += constant;
        } else {
            let key0 = self.keys.get_mut(0).expect("Missing key 0");
            key0.betas -= constant.clone() * *key0.alpha;
        }
        self
    }

    /// 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]
    pub fn add_secret(&self, constant: &SubfieldElements<F, M>, is_peer_zero: bool) -> Self {
        let result = self.clone();
        result.add_secret_owned(constant, is_peer_zero)
    }

    /// Subtracts a public constant batch from the secret shared batch, updating the keys
    /// accordingly. A designated peer (P_0) will modify its value, while the other peers will
    /// update their keys.
    #[inline]
    pub fn sub_constant_array_owned(
        mut self,
        arr: &SubfieldElements<F, M>,
        is_peer_zero: bool,
    ) -> Self {
        if is_peer_zero {
            self.value -= arr;
        } else {
            let key0 = self.keys.get_mut(0).expect("Missing key 0");
            let alpha = *key0.alpha;
            izip_eq!(&mut key0.betas, arr).for_each(|(beta, val)| *beta += alpha * val);
        }
        self
    }
}

// === Constant Time Selection / Equality === //

impl<F: FieldExtension, M: Positive> ConditionallySelectable for FieldShares<F, M> {
    #[inline]
    fn conditional_select(a: &Self, b: &Self, choice: Choice) -> Self {
        FieldShares {
            value: HeapArray::conditional_select(&a.value, &b.value, choice),
            macs: izip_eq!(&a.macs, &b.macs)
                .map(|(a_mac, b_mac)| HeapArray::conditional_select(a_mac, b_mac, choice))
                .collect::<Vec<_>>()
                .into(),
            keys: izip_eq!(&a.keys, &b.keys)
                .map(|(a_key, b_key)| FieldShareKeys::conditional_select(a_key, b_key, choice))
                .collect::<Vec<_>>()
                .into(),
        }
    }
}

impl<F: FieldExtension, M: Positive> ConstantTimeEq for FieldShares<F, M> {
    #[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)
    }
}

// === Other Ops === //

impl<F: FieldExtension, M: Positive> FieldShares<F, M> {
    /// Compute the dot product of the share value with another share.
    pub fn dot_product(&self, other: &SubfieldElements<F, M>) -> FieldShare<F> {
        FieldShare {
            value: izip_eq!(&self.value, other)
                .map(|(value_i, other_i)| *value_i * other_i)
                .sum(),
            macs: izip_eq!(&self.macs)
                .map(|mac_i| {
                    izip_eq!(mac_i, other)
                        .map(|(mac_ij, other_i)| *mac_ij * other_i)
                        .sum()
                })
                .collect(),
            keys: izip_eq!(&self.keys)
                .map(|key_i| {
                    let beta = izip_eq!(&key_i.betas, other)
                        .map(|(key_ij, other_i)| key_ij * other_i)
                        .sum();
                    FieldShareKey {
                        alpha: key_i.alpha.clone(),
                        beta,
                    }
                })
                .collect(),
        }
    }
}

// -----------------------
// |   Split and Merge   |
// -----------------------

impl<F: FieldExtension, M: Positive> FieldShares<F, M> {
    // Split the shares into two sets of shares with M1 and M2 shares respectively.
    pub fn split<M1, M2>(self) -> (FieldShares<F, M1>, FieldShares<F, M2>)
    where
        M1: Positive,
        M2: Positive + Add<M1, Output = M>,
    {
        let FieldShares { value, macs, keys } = self;

        let (value1, value2) = value.split::<M1, M2>();
        let (macs1, macs2): (Vec<_>, Vec<_>) = macs
            .into_vec()
            .into_iter()
            .map(|mac| mac.split::<M1, M2>())
            .collect();

        let (keys1, keys2): (Vec<_>, Vec<_>) = keys
            .into_vec()
            .into_iter()
            .map(|key| key.split::<M1, M2>())
            .collect();

        (
            FieldShares::try_new(value1, macs1.into(), keys1.into()).unwrap(),
            FieldShares::try_new(value2, macs2.into(), keys2.into()).unwrap(),
        )
    }

    // Split the shares into two sets of shares with M/2 shares each.
    pub fn split_halves<MDiv2>(self) -> (FieldShares<F, MDiv2>, FieldShares<F, MDiv2>)
    where
        MDiv2: Positive + Mul<U2, Output = M>,
    {
        let FieldShares { value, macs, keys } = self;

        let (value1, value2) = value.split_halves::<MDiv2>();
        let (macs1, macs2): (Vec<_>, Vec<_>) = macs
            .into_vec()
            .into_iter()
            .map(|mac| mac.split_halves::<MDiv2>())
            .collect();

        let (keys1, keys2): (Vec<_>, Vec<_>) = keys
            .into_vec()
            .into_iter()
            .map(|key| key.split_halves::<MDiv2>())
            .collect();

        (
            FieldShares::try_new(value1, macs1.into(), keys1.into()).unwrap(),
            FieldShares::try_new(value2, macs2.into(), keys2.into()).unwrap(),
        )
    }

    // Merge two sets of shares with M/2 shares each into a single set of shares with M shares.
    pub fn merge_halves(this: Self, other: Self) -> FieldShares<F, Prod<M, U2>>
    where
        M: Positive + Mul<U2, Output: Positive>,
    {
        let FieldShares { value, macs, keys } = this;
        let FieldShares {
            value: other_value,
            macs: other_macs,
            keys: other_keys,
        } = other;

        let value = SubfieldElements::merge_halves(value, other_value);
        let macs = izip_eq!(macs, other_macs)
            .map(|(mac, other_mac)| FieldElements::merge_halves(mac, other_mac))
            .collect::<Vec<_>>();
        let keys = izip_eq!(keys, other_keys)
            .map(|(key, other_key)| FieldShareKeys::merge_halves(key, other_key))
            .collect::<Vec<_>>();

        FieldShares::try_new(value, macs.into(), keys.into()).unwrap()
    }

    // Split the shares into three sets of shares with M1, M2 and M3 shares respectively.
    pub fn split3<M1, M2, M3>(self) -> (FieldShares<F, M1>, FieldShares<F, M2>, FieldShares<F, M3>)
    where
        M1: Positive,
        M2: Positive + Add<M1>,
        M3: Positive + Add<Sum<M2, M1>, Output = M>,
    {
        let FieldShares { value, macs, keys } = self;

        let (value1, value2, value3) = value.split3::<M1, M2, M3>();
        let (macs1, macs2, macs3): (Vec<_>, Vec<_>, Vec<_>) = macs
            .into_vec()
            .into_iter()
            .map(|mac| mac.split3::<M1, M2, M3>())
            .multiunzip();

        let (keys1, keys2, keys3): (Vec<_>, Vec<_>, Vec<_>) = keys
            .into_vec()
            .into_iter()
            .map(|key| key.split3::<M1, M2, M3>())
            .multiunzip();

        (
            FieldShares::try_new(value1, macs1.into(), keys1.into()).unwrap(),
            FieldShares::try_new(value2, macs2.into(), keys2.into()).unwrap(),
            FieldShares::try_new(value3, macs3.into(), keys3.into()).unwrap(),
        )
    }

    // Split the shares into three sets of shares with M/3 shares each.
    pub fn split_thirds<MDiv3>(
        self,
    ) -> (
        FieldShares<F, MDiv3>,
        FieldShares<F, MDiv3>,
        FieldShares<F, MDiv3>,
    )
    where
        MDiv3: Positive + Mul<U3, Output = M>,
    {
        let FieldShares { value, macs, keys } = self;

        let (value1, value2, value3) = value.split_thirds::<MDiv3>();
        let (macs1, macs2, macs3): (Vec<_>, Vec<_>, Vec<_>) = macs
            .into_vec()
            .into_iter()
            .map(|mac| mac.split_thirds::<MDiv3>())
            .multiunzip();

        let (keys1, keys2, keys3): (Vec<_>, Vec<_>, Vec<_>) = keys
            .into_vec()
            .into_iter()
            .map(|key| key.split_thirds::<MDiv3>())
            .multiunzip();

        (
            FieldShares::try_new(value1, macs1.into(), keys1.into()).unwrap(),
            FieldShares::try_new(value2, macs2.into(), keys2.into()).unwrap(),
            FieldShares::try_new(value3, macs3.into(), keys3.into()).unwrap(),
        )
    }

    // Merge three sets of shares with M/3 shares each into a single set of shares with M shares.
    pub fn merge_thirds(this: Self, other1: Self, other2: Self) -> FieldShares<F, Prod<M, U3>>
    where
        M: Positive + Mul<U3, Output: Positive>,
    {
        let FieldShares {
            value: v1,
            macs: m1,
            keys: k1,
        } = this;
        let FieldShares {
            value: v2,
            macs: m2,
            keys: k2,
        } = other1;
        let FieldShares {
            value: v3,
            macs: m3,
            keys: k3,
        } = other2;

        let value = SubfieldElements::merge_thirds(v1, v2, v3);
        let macs = izip_eq!(m1, m2, m3)
            .map(|(mac1, mac2, mac3)| FieldElements::merge_thirds(mac1, mac2, mac3))
            .collect::<Vec<_>>();
        let keys = izip_eq!(k1, k2, k3)
            .map(|(key1, key2, key3)| FieldShareKeys::merge_thirds(key1, key2, key3))
            .collect::<Vec<_>>();

        FieldShares::try_new(value, macs.into(), keys.into()).unwrap()
    }
}

// ------------------------
// |   Iterate and Cast   |
// ------------------------

// === Single Element === //

impl<F: FieldExtension> From<FieldShare<F>> for FieldShares<F, U1> {
    fn from(share: FieldShare<F>) -> Self {
        FieldShares {
            value: HeapArray::from(share.value),
            macs: share
                .macs
                .into_vec()
                .into_iter()
                .map(HeapArray::from)
                .collect(),
            keys: share
                .keys
                .into_vec()
                .into_iter()
                .map(FieldShareKeys::from)
                .collect(),
        }
    }
}

// === Multiple elements === //

impl<F: FieldExtension, M: Positive> From<HeapArray<FieldShare<F>, M>> for FieldShares<F, M> {
    fn from(shares: HeapArray<FieldShare<F>, M>) -> Self {
        let (values, macs, keys): (Vec<_>, Vec<_>, Vec<_>) = shares
            .into_iter()
            .map(|share| (share.value, share.macs, share.keys))
            .multiunzip();
        let macs = transpose(macs)
            .into_iter()
            .map(HeapArray::from_iter)
            .collect::<Box<[_]>>();
        let keys = transpose(keys)
            .into_iter()
            .map(|peer_keys| {
                let alpha = peer_keys[0].get_alpha();
                let betas = peer_keys
                    .into_iter()
                    .map(|key| {
                        let FieldShareKey { alpha: _, beta } = key;
                        beta
                    })
                    .collect::<HeapArray<_, M>>();
                FieldShareKeys::new(alpha, betas)
            })
            .collect::<Box<[_]>>();

        FieldShares {
            value: HeapArray::from_iter(values),
            macs,
            keys,
        }
    }
}

// === Iterators === //

type SubfieldElementsIterator<F, M> = <SubfieldElements<F, M> as IntoIterator>::IntoIter;
type FieldElementsIterator<F, M> = <FieldElements<F, M> as IntoIterator>::IntoIter;

#[derive(Default, Clone, Debug)]
pub struct FieldSharesIterator<F: FieldExtension, M: Positive> {
    index: usize,

    value: SubfieldElementsIterator<F, M>,
    macs: Vec<FieldElementsIterator<F, M>>,
    betas: Vec<FieldElementsIterator<F, M>>,
    alphas: Vec<GlobalFieldKey<F>>,
}

impl<F: FieldExtension, M: Positive> ExactSizeIterator for FieldSharesIterator<F, M> {
    fn len(&self) -> usize {
        M::to_usize() - self.index
    }
}

impl<F: FieldExtension, M: Positive> Iterator for FieldSharesIterator<F, M> {
    type Item = FieldShare<F>;

    fn next(&mut self) -> Option<Self::Item> {
        if self.index < M::to_usize() {
            let value = self.value.next()?;
            let macs = self
                .macs
                .iter_mut()
                .map(|mac| mac.next())
                .collect::<Option<_>>()?;
            let keys = izip!(&mut self.betas, &self.alphas)
                .map(|(beta, alpha)| {
                    beta.next().map(|beta| FieldShareKey {
                        alpha: alpha.clone(),
                        beta,
                    })
                })
                .collect::<Option<_>>()?;
            self.index += 1;
            Some(FieldShare::new(value, macs, keys))
        } else {
            None
        }
    }
}

impl<F: FieldExtension, M: Positive> IntoIterator for FieldShares<F, M> {
    type Item = FieldShare<F>;
    type IntoIter = FieldSharesIterator<F, M>;

    fn into_iter(self) -> Self::IntoIter {
        let FieldShares { value, macs, keys } = self;
        let value = value.into_iter();
        let macs = macs
            .into_vec()
            .into_iter()
            .map(|mac| mac.into_iter())
            .collect();
        let (betas, alphas): (Vec<_>, Vec<_>) = keys
            .into_vec()
            .into_iter()
            .map(|key| (key.betas.into_iter(), key.alpha))
            .unzip();

        FieldSharesIterator {
            index: 0,
            value,
            macs,
            betas,
            alphas,
        }
    }
}

impl<F: FieldExtension, M: Positive> IntoIterator for &FieldShares<F, M> {
    type Item = FieldShare<F>;
    type IntoIter = FieldSharesIterator<F, M>;

    fn into_iter(self) -> Self::IntoIter {
        let value = self.value.clone().into_iter();
        let macs = self
            .macs
            .iter()
            .map(|mac| mac.clone().into_iter())
            .collect();
        let (betas, alphas): (Vec<_>, Vec<_>) = self
            .keys
            .iter()
            .map(|key| (key.betas.clone().into_iter(), key.alpha.clone()))
            .unzip();

        FieldSharesIterator {
            index: 0,
            value,
            macs,
            betas,
            alphas,
        }
    }
}

impl<F: FieldExtension, N: Positive> FromIterator<FieldShare<F>> for FieldShares<F, N> {
    fn from_iter<T: IntoIterator<Item = FieldShare<F>>>(iter: T) -> Self {
        let (values, macs, keys): (Vec<_>, Vec<_>, Vec<_>) = iter
            .into_iter()
            .map(|share| (share.value, share.macs, share.keys))
            .multiunzip();
        let macs = transpose(macs)
            .into_iter()
            .map(HeapArray::from_iter)
            .collect::<Box<[_]>>();
        let keys = transpose(keys)
            .into_iter()
            .map(|peer_keys| {
                let alpha = peer_keys[0].get_alpha();
                let betas = peer_keys
                    .into_iter()
                    .map(|key| {
                        let FieldShareKey { alpha: _, beta } = key;
                        beta
                    })
                    .collect::<HeapArray<_, N>>();
                FieldShareKeys::new(alpha, betas)
            })
            .collect::<Box<[_]>>();

        FieldShares {
            value: HeapArray::from_iter(values),
            macs,
            keys,
        }
    }
}

impl<F: FieldExtension, N: Positive> IntoParallelIterator for FieldShares<F, N> {
    type Item = FieldShare<F>;
    type Iter = rayon::vec::IntoIter<FieldShare<F>>;

    fn into_par_iter(self) -> Self::Iter {
        self.into_iter().collect::<Vec<_>>().into_par_iter()
    }
}

impl<F: FieldExtension, N: Positive> Batched for FieldShares<F, N> {
    type Item = FieldShare<F>;
    type Size = N;
}

// === Chunking === //
pub struct FieldSharesChunks<F: FieldExtension, M: Positive + PartialDiv<CS>, CS: Positive> {
    field_shares: FieldSharesIterator<F, M>,
    current_chunk: usize,
    _chunk_size: std::marker::PhantomData<CS>,
}

impl<F: FieldExtension, M: Positive + PartialDiv<CS>, CS: Positive> FieldSharesChunks<F, M, CS> {
    #[allow(clippy::len_without_is_empty)]
    pub fn len(&self) -> usize {
        // The size is always a multiple of the number of chunks because of the `PartialDiv<CS>`
        // bound
        M::USIZE / CS::USIZE - self.current_chunk
    }
}

impl<F: FieldExtension, M: Positive + PartialDiv<CS>, CS: Positive> Iterator
    for FieldSharesChunks<F, M, CS>
{
    type Item = FieldShares<F, CS>;

    fn next(&mut self) -> Option<Self::Item> {
        if self.current_chunk * CS::to_usize() >= M::to_usize() {
            return None;
        }

        let chunk_shares = self
            .field_shares
            .by_ref()
            .take(CS::to_usize())
            .collect::<Vec<_>>();

        self.current_chunk += 1;

        Some(chunk_shares.into_iter().collect())
    }
}

impl<F: FieldExtension, M: Positive> FieldShares<F, M> {
    /// Creates an iterator that yields chunks of the specified size. Each chunk is a
    /// `FieldShares<F, CS>`.
    pub fn chunks<CS: Positive>(&self) -> FieldSharesChunks<F, M, CS>
    where
        M: PartialDiv<CS>,
    {
        FieldSharesChunks {
            field_shares: self.into_iter(),
            current_chunk: 0,
            _chunk_size: std::marker::PhantomData,
        }
    }
}

#[cfg(test)]
mod tests {
    use std::ops::Div;

    use itertools::enumerate;
    use typenum::{Unsigned, U12};

    use super::*;
    use crate::{
        algebra::elliptic_curve::Curve25519Ristretto as C,
        random::{self},
        sharing::{GlobalScalarKey, ScalarShares, Verifiable},
        types::heap_array::curve_arrays::Scalars,
    };

    // TODO: Generalize once PairwiseAuthenticatedShare trait is implemented.

    //////////////////////////////////////////////////
    // CHANGE ONLY THESE TO TEST ANOTHER SHARE TYPE //
    pub type M = U12;
    pub type Value = Scalars<C, M>;
    pub type Constant = Scalars<C, M>;
    pub type Share = ScalarShares<C, M>;
    pub type GlobalKey = GlobalScalarKey<C>;

    // Batching
    pub type Mdiv2 = <M as Div<U2>>::Output;
    pub type ShareMdiv2 = ScalarShares<C, Mdiv2>;
    pub type Mdiv3 = <M as Div<U3>>::Output;
    pub type ShareMdiv3 = ScalarShares<C, Mdiv3>;
    //////////////////////////////////////////////////

    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 = &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_secret(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_secret_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_ref = izip_eq!(&shares_a)
            .map(|share_a| share_a * k.to_owned())
            .collect::<Vec<_>>();
        let reconstructed = Share::reconstruct_all(&shares_a_times_k_ref).unwrap();
        assert_eq!(reconstructed, a.to_owned() * k);

        // 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)));
    }

    #[test]
    fn test_split_halves() {
        let m_div2 = Mdiv2::to_usize();

        let shares = Share::random_with(&mut random::test_rng(), N_PARTIES);

        let (shares1, shares2) = shares.clone().split_halves::<Mdiv2>();

        // Check that the shares are split correctly
        assert_eq!(shares1.get_value().len(), m_div2);
        assert_eq!(shares2.get_value().len(), m_div2);

        assert_eq!(shares1.get_value().as_ref(), &shares.get_value()[..m_div2]);
        assert_eq!(shares2.get_value().as_ref(), &shares.get_value()[m_div2..]);

        izip_eq!(&shares1.macs, &shares2.macs, &shares.macs).for_each(|(mac1, mac2, mac)| {
            assert_eq!(mac1.as_ref(), &mac[..m_div2]);
            assert_eq!(mac2.as_ref(), &mac[m_div2..]);
        });
        izip_eq!(&shares1.keys, &shares2.keys, &shares.keys).for_each(|(key1, key2, key)| {
            assert_eq!(key1.alpha, key.alpha);
            assert_eq!(key2.alpha, key.alpha);
            assert_eq!(key1.betas.as_ref(), &key.betas[..m_div2]);
            assert_eq!(key2.betas.as_ref(), &key.betas[m_div2..]);
        });

        // Check that the shares can be merged back
        let merged_shares = ShareMdiv2::merge_halves(shares1, shares2);
        assert_eq!(merged_shares, shares);
    }

    #[test]
    fn test_split_thirds() {
        let m_div3 = Mdiv3::to_usize();

        let shares = Share::random_with(&mut random::test_rng(), N_PARTIES);

        let (shares1, shares2, shares3) = shares.clone().split_thirds::<Mdiv3>();

        // Check that the shares are split correctly
        assert_eq!(shares1.get_value().len(), m_div3);
        assert_eq!(shares2.get_value().len(), m_div3);
        assert_eq!(shares3.get_value().len(), m_div3);

        assert_eq!(shares1.get_value().as_ref(), &shares.get_value()[..m_div3]);
        assert_eq!(
            shares2.get_value().as_ref(),
            &shares.get_value()[m_div3..(2 * m_div3)]
        );
        assert_eq!(
            shares3.get_value().as_ref(),
            &shares.get_value()[(2 * m_div3)..]
        );

        izip_eq!(&shares1.macs, &shares2.macs, &shares3.macs, &shares.macs).for_each(
            |(mac1, mac2, mac3, mac)| {
                assert_eq!(mac1.as_ref(), &mac[..m_div3]);
                assert_eq!(mac2.as_ref(), &mac[m_div3..(2 * m_div3)]);
                assert_eq!(mac3.as_ref(), &mac[(2 * m_div3)..(3 * m_div3)]);
            },
        );

        izip_eq!(&shares1.keys, &shares2.keys, &shares3.keys, &shares.keys).for_each(
            |(key1, key2, key3, key)| {
                assert_eq!(key1.alpha, key.alpha);
                assert_eq!(key2.alpha, key.alpha);
                assert_eq!(key3.alpha, key.alpha);

                assert_eq!(key1.betas.as_ref(), &key.betas[..m_div3]);
                assert_eq!(key2.betas.as_ref(), &key.betas[m_div3..(2 * m_div3)]);
                assert_eq!(key3.betas.as_ref(), &key.betas[(2 * m_div3)..(3 * m_div3)]);
            },
        );

        // Check that the shares can be merged back
        let merged_shares = ShareMdiv3::merge_thirds(shares1, shares2, shares3);
        assert_eq!(merged_shares, shares);
    }

    #[test]
    fn test_into_iter() {
        let m = M::to_usize();

        let shares = Share::random_with(&mut random::test_rng(), N_PARTIES);

        let mut iter = shares.clone().into_iter();
        assert_eq!(iter.len(), m);

        for i in 0..m {
            assert_eq!(iter.len(), m - i);
            let share = iter.next().unwrap();
            assert_eq!(share.value, shares.get_value()[i]);

            for j in 0..N_PARTIES - 1 {
                assert_eq!(share.macs[j], shares.macs[j][i]);
                assert_eq!(share.keys[j].alpha, shares.keys[j].alpha);
                assert_eq!(share.keys[j].beta, shares.keys[j].betas[i]);
            }
        }
    }

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

        let collected: Vec<_> = shares.clone().into_iter().collect();
        let from_iterator: Share = collected.into_iter().collect();

        assert_eq!(shares, from_iterator);
    }

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

        let mut collected: Vec<_> = shares.clone().into_iter().collect();
        collected.pop(); // Make the sizes unequal
        let _ = collected.into_iter().collect::<Share>();
    }

    #[test]
    fn test_chunks() {
        type ChunkSize = typenum::U4;
        let m = M::to_usize();
        let chunk_size = ChunkSize::to_usize();
        let n_chunks = m / chunk_size;

        let shares = Share::random_with(&mut random::test_rng(), N_PARTIES);
        let mut chunks_iter = shares.chunks::<ChunkSize>();

        assert_eq!(chunks_iter.len(), n_chunks);

        for i in 0..n_chunks {
            // Check that the chunk size is correct
            assert_eq!(chunks_iter.len(), n_chunks - i);
            let chunk = chunks_iter.next().unwrap();
            assert_eq!(chunk.value.len(), chunk_size);

            for j in 0..chunk_size {
                assert_eq!(chunk.value[j], shares.get_value()[i * chunk_size + j]);
            }

            for (mac_chunk, macs) in izip_eq!(&chunk.macs, &shares.macs) {
                for j in 0..chunk_size {
                    assert_eq!(mac_chunk[j], macs[i * chunk_size + j]);
                }
            }

            for (key_chunk, keys) in izip_eq!(&chunk.keys, &shares.keys) {
                assert_eq!(key_chunk.alpha, keys.alpha);
                for j in 0..chunk_size {
                    assert_eq!(key_chunk.betas[j], keys.betas[i * chunk_size + j]);
                }
            }
        }

        assert!(chunks_iter.next().is_none());
    }
}