composite_modulus_proofs 0.1.0

//! Proof that modulus `N` is the product of two distinct primes. So `N` could be of form `p*q` but not `p*q*r` or `p^a*q^b`
//! where `p`, `q` and `r` are primes and `a, b > 1`. Described in section 3.4 of the paper [Efficient Noninteractive Certification of RSA Moduli and Beyond](https://eprint.iacr.org/2018/057)
//!
//! This is a combination of the 2 sub-protocols: proof that modulus `N` has exactly two distinct prime divisors and proof that `N` is square-free.
//!

use crate::{
    error::Error,
    setup::{Modulus, Primes, PrimesWithPrecomp},
    square_free::ProofSquareFree,
    two_prime_divisors::ProofTwoPrimeDivisors,
};
use ark_std::io::Write;
use crypto_bigint::{modular::SafeGcdInverter, Concat, Odd, PrecomputeInverter, Split, Uint};
use digest::{ExtendableOutput, Update};
use rand_core::CryptoRngCore;

/// Proof that modulus `N` is the product of two distinct primes
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct ProofProductOfTwoPrimes<
    const MODULUS_LIMBS: usize,
    const NUM_CHALLENGES_SQR_FREE: usize,
    const ALPHA: usize,
    const KAPPA: usize,
> {
    /// Proof that `N` is square-free
    pub square_free: ProofSquareFree<MODULUS_LIMBS, NUM_CHALLENGES_SQR_FREE, ALPHA, KAPPA>,
    /// Proof that modulus `N` has exactly two distinct prime divisors
    pub two_prime_divs: ProofTwoPrimeDivisors<MODULUS_LIMBS, KAPPA>,
}

impl<
        const MODULUS_LIMBS: usize,
        const NUM_CHALLENGES_SQR_FREE: usize,
        const ALPHA: usize,
        const KAPPA: usize,
    > ProofProductOfTwoPrimes<MODULUS_LIMBS, NUM_CHALLENGES_SQR_FREE, ALPHA, KAPPA>
{
    pub fn new<
        D: Default + Update + ExtendableOutput,
        W: Write + AsRef<[u8]>,
        const PRIME_LIMBS: usize,
        const PRIME_UNSAT_LIMBS: usize,
        const MODULUS_UNSAT_LIMBS: usize,
    >(
        primes: Primes<PRIME_LIMBS>,
        modulus: &Modulus<MODULUS_LIMBS>,
        nonce: &[u8],
        transcript: &mut W,
    ) -> Result<Self, Error>
    where
        Uint<PRIME_LIMBS>: Concat<Output = Uint<MODULUS_LIMBS>>,
        Uint<MODULUS_LIMBS>: Split<Output = Uint<PRIME_LIMBS>>,
        Odd<Uint<PRIME_LIMBS>>: PrecomputeInverter<
            Inverter = SafeGcdInverter<PRIME_LIMBS, PRIME_UNSAT_LIMBS>,
            Output = Uint<PRIME_LIMBS>,
        >,
        Odd<Uint<MODULUS_LIMBS>>:
            PrecomputeInverter<Inverter = SafeGcdInverter<MODULUS_LIMBS, MODULUS_UNSAT_LIMBS>>,
    {
        let square_free =
            ProofSquareFree::<MODULUS_LIMBS, NUM_CHALLENGES_SQR_FREE, ALPHA, KAPPA>::new::<
                D,
                W,
                PRIME_LIMBS,
                MODULUS_UNSAT_LIMBS,
            >(primes.clone(), modulus, nonce, transcript)?;
        let two_prime_divs = ProofTwoPrimeDivisors::<MODULUS_LIMBS, KAPPA>::new::<
            D,
            W,
            PRIME_LIMBS,
            PRIME_UNSAT_LIMBS,
        >(primes, modulus, nonce, transcript)?;
        Ok(Self {
            square_free,
            two_prime_divs,
        })
    }

    pub fn new_given_precomputation<
        D: Default + Update + ExtendableOutput,
        W: Write + AsRef<[u8]>,
        const PRIME_LIMBS: usize,
    >(
        primes: PrimesWithPrecomp<PRIME_LIMBS, MODULUS_LIMBS>,
        modulus: &Modulus<MODULUS_LIMBS>,
        nonce: &[u8],
        transcript: &mut W,
    ) -> Result<Self, Error>
    where
        Uint<PRIME_LIMBS>: Concat<Output = Uint<MODULUS_LIMBS>>,
        Uint<MODULUS_LIMBS>: Split<Output = Uint<PRIME_LIMBS>>,
    {
        let square_free = ProofSquareFree::<MODULUS_LIMBS, NUM_CHALLENGES_SQR_FREE, ALPHA, KAPPA>::new_given_precomputation::<
            D,
            W,
            PRIME_LIMBS,
        >(
            primes.clone(),
            modulus,
            nonce,
            transcript,
        )?;
        let two_prime_divs =
            ProofTwoPrimeDivisors::<MODULUS_LIMBS, KAPPA>::new_given_precomputation::<
                D,
                W,
                PRIME_LIMBS,
            >(primes, modulus, nonce, transcript)?;
        Ok(Self {
            square_free,
            two_prime_divs,
        })
    }

    pub fn num_responses_for_square_free_protocol(&self) -> usize {
        self.square_free.num_responses()
    }

    pub fn num_responses_for_two_prime_divisors_protocol(&self) -> usize {
        self.two_prime_divs.num_responses()
    }

    pub fn num_responses(&self) -> usize {
        self.square_free.num_responses() + self.two_prime_divs.num_responses()
    }

    pub fn verify<
        R: CryptoRngCore,
        D: Default + Update + ExtendableOutput,
        W: Write + AsRef<[u8]>,
    >(
        &self,
        rng: &mut R,
        modulus: &Modulus<MODULUS_LIMBS>,
        nonce: &[u8],
        transcript: &mut W,
    ) -> Result<(), Error> {
        self.square_free
            .verify::<D, W>(modulus, nonce, transcript)?;
        self.two_prime_divs
            .verify::<R, D, W>(rng, modulus, nonce, transcript)?;
        Ok(())
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::{safegcd_nlimbs, util::timing_info};
    use crypto_bigint::U256;
    use rand_core::OsRng;
    use sha3::Shake256;
    use std::time::Instant;

    macro_rules! check_given_primes {
        ( $num_iters: ident, $prime_type:ident, $primes: ident ) => {
            const KAPPA: usize = 128;
            const ALPHA: usize = 65537;
            const NUM_CHALLENGES_SQR_FREE: usize =
                crate::gcd_is_one::num_challenges::<ALPHA, KAPPA>() as usize;
            const NUM_CHALLENGES_M2: usize =
                crate::two_prime_divisors::num_challenges::<KAPPA>() as usize;

            const PRIME_LIMBS: usize = $prime_type::LIMBS;
            const PRIME_UNSAT_LIMBS: usize = safegcd_nlimbs!(Uint::<PRIME_LIMBS>::BITS as usize);
            const MODULUS_LIMBS: usize = PRIME_LIMBS * 2;
            const MODULUS_UNSAT_LIMBS: usize =
                safegcd_nlimbs!(Uint::<MODULUS_LIMBS>::BITS as usize);

            let mut rng = OsRng::default();
            let modulus = Modulus::<MODULUS_LIMBS>::new(&$primes);
            let primes_with_crt = PrimesWithPrecomp::from($primes.clone());
            let nonce = b"123";

            let mut prove_times = vec![];
            let mut prove_with_precomp_times = vec![];
            let mut ver_times = vec![];

            println!(
                "Running {} iterations for {} bits prime - {} challenges for {} bits of security",
                $num_iters,
                $prime_type::BITS,
                NUM_CHALLENGES_M2,
                KAPPA
            );
            for _ in 0..$num_iters {
                let mut transcript = vec![];
                let start = Instant::now();
                let proof = ProofProductOfTwoPrimes::<
                    MODULUS_LIMBS,
                    NUM_CHALLENGES_SQR_FREE,
                    ALPHA,
                    KAPPA,
                >::new::<Shake256, _, PRIME_LIMBS, PRIME_UNSAT_LIMBS, MODULUS_UNSAT_LIMBS>(
                    $primes.clone(),
                    &modulus,
                    nonce,
                    &mut transcript,
                )
                .unwrap();
                prove_times.push(start.elapsed());

                assert_eq!(
                    proof.num_responses_for_square_free_protocol(),
                    NUM_CHALLENGES_SQR_FREE
                );
                assert_eq!(
                    proof.num_responses_for_two_prime_divisors_protocol(),
                    NUM_CHALLENGES_M2
                );
                assert_eq!(
                    proof.num_responses(),
                    NUM_CHALLENGES_SQR_FREE + NUM_CHALLENGES_M2
                );

                let mut transcript = vec![];
                let start = Instant::now();
                proof
                    .verify::<OsRng, Shake256, _>(&mut rng, &modulus, nonce, &mut transcript)
                    .unwrap();
                ver_times.push(start.elapsed());

                let mut transcript = vec![];
                let start = Instant::now();
                let proof = ProofProductOfTwoPrimes::<
                    MODULUS_LIMBS,
                    NUM_CHALLENGES_SQR_FREE,
                    ALPHA,
                    KAPPA,
                >::new_given_precomputation::<Shake256, _, PRIME_LIMBS>(
                    primes_with_crt.clone(),
                    &modulus,
                    nonce,
                    &mut transcript,
                )
                .unwrap();
                prove_with_precomp_times.push(start.elapsed());

                let mut transcript = vec![];
                let start = Instant::now();
                proof
                    .verify::<OsRng, Shake256, _>(&mut rng, &modulus, nonce, &mut transcript)
                    .unwrap();
                ver_times.push(start.elapsed());
            }

            println!("Proving time: {:?}", timing_info(prove_times));
            println!(
                "Proving time with precomputation: {:?}",
                timing_info(prove_with_precomp_times)
            );
            println!("Verification time: {:?}", timing_info(ver_times));
        };
    }

    #[test]
    fn proof() {
        let mut rng = OsRng::default();
        let primes = Primes::<{ U256::LIMBS }>::new(&mut rng);
        let num_iters = 10;
        check_given_primes!(num_iters, U256, primes);
    }

    // TODO: Uncomment after optimizing prime-power check
    // #[test]
    // fn proof_with_1024_bit_primes() {
    //     let (p, q) = get_1024_bit_primes();
    //     let primes = Primes::from_primes(p, q);
    //     let num_iters = 10;
    //     check_given_primes!(num_iters, U1024, primes);
    // }
    //
    // #[test]
    // fn proof_with_2048_bit_primes() {
    //     let (p, q) = get_2048_bit_primes();
    //     let primes = Primes::from_primes(p, q);
    //     let num_iters = 10;
    //     check_given_primes!(num_iters, U2048, primes);
    // }
}