composite_modulus_proofs/

blum_integer.rs

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

#[derive(Debug, Clone, PartialEq, Eq)]
pub struct ProofOfBlumInteger<
    const MODULUS_LIMBS: usize,
    const NUM_CHALLENGES_SQR_FREE: usize,
    const ALPHA: usize,
    const KAPPA: usize,
> {
    pub square_free: ProofSquareFree<MODULUS_LIMBS, NUM_CHALLENGES_SQR_FREE, ALPHA, KAPPA>,
    pub blum_powers: ProofOfBlumPowers<MODULUS_LIMBS, KAPPA>,
}

impl<
        const MODULUS_LIMBS: usize,
        const NUM_CHALLENGES_SQR_FREE: usize,
        const ALPHA: usize,
        const KAPPA: usize,
    > ProofOfBlumInteger<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 blum_powers =
            ProofOfBlumPowers::<MODULUS_LIMBS, KAPPA>::new::<D, W, PRIME_LIMBS, PRIME_UNSAT_LIMBS>(
                primes, modulus, nonce, transcript,
            )?;
        Ok(Self {
            square_free,
            blum_powers,
        })
    }

    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 blum_powers = ProofOfBlumPowers::<MODULUS_LIMBS, KAPPA>::new_given_precomputation::<
            D,
            W,
            PRIME_LIMBS,
        >(primes, modulus, nonce, transcript)?;
        Ok(Self {
            square_free,
            blum_powers,
        })
    }

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

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

    pub fn num_responses(&self) -> usize {
        self.square_free.num_responses() + self.blum_powers.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.blum_powers
            .verify::<R, D, W>(rng, modulus, nonce, transcript)?;
        Ok(())
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::{math::misc::is_3_mod_4, safegcd_nlimbs, util::timing_info};
    use crypto_bigint::{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_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::<PRIME_LIMBS, MODULUS_LIMBS>::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 = ProofOfBlumInteger::<
                    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_blum_powers_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 = ProofOfBlumInteger::<
                    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 bad_proof() {
        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 PRIME_LIMBS: usize = U64::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 blum_primes = Primes::<{ U64::LIMBS }>::new_with_blum_primes(&mut rng);
        let modulus = Modulus::<MODULUS_LIMBS>::new(&blum_primes);

        // Create non-Blum primes. Proofs should fail for these
        let non_blum_primes = {
            let mut pr = Primes::<{ U64::LIMBS }>::new(&mut rng);
            while is_3_mod_4(&pr.p) || is_3_mod_4(&pr.q) {
                pr = Primes::<{ U64::LIMBS }>::new(&mut rng);
            }
            pr
        };
        let bad_modulus = Modulus::<MODULUS_LIMBS>::new(&non_blum_primes);
        let nonce = b"123";

        let mut transcript = vec![];
        let proof =
            ProofOfBlumInteger::<MODULUS_LIMBS, NUM_CHALLENGES_SQR_FREE, ALPHA, KAPPA>::new::<
                Shake256,
                _,
                PRIME_LIMBS,
                PRIME_UNSAT_LIMBS,
                MODULUS_UNSAT_LIMBS,
            >(blum_primes.clone(), &modulus, nonce, &mut transcript)
            .unwrap();

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

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

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