composite_modulus_proofs 0.1.0

//! Proof that modulus `N` is square-free. Described in section 3.2 of the paper [Efficient Noninteractive Certification of RSA Moduli and Beyond](https://eprint.iacr.org/2018/057)
//! Uses the proof protocol of `gcd(x, phi(N)) = 1` where `x` is set to `N` since `gcd(N, phi(N)) = 1` implies `N` is square free as
//! per Lemma A.3 of the paper

use crate::{
    error::Error,
    gcd_is_one::ProofGcdIsOne,
    setup::{Modulus, Primes, PrimesWithPrecomp},
};
use ark_std::io::Write;
use crypto_bigint::{modular::SafeGcdInverter, Concat, Odd, PrecomputeInverter, Split, Uint};
use digest::{ExtendableOutput, Update};

/// Proof that `N` is square-free. `NUM_CHALLENGES` depends on `ALPHA` and `KAPPA` as per the paper but can also
/// be set independently as done in another protocol.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct ProofSquareFree<
    const MODULUS_LIMBS: usize,
    const NUM_CHALLENGES: usize,
    const ALPHA: usize,
    const KAPPA: usize,
>(pub ProofGcdIsOne<MODULUS_LIMBS, NUM_CHALLENGES, ALPHA, KAPPA>);

impl<
        const MODULUS_LIMBS: usize,
        const NUM_CHALLENGES: usize,
        const ALPHA: usize,
        const KAPPA: usize,
    > ProofSquareFree<MODULUS_LIMBS, NUM_CHALLENGES, ALPHA, KAPPA>
{
    /// Create a proof that `N` is square-free. `transcript` is the proof transcript that is shared by
    /// other sub-protocols as well which this is running as a sub-protocol of a larger protocol.
    pub fn new<
        D: Default + Update + ExtendableOutput,
        W: Write + AsRef<[u8]>,
        const PRIME_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>>,
        Odd<Uint<MODULUS_LIMBS>>:
            PrecomputeInverter<Inverter = SafeGcdInverter<MODULUS_LIMBS, MODULUS_UNSAT_LIMBS>>,
    {
        Ok(Self(ProofGcdIsOne::new::<
            D,
            W,
            PRIME_LIMBS,
            MODULUS_UNSAT_LIMBS,
        >(
            modulus.0.as_ref(),
            primes,
            modulus,
            nonce,
            transcript,
        )?))
    }

    /// Same as `Self::new` but returns the challenges used to create the proof. Useful when used with certain other protocols
    pub fn new_and_return_challenges<
        D: Default + Update + ExtendableOutput,
        W: Write + AsRef<[u8]>,
        const PRIME_LIMBS: usize,
        const MODULUS_UNSAT_LIMBS: usize,
    >(
        primes: Primes<PRIME_LIMBS>,
        modulus: &Modulus<MODULUS_LIMBS>,
        nonce: &[u8],
        transcript: &mut W,
    ) -> Result<(Self, [Uint<MODULUS_LIMBS>; NUM_CHALLENGES]), Error>
    where
        Uint<PRIME_LIMBS>: Concat<Output = Uint<MODULUS_LIMBS>>,
        Odd<Uint<MODULUS_LIMBS>>:
            PrecomputeInverter<Inverter = SafeGcdInverter<MODULUS_LIMBS, MODULUS_UNSAT_LIMBS>>,
    {
        let (p, challenges) = ProofGcdIsOne::new_and_return_challenges::<
            D,
            W,
            PRIME_LIMBS,
            MODULUS_UNSAT_LIMBS,
        >(modulus.0.as_ref(), primes, modulus, nonce, transcript)?;
        Ok((Self(p), challenges))
    }

    /// Same as `Self::new` but takes the primes and some precomputation to make the proof generation is faster.
    /// Use it if creating frequent proofs.
    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 n_inv_p_minus_1 = primes.n_inv_p_minus_1.clone();
        let n_inv_q_minus_1 = primes.n_inv_q_minus_1.clone();
        Ok(Self(ProofGcdIsOne::new_given_x_inv_and_precomputation::<
            D,
            W,
            PRIME_LIMBS,
        >(
            modulus.0.as_ref(),
            &n_inv_p_minus_1,
            &n_inv_q_minus_1,
            primes,
            modulus,
            nonce,
            transcript,
        )?))
    }

    /// Same as `Self::new_given_precomputation` but returns the challenges used to create the proof. Useful when used with certain other protocols
    pub fn new_given_precomputation_and_return_challenges<
        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, [Uint<MODULUS_LIMBS>; NUM_CHALLENGES]), Error>
    where
        Uint<PRIME_LIMBS>: Concat<Output = Uint<MODULUS_LIMBS>>,
        Uint<MODULUS_LIMBS>: Split<Output = Uint<PRIME_LIMBS>>,
    {
        let n_inv_p_minus_1 = primes.n_inv_p_minus_1.clone();
        let n_inv_q_minus_1 = primes.n_inv_q_minus_1.clone();
        let (proof, challenges) =
            ProofGcdIsOne::new_given_x_inv_and_precomputation_and_return_challenges::<
                D,
                W,
                PRIME_LIMBS,
            >(
                modulus.0.as_ref(),
                &n_inv_p_minus_1,
                &n_inv_q_minus_1,
                primes,
                modulus,
                nonce,
                transcript,
            )?;
        Ok((Self(proof), challenges))
    }

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

    /// Verify the proof that `N` is square-free. `transcript` is the proof transcript that is shared by
    /// other sub-protocols as well which this is running as a sub-protocol of a larger protocol.
    pub fn verify<D: Default + Update + ExtendableOutput, W: Write + AsRef<[u8]>>(
        &self,
        modulus: &Modulus<MODULUS_LIMBS>,
        nonce: &[u8],
        transcript: &mut W,
    ) -> Result<(), Error> {
        self.0
            .verify::<D, W>(modulus.0.as_ref(), modulus, nonce, transcript)
    }

    pub fn verify_and_return_challenges<
        D: Default + Update + ExtendableOutput,
        W: Write + AsRef<[u8]>,
    >(
        &self,
        modulus: &Modulus<MODULUS_LIMBS>,
        nonce: &[u8],
        transcript: &mut W,
    ) -> Result<((), [Uint<MODULUS_LIMBS>; NUM_CHALLENGES]), Error> {
        self.0
            .verify_and_return_challenges::<D, W>(modulus.0.as_ref(), modulus, nonce, transcript)
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::{
        gcd_is_one::num_challenges,
        safegcd_nlimbs,
        util::{get_1024_bit_primes, get_2048_bit_primes, timing_info},
    };
    use crypto_bigint::{U1024, U2048, U256, U64};
    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: usize = num_challenges::<ALPHA, 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 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_crt_times = vec![];
            let mut ver_times = vec![];

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

                assert_eq!(proof.num_responses(), NUM_CHALLENGES);

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

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

                assert_eq!(proof.num_responses(), NUM_CHALLENGES);

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

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

            let mut same_primes = $primes.clone();
            same_primes.q = same_primes.p;
            let modulus_with_square = Modulus::<MODULUS_LIMBS>::new(&same_primes);

            let mut transcript = vec![];
            let proof = ProofSquareFree::<MODULUS_LIMBS, NUM_CHALLENGES, ALPHA, KAPPA>::new::<
                Shake256,
                _,
                PRIME_LIMBS,
                MODULUS_UNSAT_LIMBS,
            >(
                same_primes.clone(),
                &modulus_with_square,
                nonce,
                &mut transcript,
            )
            .unwrap();

            let mut transcript = vec![];
            assert!(proof
                .verify::<Shake256, _>(&modulus, nonce, &mut transcript)
                .is_err());
        };
    }

    #[test]
    fn bad_proofs() {
        const KAPPA: usize = 128;
        const ALPHA: usize = 65537;
        const NUM_CHALLENGES: usize = num_challenges::<ALPHA, KAPPA>() as usize;
        const PRIME_LIMBS: usize = U64::LIMBS;
        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 primes = Primes::<{ U64::LIMBS }>::new(&mut rng);
        let nonce = b"123";

        let mut same_primes = primes.clone();
        same_primes.q = same_primes.p;
        let modulus_with_square = Modulus::<MODULUS_LIMBS>::new(&same_primes);

        let mut transcript = vec![];
        let proof = ProofSquareFree::<MODULUS_LIMBS, NUM_CHALLENGES, ALPHA, KAPPA>::new::<
            Shake256,
            _,
            PRIME_LIMBS,
            MODULUS_UNSAT_LIMBS,
        >(
            same_primes.clone(),
            &modulus_with_square,
            nonce,
            &mut transcript,
        )
        .unwrap();

        let mut transcript = vec![];
        assert!(proof
            .verify::<Shake256, _>(&modulus_with_square, nonce, &mut transcript)
            .is_err());
    }

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

    #[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);
    }
}