arcium-primitives 0.4.0

pub mod prf;
pub mod prg;
pub mod rng;

use rand::{distributions::Standard, prelude::Distribution};
pub use rand_chacha::rand_core::CryptoRngCore;
#[cfg(any(test, feature = "dev"))]
pub use rng::test_rng;
pub use rng::{BaseRng, Seed, SeedableRng};
use subtle::Choice;
use typenum::Unsigned;

use crate::{
    algebra::field::FieldExtension,
    constants::Lambda,
    errors::PrimitiveError,
    utils::IntoExactSizeIterator,
};

/// A trait for getting a random value for a type. Will be replaced by the `random` feature
/// once it is included in std (https://github.com/rust-lang/rust/issues/130703).
pub trait Random: Sized {
    // Generates a random value.
    fn random(rng: impl CryptoRngCore) -> Self;

    // Generates a container with `size` random elements.
    fn random_n<Container: FromIterator<Self>>(
        mut rng: impl CryptoRngCore,
        size: usize,
    ) -> Container {
        (0..size).map(|_| Self::random(&mut rng)).collect()
    }
}

/// Generalise so that `rand::random()` can be used for any type that implements `Random`.
impl<T> Random for T
where
    Standard: Distribution<T>,
{
    #[inline]
    fn random(mut source: impl CryptoRngCore) -> Self {
        Standard.sample(&mut source)
    }
}

/// A trait for getting a random value for a type alongside some data.
pub trait RandomWith<D: Clone>: Sized {
    // Generates a random value given additional data.
    fn random_with(rng: impl CryptoRngCore, data: D) -> Self;

    // Generates a container with `size` random elements and some available data.
    fn random_n_with<Container: FromIterator<Self>>(
        mut rng: impl CryptoRngCore,
        size: usize,
        data: D,
    ) -> Container {
        (0..size)
            .map(|_| Self::random_with(&mut rng, data.clone()))
            .collect()
    }

    // Generates a container with `size` random elements and some available data.
    fn random_n_with_each<Container: FromIterator<Self>>(
        mut rng: impl CryptoRngCore,
        all_data: impl IntoExactSizeIterator<Item = D>,
    ) -> Container {
        all_data
            .into_iter()
            .map(|data| Self::random_with(&mut rng, data))
            .collect()
    }
}

/// Generate random non-zero values.
pub trait RandomNonZero: Sized {
    // Generates a non-zero element.
    fn random_non_zero(rng: impl CryptoRngCore) -> Result<Self, PrimitiveError>;

    // Generates a container with `size` random non-zero elements.
    fn random_n_non_zero<Container: FromIterator<Self>>(
        rng: impl CryptoRngCore,
        size: usize,
    ) -> Result<Container, PrimitiveError>;
}

impl<T: FieldExtension> RandomNonZero for T {
    /// Generates a random non-zero value.
    ///
    /// May error out if it cannot find a non-zero value after a certain number
    /// of tries, defined so that:
    ///
    /// > `Prob(out == 0) <= 2^-(λ)` as long as `Prob(random()==0) <= 2^-(size_of::<Self>)`
    ///
    /// The default implementation repetitively calls `random()` (rejection sampling).
    /// As such, it is not constant-time, but the side channel leakage should not impact security
    /// as long as the rng is evaluated in constant time and produces uniformly random values.
    ///
    /// If needed, override with a constant-time implementation using `ConditionallySelectable` and
    /// always running for a fixed number of iterations, potentially returning a zero value
    /// (with overwhelmingly low probability).
    #[inline]
    fn random_non_zero(mut rng: impl CryptoRngCore) -> Result<Self, PrimitiveError> {
        let n_tries = (Lambda::USIZE).div_ceil(std::mem::size_of::<Self>());
        for _ in 0..n_tries {
            let value = <Self as ff::Field>::random(&mut rng);
            if !<Choice as Into<bool>>::into(value.is_zero()) {
                return Ok(value);
            }
        }
        Err(PrimitiveError::ZeroValueSampled(
            std::any::type_name::<Self>().into(),
        ))
    }

    // Generates a container with `size` random non-zero elements.
    fn random_n_non_zero<Container: FromIterator<Self>>(
        mut rng: impl CryptoRngCore,
        size: usize,
    ) -> Result<Container, PrimitiveError> {
        (0..size).map(|_| Self::random_non_zero(&mut rng)).collect()
    }
}