fancy_garbling/circuits/arithmetic/
exponentiation.rs

1use crate::{CrtBundle, FancyProj, HasModulus, circuit::Circuit};
2use core::marker::PhantomData;
3use swanky_channel::Channel;
4use swanky_error::Result;
5
6/// Given a [`CrtBundle`] `x` and constant exponent `c`, output `x^c`.
7///
8/// This uses projection gates to compute the exponentiation for each modulus in
9/// the CRT bundle.
10#[derive(Default)]
11pub struct ConstantExponentiation<'a>(PhantomData<&'a ()>);
12
13impl<'a> ConstantExponentiation<'a> {
14    /// Create a new [`ConstantExponentiation`] circuit.
15    pub fn new() -> Self {
16        Default::default()
17    }
18}
19
20impl<'a, F: FancyProj> Circuit<F> for ConstantExponentiation<'a>
21where
22    F::Item: 'a,
23{
24    type Input = (&'a CrtBundle<F::Item>, u32);
25    type Output = CrtBundle<F::Item>;
26
27    fn execute(
28        &self,
29        backend: &mut F,
30        inputs: Self::Input,
31        channel: &mut Channel,
32    ) -> Result<Self::Output> {
33        let (x, c) = inputs;
34        x.wires()
35            .iter()
36            .map(|x| {
37                let p = x.modulus();
38                let tab = (0..p)
39                    .map(|x| ((x as u64).pow(c) % p as u64) as u16)
40                    .collect::<Vec<_>>();
41                backend.proj(x, p, Some(tab), channel)
42            })
43            .collect::<Result<_>>()
44            .map(CrtBundle::new)
45    }
46}
47
48#[cfg(test)]
49mod test {
50    use crate::{
51        circuits::arithmetic::ConstantExponentiation,
52        dummy::{Dummy, DummyVal},
53        util::RngExt,
54    };
55    use rand::{Rng, thread_rng};
56
57    #[test]
58    fn constant_exponentiation() {
59        let mut rng = thread_rng();
60        let q = rng.gen_usable_composite_modulus();
61
62        for _ in 0..16 {
63            let x = rng.r#gen::<u16>() as u128 % q;
64            let c = rng.gen_range(2..10);
65            let x_input = DummyVal::to_crt(x, q);
66            let circuit = ConstantExponentiation::new();
67            let z = Dummy::eval(&circuit, (&x_input, c)).unwrap();
68            let output = DummyVal::from_crt(&z, q);
69
70            // Compute x^c mod q using modular arithmetic to avoid overflow
71            let mut expected = 1u128;
72            for _ in 0..c {
73                expected = (expected * x) % q;
74            }
75            assert_eq!(output, expected);
76        }
77    }
78}
fancy_garbling/circuits/arithmetic/exponentiation.rs

fancy_garbling/circuits/arithmetic/
exponentiation.rs
