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