primitives/sharing/authenticated/batched/

curve_shares.rs

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

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

use super::CurveKeys;
use crate::{
    algebra::elliptic_curve::{Curve, Scalar, ScalarAsExtension},
    errors::{
        PrimitiveError,
        VerificationError::{self, MissingKey},
    },
    izip_eq,
    random::{CryptoRngCore, Random, RandomWith},
    sharing::{
        authenticated::NParties,
        unauthenticated::AdditiveShares,
        GlobalCurveKey,
        Reconstructible,
        VerifiableWith,
    },
    types::{
        heap_array::curve_arrays::{CurvePoints, Scalars, ScalarsAsExtension},
        ConditionallySelectable,
        PeerIndex,
        Positive,
    },
    utils::IntoExactSizeIterator,
};
#[derive(Clone, Default, PartialEq, Eq, Serialize, Deserialize)]
#[serde(bound = "C: Curve, M: Positive")]
pub struct OpenPointShares<C: Curve, M: Positive> {
    pub(crate) value: CurvePoints<C, M>,
    pub(crate) mac: CurvePoints<C, M>,
}

impl<C: Curve, M: Positive> OpenPointShares<C, M> {
    pub fn new(value: CurvePoints<C, M>, mac: CurvePoints<C, M>) -> Self {
        Self { value, mac }
    }

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

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

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

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

impl<C: Curve, M: Positive> PointShares<C, M> {
    pub fn try_new(
        value: CurvePoints<C, M>,
        macs: Box<[CurvePoints<C, M>]>,
        keys: Box<[CurveKeys<C, M>]>,
    ) -> Result<Self, PrimitiveError> {
        if macs.is_empty() {
            return Err(PrimitiveError::InvalidParameters(
                "n_parties < 2".to_string(),
            ));
        }
        if macs.len() != keys.len() {
            return Err(PrimitiveError::SizeError(macs.len(), keys.len()));
        }
        /* NOTE: We assume length equality for macs & keys from this point on */
        Ok(Self { value, macs, keys })
    }

    fn new(
        value: CurvePoints<C, M>,
        macs: Box<[CurvePoints<C, M>]>,
        keys: Box<[CurveKeys<C, M>]>,
    ) -> Self {
        Self { value, macs, keys }
    }

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

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

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

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

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

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

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

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

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

impl<C: Curve, M: Positive> Reconstructible for PointShares<C, M> {
    type Opening = OpenPointShares<C, M>;
    type Secret = CurvePoints<C, M>;

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

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

    /// Reconstruct a secret from openings coming from all other parties.
    fn reconstruct(
        &self,
        openings: &[OpenPointShares<C, M>],
    ) -> Result<Self::Secret, PrimitiveError> {
        if openings.len() != self.get_keys().len() {
            return Err(PrimitiveError::SizeError(
                openings.len(),
                self.get_keys().len(),
            ));
        }

        izip_eq!(openings, self.get_keys()).enumerate().try_fold(
            self.get_value().to_owned(),
            |acc, (i, (open_share, key))| {
                key.verify_mac(open_share)
                    .map_err(|e| e.blame(i).add_state(self))?;
                Ok(acc + open_share.get_value())
            },
        )
    }
}

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

fn compute_macs<C: Curve, M: Positive>(
    all_unauth_shares: &[CurvePoints<C, M>],
    all_keys: &[Box<[CurveKeys<C, M>]>],
) -> Vec<Box<[CurvePoints<C, 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<C: Curve, M: Positive> Random for PointShares<C, 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 one random field share per peer, with consistent MACs and keys across all peers.
    fn random_n<Container: FromIterator<Self>>(
        mut rng: impl CryptoRngCore,
        n_parties: NParties,
    ) -> Container {
        let all_unauth_shares: Vec<_> = CurvePoints::random_n(&mut rng, n_parties);
        let all_keys = (0..n_parties)
            .map(|_| CurveKeys::<C, 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)| PointShares::new(value, macs, keys))
            .collect()
    }
}

impl<C: Curve, M: Positive> RandomWith<NParties> for PointShares<C, 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 {
        PointShares::new(
            CurvePoints::<C, M>::random(&mut rng),
            CurvePoints::<C, M>::random_n(&mut rng, n_parties - 1),
            CurveKeys::<C, M>::random_n(&mut rng, n_parties - 1),
        )
    }
}

impl<C: Curve, M: Positive> RandomWith<(NParties, CurvePoints<C, M>)> for PointShares<C, 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, CurvePoints<C, M>),
    ) -> Self {
        let (n_parties, value) = n_parties_value;
        PointShares::new(
            value,
            CurvePoints::<C, M>::random_n(&mut rng, n_parties - 1),
            CurveKeys::<C, M>::random_n(&mut rng, n_parties - 1),
        )
    }
}

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

    /// Generate a random field share with a specific secret share as value,
    /// with consistent random MACs and keys across all peers.
    fn random_n_with_each<Container: FromIterator<Self>>(
        mut rng: impl CryptoRngCore,
        n_parties_and_value: impl IntoExactSizeIterator<Item = CurvePoints<C, M>>,
    ) -> Container {
        let all_unauth_shares = n_parties_and_value.into_iter().collect::<Vec<_>>();
        let n_parties = all_unauth_shares.len();
        let all_keys = (0..n_parties)
            .map(|_| CurveKeys::<C, 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)| PointShares::new(value, macs, keys))
            .collect()
    }
}

impl<C: Curve, M: Positive> RandomWith<Vec<GlobalCurveKey<C>>> for PointShares<C, M> {
    /// Generate a random field share from its global keys (alphas).
    fn random_with(mut rng: impl CryptoRngCore, alphas: Vec<GlobalCurveKey<C>>) -> Self {
        let n_other_parties = alphas.len();
        PointShares::new(
            CurvePoints::random(&mut rng),
            CurvePoints::<C, M>::random_n(&mut rng, n_other_parties),
            CurveKeys::<C, 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<GlobalCurveKey<C>>>,
    ) -> Container {
        let all_alphas = all_alphas.into_iter();
        let all_unauth_shares: Vec<_> = CurvePoints::random_n(&mut rng, all_alphas.len());
        let all_keys = all_alphas
            .into_iter()
            .map(|my_alphas| CurveKeys::<C, 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)| PointShares::new(value, macs, keys))
            .collect()
    }
}

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

impl<C: Curve, M: Positive> RandomWith<(CurvePoints<C, M>, Vec<Vec<GlobalCurveKey<C>>>)>
    for PointShares<C, M>
{
    fn random_with(
        _rng: impl CryptoRngCore,
        _data: (CurvePoints<C, M>, Vec<Vec<GlobalCurveKey<C>>>),
    ) -> 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: (CurvePoints<C, M>, Vec<Vec<GlobalCurveKey<C>>>),
    ) -> Container {
        let (secret_value, all_alphas) = secret_value_and_alphas;
        assert_eq!(all_alphas.len(), n_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| CurveKeys::<C, 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)| PointShares::new(value, macs, keys))
            .collect()
    }
}

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

// === Addition === //

impl<C: Curve, M: Positive> Add for PointShares<C, M> {
    type Output = PointShares<C, M>;

    #[inline]
    fn add(mut self, other: PointShares<C, M>) -> Self::Output {
        self.value += other.value;
        izip_eq!(&mut self.macs, other.macs).for_each(|(a, b)| *a += b);
        izip_eq!(&mut self.keys, other.keys).for_each(|(a, b)| *a += b);
        self
    }
}

impl<'a, C: Curve, M: Positive> Add for &'a PointShares<C, M> {
    type Output = PointShares<C, M>;

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

impl<C: Curve, M: Positive> Add<PointShares<C, M>> for &PointShares<C, M> {
    type Output = PointShares<C, M>;

    #[inline]
    fn add(self, mut other: PointShares<C, M>) -> Self::Output {
        other.value += &self.value;
        izip_eq!(&mut other.macs, &self.macs).for_each(|(a, b)| *a += b);
        izip_eq!(&mut other.keys, &self.keys).for_each(|(a, b)| *a += b);
        other
    }
}

impl<'a, C: Curve, M: Positive> Add<&'a PointShares<C, M>> for PointShares<C, M> {
    type Output = PointShares<C, M>;

    #[inline]
    fn add(mut self, other: &'a PointShares<C, M>) -> Self::Output {
        self.value += &other.value;
        izip_eq!(&mut self.macs, &other.macs).for_each(|(a, b)| *a += b);
        izip_eq!(&mut self.keys, &other.keys).for_each(|(a, b)| *a += b);
        self
    }
}

// === AddAssign === //

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

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

// === Subtraction === //

impl<C: Curve, M: Positive> Sub for PointShares<C, M> {
    type Output = PointShares<C, M>;

    #[inline]
    fn sub(mut self, other: PointShares<C, M>) -> Self::Output {
        self.value -= other.value;
        izip_eq!(&mut self.macs, other.macs).for_each(|(a, b)| *a -= b);
        izip_eq!(&mut self.keys, other.keys).for_each(|(a, b)| *a -= b);
        self
    }
}

impl<'a, C: Curve, M: Positive> Sub<&'a PointShares<C, M>> for &'a PointShares<C, M> {
    type Output = PointShares<C, M>;

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

impl<C: Curve, M: Positive> Sub<PointShares<C, M>> for &PointShares<C, M> {
    type Output = PointShares<C, M>;

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

impl<'a, C: Curve, M: Positive> Sub<&'a PointShares<C, M>> for PointShares<C, M> {
    type Output = PointShares<C, M>;

    #[inline]
    fn sub(mut self, other: &'a PointShares<C, M>) -> Self::Output {
        self.value -= &other.value;
        izip_eq!(&mut self.macs, &other.macs).for_each(|(a, b)| *a -= b);
        izip_eq!(&mut self.keys, &other.keys).for_each(|(a, b)| *a -= b);
        self
    }
}
// === SubAssign === //

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

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

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

impl<'a, C: Curve, M: Positive> Mul<&'a ScalarAsExtension<C>> for PointShares<C, M> {
    type Output = PointShares<C, M>;

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

impl<'a, C: Curve, M: Positive> Mul<&'a ScalarAsExtension<C>> for &'a PointShares<C, M> {
    type Output = PointShares<C, M>;

    #[inline]
    fn mul(self, other: &'a ScalarAsExtension<C>) -> Self::Output {
        PointShares {
            value: &self.value * other,
            keys: self.keys.iter().map(|key| key * other).collect(),
            macs: self.macs.iter().map(|mac| mac * other).collect(),
        }
    }
}

impl<'a, C: Curve, M: Positive> Mul<&'a Scalar<C>> for PointShares<C, M> {
    type Output = PointShares<C, M>;

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

impl<'a, C: Curve, M: Positive> Mul<&'a Scalar<C>> for &'a PointShares<C, M> {
    type Output = PointShares<C, M>;

    #[inline]
    fn mul(self, other: &'a Scalar<C>) -> Self::Output {
        PointShares {
            value: &self.value * other,
            keys: self.keys.iter().map(|key| key * other).collect(),
            macs: self.macs.iter().map(|mac| mac * other).collect(),
        }
    }
}

impl<'a, C: Curve, M: Positive> Mul<&'a ScalarsAsExtension<C, M>> for PointShares<C, M> {
    type Output = PointShares<C, M>;

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

impl<'a, C: Curve, M: Positive> Mul<&'a ScalarsAsExtension<C, M>> for &'a PointShares<C, M> {
    type Output = PointShares<C, M>;

    #[inline]
    fn mul(self, other: &'a ScalarsAsExtension<C, M>) -> Self::Output {
        PointShares {
            value: &self.value * other,
            keys: self.keys.iter().map(|key| key * other).collect(),
            macs: self.macs.iter().map(|mac| mac * other).collect(),
        }
    }
}

impl<'a, C: Curve, M: Positive> Mul<&'a Scalars<C, M>> for PointShares<C, M> {
    type Output = PointShares<C, M>;

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

impl<'a, C: Curve, M: Positive> Mul<&'a Scalars<C, M>> for &'a PointShares<C, M> {
    type Output = PointShares<C, M>;

    #[inline]
    fn mul(self, other: &'a Scalars<C, M>) -> Self::Output {
        PointShares {
            value: &self.value * other,
            keys: self.keys.iter().map(|key| key * other).collect(),
            macs: self.macs.iter().map(|mac| mac * other).collect(),
        }
    }
}

// === MulAssign === //

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

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

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

impl<'a, C: Curve, M: Positive> MulAssign<&'a Scalars<C, M>> for PointShares<C, M> {
    #[inline]
    fn mul_assign(&mut self, other: &'a Scalars<C, M>) {
        self.value *= other;
        izip_eq!(&mut self.keys).for_each(|key| *key *= other);
        izip_eq!(&mut self.macs).for_each(|mac| *mac *= other);
    }
}
// === Negation === //

impl<C: Curve, M: Positive> Neg for PointShares<C, M> {
    type Output = Self;

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

impl<C: Curve, M: Positive> Neg for &PointShares<C, M> {
    type Output = PointShares<C, M>;

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

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

impl<C: Curve, M: Positive> PointShares<C, 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: &CurvePoints<C, 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 * *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: &CurvePoints<C, M>, is_peer_zero: bool) -> Self {
        let result = self.clone();
        result.add_secret_owned(constant, is_peer_zero)
    }
}

// === Constant time equality / selection === //

impl<C: Curve, M: Positive> ConstantTimeEq for PointShares<C, 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)
    }
}

impl<C: Curve, M: Positive> ConditionallySelectable for PointShares<C, M> {
    fn conditional_select(a: &Self, b: &Self, choice: Choice) -> Self {
        PointShares {
            value: CurvePoints::conditional_select(&a.value, &b.value, choice),
            macs: izip_eq!(&a.macs, &b.macs)
                .map(|(a, b)| CurvePoints::conditional_select(a, b, choice))
                .collect(),
            keys: izip_eq!(&a.keys, &b.keys)
                .map(|(a, b)| CurveKeys::conditional_select(a, b, choice))
                .collect(),
        }
    }
}

#[cfg(test)]
mod tests {

    use itertools::enumerate;
    use typenum::U12;

    use super::*;
    use crate::{
        algebra::elliptic_curve::Curve25519Ristretto as C,
        random,
        sharing::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 = CurvePoints<C, M>;
    pub type Constant = Scalars<C, M>;
    pub type Share = PointShares<C, M>;
    pub type GlobalKey = GlobalCurveKey<C>;
    //////////////////////////////////////////////////

    pub const N_PARTIES: usize = 3;

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

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

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

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

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

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

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

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

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

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