composite_modulus_proofs 0.1.0

//! Proving that a modulus is a Paillier-Blum modulus, i.e. `gcd(N, phi(N)) = 1` for modulus `N=p*q` where `p` and `q` are Blum primes, i.e. `p mod 4 = 3` and `q mod 4 = 3` using the protocol described in Fig 12, section 5.2 in the paper [UC Non-Interactive, Proactive, Distributed ECDSA with Identifiable Aborts](https://eprint.iacr.org/2021/060)
//!
//! Also refer the non-interactive version [here](https://www.zkdocs.com/docs/zkdocs/zero-knowledge-protocols/product-primes/paillier_blum_modulus/) but this
//! implementation has a minor deviation. Rather than prover sampling a quadratic non-residue and sending it in proof, it's generated by hashing
//! random bytes such that verifier can generate himself.
//!
//! Uses the protocol for square-free `N` to prove `gcd(N, phi(N)) = 1`

use crate::{
    error::Error,
    math::{
        jacobi::jacobi_symbol_vartime,
        sqrt::{
            exponents_for_sqrt_mod_blum_integer,
            fourth_root_mod_blum_integer_given_prime_factors_as_mtg_params_and_precomp,
        },
    },
    setup::{Modulus, Primes, PrimesWithPrecomp},
    square_free::ProofSquareFree,
    util::uint_le_bytes,
};
use alloc::vec;
use ark_std::{cfg_into_iter, cfg_iter_mut, io::Write};
use crypto_bigint::{
    modular::{MontyForm, MontyParams, SafeGcdInverter},
    Concat, Odd, PrecomputeInverter, Split, Uint,
};
use crypto_primes::is_prime_with_rng;
use digest::{ExtendableOutput, Update};
use rand_core::CryptoRngCore;

#[cfg(feature = "parallel")]
use rayon::prelude::*;

/// Proving that a modulus is a Paillier-Blum modulus, i.e. `gcd(N, phi(N)) = 1` for modulus `N=p*q` where `p` and `q` are Blum primes, i.e. `p mod 4 = 3` and `q mod 4 = 3`
/// `NUM_CHALLENGES` is what's called `m` in the paper. `KAPPA` isn't really used here and is only because `ProofSquareFree` requires it.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct ProofPaillierBlumModulus<
    const MODULUS_LIMBS: usize,
    const NUM_CHALLENGES: usize,
    const ALPHA: usize,
    const KAPPA: usize,
> {
    pub square_free: ProofSquareFree<MODULUS_LIMBS, NUM_CHALLENGES, ALPHA, KAPPA>,
    /// Each item of the array is `(selector, response)` where `response` is the 4th root and `selector`
    /// determines whose 4th root is it.
    /// For index `i`, challenge and response are `c_i` and `r_i` respectively and `w` is a quadratic
    /// non-residue with Jacobi symbol -1, following rules apply
    /// selector = 0 => `r_i = {c_i}^4`
    /// selector = 1 => `r_i = {-c_i}^4`
    /// selector = 2 => `r_i = {w*c_i}^4`
    /// selector = 3 => `r_i = {-w*c_i}^4`
    pub responses: [(u8, Uint<MODULUS_LIMBS>); NUM_CHALLENGES],
}

impl<
        const MODULUS_LIMBS: usize,
        const NUM_CHALLENGES: usize,
        const ALPHA: usize,
        const KAPPA: usize,
    > ProofPaillierBlumModulus<MODULUS_LIMBS, NUM_CHALLENGES, 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 w = Self::generate_qnr::<D, W>(modulus, nonce, transcript);
        let (square_free, challenges) = ProofSquareFree::<
            MODULUS_LIMBS,
            NUM_CHALLENGES,
            ALPHA,
            KAPPA,
        >::new_and_return_challenges::<
            D,
            W,
            PRIME_LIMBS,
            MODULUS_UNSAT_LIMBS,
        >(primes.clone(), modulus, nonce, transcript)?;
        let p_mtg = MontyParams::new(primes.p);
        let q_mtg = MontyParams::new(primes.q);
        // gcd(p, q) will be 1
        let p_inv = MontyForm::new(p_mtg.modulus(), q_mtg).inv().unwrap();
        Ok(Self {
            square_free,
            responses: Self::generate_responses(&w, &challenges, modulus, p_mtg, q_mtg, p_inv),
        })
    }

    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 w = Self::generate_qnr::<D, W>(modulus, nonce, transcript);
        let (square_free, challenges) = ProofSquareFree::<
            MODULUS_LIMBS,
            NUM_CHALLENGES,
            ALPHA,
            KAPPA,
        >::new_given_precomputation_and_return_challenges::<
            D,
            W,
            PRIME_LIMBS,
        >(primes.clone(), modulus, nonce, transcript)?;
        Ok(Self {
            square_free,
            responses: Self::generate_responses(
                &w,
                &challenges,
                modulus,
                primes.p_mtg,
                primes.q_mtg,
                primes.p_inv,
            ),
        })
    }

    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> {
        if is_prime_with_rng(rng, modulus.0.as_ref()) {
            return Err(Error::ModulusIsPrime);
        }
        let w = Self::generate_qnr::<D, W>(modulus, nonce, transcript);
        let (_, challenges) = self
            .square_free
            .verify_and_return_challenges::<D, W>(modulus, nonce, transcript)?;
        let params = MontyParams::new_vartime(modulus.0);
        let w_mtg = MontyForm::new(&w, params);
        #[allow(unused_mut)]
        let mut res = cfg_into_iter!(0..challenges.len()).map(|i| {
            let (selector, r) = self.responses[i];
            if !modulus.is_greater_than(&r) {
                return Err(Error::GreaterThanModulus(i as u32));
            }
            let r_4 = MontyForm::new(&r, params).square().square();
            let chal_mtg = MontyForm::new(&challenges[i], params);
            match selector {
                0 => {
                    if r_4.retrieve() != challenges[i] {
                        Err(Error::InvalidProofForIndex(i as u32))
                    } else {
                        Ok(())
                    }
                }
                1 => {
                    if r_4.retrieve() != chal_mtg.neg().retrieve() {
                        Err(Error::InvalidProofForIndex(i as u32))
                    } else {
                        Ok(())
                    }
                }
                3 => {
                    if r_4.retrieve() != chal_mtg.neg().mul(&w_mtg).retrieve() {
                        Err(Error::InvalidProofForIndex(i as u32))
                    } else {
                        Ok(())
                    }
                }
                2 => {
                    if r_4.retrieve() != chal_mtg.mul(&w_mtg).retrieve() {
                        Err(Error::InvalidProofForIndex(i as u32))
                    } else {
                        Ok(())
                    }
                }
                _ => Err(Error::InvalidSelectorForIndex(selector, i as u32)),
            }
        });
        report_error_if_any!(res)
    }

    /// Generate a quadratic non-residue with Jacobi symbol as -1 from the transcript. The transcript is updated in the process.
    pub fn generate_qnr<D: Default + Update + ExtendableOutput, W: Write + AsRef<[u8]>>(
        modulus: &Modulus<MODULUS_LIMBS>,
        nonce: &[u8],
        transcript: &mut W,
    ) -> Uint<MODULUS_LIMBS> {
        transcript
            .write_all(b"proof-of-paillier-blum-modulus")
            .unwrap();
        transcript.write_all(&uint_le_bytes(&modulus.0)).unwrap();
        // Not hashing in MODULUS_LIMBS since it can change if proof generation and verification happen on different arch. (64 bit vs 32 bit)
        transcript
            .write_all(modulus.size_for_hashing().as_slice())
            .unwrap();
        transcript.write_all(nonce).unwrap();
        let mut c_bytes = vec![0; Uint::<MODULUS_LIMBS>::BYTES];
        let mut i = 0_u32;
        let mut w = None;
        while w.is_none() {
            transcript.write_all(i.to_le_bytes().as_slice()).unwrap();
            D::digest_xof(transcript.as_ref(), &mut c_bytes);
            let c = Uint::<MODULUS_LIMBS>::from_le_slice(&c_bytes);
            if modulus.is_greater_than(&c)
                && jacobi_symbol_vartime(c.clone(), modulus.0.clone()).is_minus_one()
            {
                w = Some(c.clone());
                break;
            }
            i += 1;
        }
        let w = w.unwrap();
        transcript.write_all(&uint_le_bytes(&w)).unwrap();
        w
    }

    fn generate_responses<const PRIME_LIMBS: usize>(
        w: &Uint<MODULUS_LIMBS>,
        challenges: &[Uint<MODULUS_LIMBS>; NUM_CHALLENGES],
        modulus: &Modulus<MODULUS_LIMBS>,
        p_mtg: MontyParams<PRIME_LIMBS>,
        q_mtg: MontyParams<PRIME_LIMBS>,
        p_inv: MontyForm<PRIME_LIMBS>,
    ) -> [(u8, Uint<MODULUS_LIMBS>); NUM_CHALLENGES]
    where
        Uint<PRIME_LIMBS>: Concat<Output = Uint<MODULUS_LIMBS>>,
    {
        let mut responses = [(0, Uint::<MODULUS_LIMBS>::ZERO); NUM_CHALLENGES];
        let (exp_mod_p_minus_1, exp_mod_q_minus_1) =
            exponents_for_sqrt_mod_blum_integer(p_mtg, q_mtg);
        let params = MontyParams::new_vartime(modulus.0);
        let w_mtg = MontyForm::new(w, params);
        cfg_iter_mut!(responses).enumerate().for_each(|(i, r)| {
            let mut selector = 0;
            let chal_mtg = MontyForm::new(&challenges[i], params);
            let fourth_root = fourth_root_mod_blum_integer_given_prime_factors_as_mtg_params_and_precomp::<
                PRIME_LIMBS,
                MODULUS_LIMBS,
            >(
                &challenges[i],
                &exp_mod_p_minus_1,
                &exp_mod_q_minus_1,
                p_inv,
                p_mtg,
                q_mtg,
            );
            if let Some(f) = fourth_root {
                *r = (selector, f);
            } else {
                selector = 1;
                let fourth_root = fourth_root_mod_blum_integer_given_prime_factors_as_mtg_params_and_precomp::<
                    PRIME_LIMBS,
                    MODULUS_LIMBS,
                >(
                    &chal_mtg.neg().retrieve(),
                    &exp_mod_p_minus_1,
                    &exp_mod_q_minus_1,
                    p_inv,
                    p_mtg,
                    q_mtg,
                );
                if let Some(f) = fourth_root {
                    *r = (selector, f);
                } else {
                    selector = 3;
                    let fourth_root = fourth_root_mod_blum_integer_given_prime_factors_as_mtg_params_and_precomp::<
                        PRIME_LIMBS,
                        MODULUS_LIMBS,
                    >(
                        &chal_mtg.neg().mul(&w_mtg).retrieve(),
                        &exp_mod_p_minus_1,
                        &exp_mod_q_minus_1,
                        p_inv,
                        p_mtg,
                        q_mtg,
                    );
                    if let Some(f) = fourth_root {
                        *r = (selector, f);
                    } else {
                        selector = 2;
                        let fourth_root = fourth_root_mod_blum_integer_given_prime_factors_as_mtg_params_and_precomp::<
                            PRIME_LIMBS,
                            MODULUS_LIMBS,
                        >(
                            &chal_mtg.mul(&w_mtg).retrieve(),
                            &exp_mod_p_minus_1,
                            &exp_mod_q_minus_1,
                            p_inv,
                            p_mtg,
                            q_mtg,
                        );
                        if let Some(f) = fourth_root {
                            *r = (selector, f);
                        } else {
                            panic!("this should never happen");
                        }
                    }
                }
            }
        });
        responses
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::{
        math::misc::is_3_mod_4,
        safegcd_nlimbs,
        util::{get_2048_bit_safe_primes, timing_info},
    };
    use crypto_bigint::{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_SQR_FREE: usize = 80;

            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_SQR_FREE,
                KAPPA
            );
            for _ in 0..$num_iters {
                let mut transcript = vec![];
                let start = Instant::now();
                let proof = ProofPaillierBlumModulus::<
                    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());

                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 = ProofPaillierBlumModulus::<
                    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 = 80;

        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 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 modulus = Modulus::<MODULUS_LIMBS>::new(&blum_primes);
        let bad_modulus = Modulus::<MODULUS_LIMBS>::new(&non_blum_primes);
        let nonce = b"123";

        let mut transcript = vec![];
        let proof = ProofPaillierBlumModulus::<
            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);
    }

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