composite_modulus_proofs/
square_free.rs

1//! 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)
2//! 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
3//! per Lemma A.3 of the paper
4
5use crate::{
6    error::Error,
7    gcd_is_one::ProofGcdIsOne,
8    setup::{Modulus, Primes, PrimesWithPrecomp},
9};
10use ark_std::io::Write;
11use crypto_bigint::{modular::SafeGcdInverter, Concat, Odd, PrecomputeInverter, Split, Uint};
12use digest::{ExtendableOutput, Update};
13
14/// Proof that `N` is square-free. `NUM_CHALLENGES` depends on `ALPHA` and `KAPPA` as per the paper but can also
15/// be set independently as done in another protocol.
16#[derive(Debug, Clone, PartialEq, Eq)]
17pub struct ProofSquareFree<
18    const MODULUS_LIMBS: usize,
19    const NUM_CHALLENGES: usize,
20    const ALPHA: usize,
21    const KAPPA: usize,
22>(pub ProofGcdIsOne<MODULUS_LIMBS, NUM_CHALLENGES, ALPHA, KAPPA>);
23
24impl<
25        const MODULUS_LIMBS: usize,
26        const NUM_CHALLENGES: usize,
27        const ALPHA: usize,
28        const KAPPA: usize,
29    > ProofSquareFree<MODULUS_LIMBS, NUM_CHALLENGES, ALPHA, KAPPA>
30{
31    /// Create a proof that `N` is square-free. `transcript` is the proof transcript that is shared by
32    /// other sub-protocols as well which this is running as a sub-protocol of a larger protocol.
33    pub fn new<
34        D: Default + Update + ExtendableOutput,
35        W: Write + AsRef<[u8]>,
36        const PRIME_LIMBS: usize,
37        const MODULUS_UNSAT_LIMBS: usize,
38    >(
39        primes: Primes<PRIME_LIMBS>,
40        modulus: &Modulus<MODULUS_LIMBS>,
41        nonce: &[u8],
42        transcript: &mut W,
43    ) -> Result<Self, Error>
44    where
45        Uint<PRIME_LIMBS>: Concat<Output = Uint<MODULUS_LIMBS>>,
46        Odd<Uint<MODULUS_LIMBS>>:
47            PrecomputeInverter<Inverter = SafeGcdInverter<MODULUS_LIMBS, MODULUS_UNSAT_LIMBS>>,
48    {
49        Ok(Self(ProofGcdIsOne::new::<
50            D,
51            W,
52            PRIME_LIMBS,
53            MODULUS_UNSAT_LIMBS,
54        >(
55            modulus.0.as_ref(),
56            primes,
57            modulus,
58            nonce,
59            transcript,
60        )?))
61    }
62
63    /// Same as `Self::new` but returns the challenges used to create the proof. Useful when used with certain other protocols
64    pub fn new_and_return_challenges<
65        D: Default + Update + ExtendableOutput,
66        W: Write + AsRef<[u8]>,
67        const PRIME_LIMBS: usize,
68        const MODULUS_UNSAT_LIMBS: usize,
69    >(
70        primes: Primes<PRIME_LIMBS>,
71        modulus: &Modulus<MODULUS_LIMBS>,
72        nonce: &[u8],
73        transcript: &mut W,
74    ) -> Result<(Self, [Uint<MODULUS_LIMBS>; NUM_CHALLENGES]), Error>
75    where
76        Uint<PRIME_LIMBS>: Concat<Output = Uint<MODULUS_LIMBS>>,
77        Odd<Uint<MODULUS_LIMBS>>:
78            PrecomputeInverter<Inverter = SafeGcdInverter<MODULUS_LIMBS, MODULUS_UNSAT_LIMBS>>,
79    {
80        let (p, challenges) = ProofGcdIsOne::new_and_return_challenges::<
81            D,
82            W,
83            PRIME_LIMBS,
84            MODULUS_UNSAT_LIMBS,
85        >(modulus.0.as_ref(), primes, modulus, nonce, transcript)?;
86        Ok((Self(p), challenges))
87    }
88
89    /// Same as `Self::new` but takes the primes and some precomputation to make the proof generation is faster.
90    /// Use it if creating frequent proofs.
91    pub fn new_given_precomputation<
92        D: Default + Update + ExtendableOutput,
93        W: Write + AsRef<[u8]>,
94        const PRIME_LIMBS: usize,
95    >(
96        primes: PrimesWithPrecomp<PRIME_LIMBS, MODULUS_LIMBS>,
97        modulus: &Modulus<MODULUS_LIMBS>,
98        nonce: &[u8],
99        transcript: &mut W,
100    ) -> Result<Self, Error>
101    where
102        Uint<PRIME_LIMBS>: Concat<Output = Uint<MODULUS_LIMBS>>,
103        Uint<MODULUS_LIMBS>: Split<Output = Uint<PRIME_LIMBS>>,
104    {
105        let n_inv_p_minus_1 = primes.n_inv_p_minus_1.clone();
106        let n_inv_q_minus_1 = primes.n_inv_q_minus_1.clone();
107        Ok(Self(ProofGcdIsOne::new_given_x_inv_and_precomputation::<
108            D,
109            W,
110            PRIME_LIMBS,
111        >(
112            modulus.0.as_ref(),
113            &n_inv_p_minus_1,
114            &n_inv_q_minus_1,
115            primes,
116            modulus,
117            nonce,
118            transcript,
119        )?))
120    }
121
122    /// Same as `Self::new_given_precomputation` but returns the challenges used to create the proof. Useful when used with certain other protocols
123    pub fn new_given_precomputation_and_return_challenges<
124        D: Default + Update + ExtendableOutput,
125        W: Write + AsRef<[u8]>,
126        const PRIME_LIMBS: usize,
127    >(
128        primes: PrimesWithPrecomp<PRIME_LIMBS, MODULUS_LIMBS>,
129        modulus: &Modulus<MODULUS_LIMBS>,
130        nonce: &[u8],
131        transcript: &mut W,
132    ) -> Result<(Self, [Uint<MODULUS_LIMBS>; NUM_CHALLENGES]), Error>
133    where
134        Uint<PRIME_LIMBS>: Concat<Output = Uint<MODULUS_LIMBS>>,
135        Uint<MODULUS_LIMBS>: Split<Output = Uint<PRIME_LIMBS>>,
136    {
137        let n_inv_p_minus_1 = primes.n_inv_p_minus_1.clone();
138        let n_inv_q_minus_1 = primes.n_inv_q_minus_1.clone();
139        let (proof, challenges) =
140            ProofGcdIsOne::new_given_x_inv_and_precomputation_and_return_challenges::<
141                D,
142                W,
143                PRIME_LIMBS,
144            >(
145                modulus.0.as_ref(),
146                &n_inv_p_minus_1,
147                &n_inv_q_minus_1,
148                primes,
149                modulus,
150                nonce,
151                transcript,
152            )?;
153        Ok((Self(proof), challenges))
154    }
155
156    pub fn num_responses(&self) -> usize {
157        self.0.num_responses()
158    }
159
160    /// Verify the proof that `N` is square-free. `transcript` is the proof transcript that is shared by
161    /// other sub-protocols as well which this is running as a sub-protocol of a larger protocol.
162    pub fn verify<D: Default + Update + ExtendableOutput, W: Write + AsRef<[u8]>>(
163        &self,
164        modulus: &Modulus<MODULUS_LIMBS>,
165        nonce: &[u8],
166        transcript: &mut W,
167    ) -> Result<(), Error> {
168        self.0
169            .verify::<D, W>(modulus.0.as_ref(), modulus, nonce, transcript)
170    }
171
172    pub fn verify_and_return_challenges<
173        D: Default + Update + ExtendableOutput,
174        W: Write + AsRef<[u8]>,
175    >(
176        &self,
177        modulus: &Modulus<MODULUS_LIMBS>,
178        nonce: &[u8],
179        transcript: &mut W,
180    ) -> Result<((), [Uint<MODULUS_LIMBS>; NUM_CHALLENGES]), Error> {
181        self.0
182            .verify_and_return_challenges::<D, W>(modulus.0.as_ref(), modulus, nonce, transcript)
183    }
184}
185
186#[cfg(test)]
187mod tests {
188    use super::*;
189    use crate::{
190        gcd_is_one::num_challenges,
191        safegcd_nlimbs,
192        util::{get_1024_bit_primes, get_2048_bit_primes, timing_info},
193    };
194    use crypto_bigint::{U1024, U2048, U256, U64};
195    use rand_core::OsRng;
196    use sha3::Shake256;
197    use std::time::Instant;
198
199    macro_rules! check_given_primes {
200        ( $num_iters: ident, $prime_type:ident, $primes: ident ) => {
201            const KAPPA: usize = 128;
202            const ALPHA: usize = 65537;
203            const NUM_CHALLENGES: usize = num_challenges::<ALPHA, KAPPA>() as usize;
204            const PRIME_LIMBS: usize = $prime_type::LIMBS;
205            const PRIME_UNSAT_LIMBS: usize = safegcd_nlimbs!(Uint::<PRIME_LIMBS>::BITS as usize);
206            const MODULUS_LIMBS: usize = PRIME_LIMBS * 2;
207            const MODULUS_UNSAT_LIMBS: usize =
208                safegcd_nlimbs!(Uint::<MODULUS_LIMBS>::BITS as usize);
209
210            let modulus = Modulus::<MODULUS_LIMBS>::new(&$primes);
211            let primes_with_crt = PrimesWithPrecomp::from($primes.clone());
212            let nonce = b"123";
213
214            let mut prove_times = vec![];
215            let mut prove_crt_times = vec![];
216            let mut ver_times = vec![];
217
218            println!(
219                "Running {} iterations for {} bits prime",
220                $num_iters,
221                $prime_type::BITS
222            );
223            for _ in 0..$num_iters {
224                let mut transcript = vec![];
225                let start = Instant::now();
226                let proof = ProofSquareFree::<MODULUS_LIMBS, NUM_CHALLENGES, ALPHA, KAPPA>::new::<
227                    Shake256,
228                    _,
229                    PRIME_LIMBS,
230                    MODULUS_UNSAT_LIMBS,
231                >($primes.clone(), &modulus, nonce, &mut transcript)
232                .unwrap();
233                prove_times.push(start.elapsed());
234
235                assert_eq!(proof.num_responses(), NUM_CHALLENGES);
236
237                let mut transcript = vec![];
238                let start = Instant::now();
239                proof
240                    .verify::<Shake256, _>(&modulus, nonce, &mut transcript)
241                    .unwrap();
242                ver_times.push(start.elapsed());
243
244                let mut transcript = vec![];
245                let start = Instant::now();
246                let proof =
247                    ProofSquareFree::<MODULUS_LIMBS, NUM_CHALLENGES, ALPHA, KAPPA>::new_given_precomputation::<
248                        Shake256,
249                        _,
250                        PRIME_LIMBS,
251                    >(primes_with_crt.clone(), &modulus, nonce, &mut transcript)
252                    .unwrap();
253                prove_crt_times.push(start.elapsed());
254
255                assert_eq!(proof.num_responses(), NUM_CHALLENGES);
256
257                let mut transcript = vec![];
258                let start = Instant::now();
259                proof
260                    .verify::<Shake256, _>(&modulus, nonce, &mut transcript)
261                    .unwrap();
262                ver_times.push(start.elapsed());
263            }
264
265            println!("Proving time: {:?}", timing_info(prove_times));
266            println!("Proving time with CRT: {:?}", timing_info(prove_crt_times));
267            println!("Verification time: {:?}", timing_info(ver_times));
268
269            let mut same_primes = $primes.clone();
270            same_primes.q = same_primes.p;
271            let modulus_with_square = Modulus::<MODULUS_LIMBS>::new(&same_primes);
272
273            let mut transcript = vec![];
274            let proof = ProofSquareFree::<MODULUS_LIMBS, NUM_CHALLENGES, ALPHA, KAPPA>::new::<
275                Shake256,
276                _,
277                PRIME_LIMBS,
278                MODULUS_UNSAT_LIMBS,
279            >(
280                same_primes.clone(),
281                &modulus_with_square,
282                nonce,
283                &mut transcript,
284            )
285            .unwrap();
286
287            let mut transcript = vec![];
288            assert!(proof
289                .verify::<Shake256, _>(&modulus, nonce, &mut transcript)
290                .is_err());
291        };
292    }
293
294    #[test]
295    fn bad_proofs() {
296        const KAPPA: usize = 128;
297        const ALPHA: usize = 65537;
298        const NUM_CHALLENGES: usize = num_challenges::<ALPHA, KAPPA>() as usize;
299        const PRIME_LIMBS: usize = U64::LIMBS;
300        const MODULUS_LIMBS: usize = PRIME_LIMBS * 2;
301        const MODULUS_UNSAT_LIMBS: usize = safegcd_nlimbs!(Uint::<MODULUS_LIMBS>::BITS as usize);
302
303        let mut rng = OsRng::default();
304        let primes = Primes::<{ U64::LIMBS }>::new(&mut rng);
305        let nonce = b"123";
306
307        let mut same_primes = primes.clone();
308        same_primes.q = same_primes.p;
309        let modulus_with_square = Modulus::<MODULUS_LIMBS>::new(&same_primes);
310
311        let mut transcript = vec![];
312        let proof = ProofSquareFree::<MODULUS_LIMBS, NUM_CHALLENGES, ALPHA, KAPPA>::new::<
313            Shake256,
314            _,
315            PRIME_LIMBS,
316            MODULUS_UNSAT_LIMBS,
317        >(
318            same_primes.clone(),
319            &modulus_with_square,
320            nonce,
321            &mut transcript,
322        )
323        .unwrap();
324
325        let mut transcript = vec![];
326        assert!(proof
327            .verify::<Shake256, _>(&modulus_with_square, nonce, &mut transcript)
328            .is_err());
329    }
330
331    #[test]
332    fn proof() {
333        let mut rng = OsRng::default();
334        let primes = Primes::<{ U256::LIMBS }>::new(&mut rng);
335        let num_iters = 100;
336        check_given_primes!(num_iters, U256, primes);
337    }
338
339    #[test]
340    fn proof_with_1024_bit_primes() {
341        let (p, q) = get_1024_bit_primes();
342        let primes = Primes::from_primes(p, q);
343        let num_iters = 10;
344        check_given_primes!(num_iters, U1024, primes);
345    }
346
347    #[test]
348    fn proof_with_2048_bit_primes() {
349        let (p, q) = get_2048_bit_primes();
350        let primes = Primes::from_primes(p, q);
351        let num_iters = 10;
352        check_given_primes!(num_iters, U2048, primes);
353    }
354}
composite_modulus_proofs/square_free.rs

composite_modulus_proofs/
square_free.rs
