confium_tc/
paillier.rs

1//! Paillier homomorphic encryption.
2
3use num_bigint::{BigInt, BigUint, RandBigInt, ToBigInt};
4use num_integer::Integer;
5use num_traits::{One, Zero};
6use rand_core::OsRng;
7
8#[derive(Debug, Clone)]
9pub struct PaillierPublicKey {
10    pub n: BigUint,
11    pub n_squared: BigUint,
12    pub g: BigUint,
13}
14
15#[derive(Debug, Clone)]
16pub struct PaillierPrivateKey {
17    pub lambda: BigUint,
18    pub mu: BigUint,
19}
20
21#[derive(Debug, Clone)]
22pub struct PaillierKeypair {
23    pub public: PaillierPublicKey,
24    pub private: PaillierPrivateKey,
25}
26
27#[derive(Debug, thiserror::Error)]
28pub enum PaillierError {
29    #[error("invalid key parameters")]
30    InvalidKey,
31    #[error("encryption failed: {0}")]
32    Encryption(String),
33    #[error("decryption failed: {0}")]
34    Decryption(String),
35}
36
37pub fn generate_keypair(prime_bits: u32) -> PaillierKeypair {
38    loop {
39        let p = generate_prime(prime_bits);
40        let q = generate_prime(prime_bits);
41        if p == q {
42            continue;
43        }
44        let n = &p * &q;
45        let n_squared = &n * &n;
46
47        let p_minus_one = &p - &BigUint::one();
48        let q_minus_one = &q - &BigUint::one();
49        let gcd_val = p_minus_one.gcd(&q_minus_one);
50        let lambda = (&p_minus_one * &q_minus_one) / &gcd_val;
51
52        let g = &n + &BigUint::one();
53
54        let g_lambda = g.modpow(&lambda, &n_squared);
55        if g_lambda < BigUint::one() {
56            continue;
57        }
58        let l_val = (&g_lambda - &BigUint::one()) / &n;
59
60        let mu = match modinv_biguint(&lambda, &n) {
61            Some(m) => m,
62            None => continue,
63        };
64
65        let _ = l_val;
66        return PaillierKeypair {
67            public: PaillierPublicKey { n, n_squared, g },
68            private: PaillierPrivateKey { lambda, mu },
69        };
70    }
71}
72
73pub fn encrypt(
74    public: &PaillierPublicKey,
75    message: &BigUint,
76    randomness: &BigUint,
77) -> Result<BigUint, PaillierError> {
78    if message >= &public.n {
79        return Err(PaillierError::Encryption("message >= N".into()));
80    }
81    let g_m = public.g.modpow(message, &public.n_squared);
82    let r_n = randomness.modpow(&public.n, &public.n_squared);
83    Ok((&g_m * &r_n) % &public.n_squared)
84}
85
86pub fn decrypt(
87    private: &PaillierPrivateKey,
88    public: &PaillierPublicKey,
89    ciphertext: &BigUint,
90) -> Result<BigUint, PaillierError> {
91    let c_lambda = ciphertext.modpow(&private.lambda, &public.n_squared);
92    if c_lambda < BigUint::one() {
93        return Err(PaillierError::Decryption("c^λ underflow".into()));
94    }
95    let l_val = (&c_lambda - &BigUint::one()) / &public.n;
96    Ok((&l_val * &private.mu) % &public.n)
97}
98
99pub fn add(public: &PaillierPublicKey, ca: &BigUint, cb: &BigUint) -> BigUint {
100    (ca * cb) % &public.n_squared
101}
102
103pub fn scalar_mul(public: &PaillierPublicKey, c: &BigUint, k: &BigUint) -> BigUint {
104    c.modpow(k, &public.n_squared)
105}
106
107/// Generate a random probable prime (Miller-Rabin, 20 rounds).
108pub fn generate_prime(bits: u32) -> BigUint {
109    let mut rng = OsRng;
110    loop {
111        if bits < 2 {
112            continue;
113        }
114        let top = BigUint::one() << (bits - 1);
115        let candidate = rng.gen_biguint(bits as u64) | &top | BigUint::one();
116        if miller_rabin(&candidate, 20) {
117            return candidate;
118        }
119    }
120}
121
122/// Miller-Rabin probable-prime test.
123pub fn miller_rabin(n: &BigUint, rounds: u32) -> bool {
124    let two = BigUint::from(2u32);
125    let three = BigUint::from(3u32);
126    if n == &two || n == &three {
127        return true;
128    }
129    if (n & &BigUint::one()) == BigUint::from(0u32) || n < &three {
130        return false;
131    }
132
133    let one = BigUint::one();
134    let n_minus_one = n - &one;
135
136    let mut d = n_minus_one.clone();
137    let mut r: u32 = 0;
138    loop {
139        let test = &d & &one;
140        if test == BigUint::from(0u32) {
141            d >>= 1;
142            r += 1;
143        } else {
144            break;
145        }
146    }
147
148    let mut rng = OsRng;
149    'outer: for _ in 0..rounds {
150        let a = rng.gen_biguint_range(&two, &n_minus_one);
151        if a < two || a >= n_minus_one {
152            continue;
153        }
154        let mut x = a.modpow(&d, n);
155        if x == one || x == n_minus_one {
156            continue;
157        }
158        for _ in 0..r.saturating_sub(1) {
159            x = (&x * &x) % n;
160            if x == n_minus_one {
161                continue 'outer;
162            }
163        }
164        return false;
165    }
166    true
167}
168
169fn modinv_biguint(a: &BigUint, m: &BigUint) -> Option<BigUint> {
170    let a_int = a.to_bigint()?;
171    let m_int = m.to_bigint()?;
172    let result = modinv(&a_int, &m_int)?;
173    result.to_biguint()
174}
175
176fn modinv(a: &BigInt, m: &BigInt) -> Option<BigInt> {
177    let (g, x, _) = extended_gcd(a, m);
178    if g != BigInt::one() {
179        None
180    } else {
181        let r = &x % m;
182        if r.sign() == num_bigint::Sign::Minus {
183            Some(r + m)
184        } else {
185            Some(r)
186        }
187    }
188}
189
190fn extended_gcd(a: &BigInt, b: &BigInt) -> (BigInt, BigInt, BigInt) {
191    if b == &BigInt::zero() {
192        (a.clone(), BigInt::one(), BigInt::zero())
193    } else {
194        let (g, x1, y1) = extended_gcd(b, &(a % b));
195        (g, y1.clone(), x1 - (a / b) * &y1)
196    }
197}
198
199#[cfg(test)]
200mod tests {
201    use super::*;
202
203    fn make_keypair() -> PaillierKeypair {
204        generate_keypair(128)
205    }
206
207    fn random_below(n: &BigUint) -> BigUint {
208        let mut rng = OsRng;
209        loop {
210            let r = rng.gen_biguint(n.bits());
211            if r < *n && r > BigUint::from(0u32) {
212                return r;
213            }
214        }
215    }
216
217    #[test]
218    fn keypair_generates() {
219        let kp = make_keypair();
220        assert!(kp.public.n > BigUint::from(0u32));
221        assert_eq!(kp.public.g, &kp.public.n + &BigUint::one());
222    }
223
224    #[test]
225    fn encrypt_decrypt_round_trips() {
226        let kp = make_keypair();
227        let m = BigUint::from(42u32);
228        let r = random_below(&kp.public.n);
229        let c = encrypt(&kp.public, &m, &r).unwrap();
230        let m_dec = decrypt(&kp.private, &kp.public, &c).unwrap();
231        assert_eq!(m_dec, m);
232    }
233
234    #[test]
235    fn different_randomness_different_ciphertexts() {
236        let kp = make_keypair();
237        let m = BigUint::from(100u32);
238        let c1 = encrypt(&kp.public, &m, &random_below(&kp.public.n)).unwrap();
239        let c2 = encrypt(&kp.public, &m, &random_below(&kp.public.n)).unwrap();
240        assert_ne!(c1, c2);
241    }
242
243    #[test]
244    fn encrypt_message_geq_n_fails() {
245        let kp = make_keypair();
246        let r = random_below(&kp.public.n);
247        assert!(encrypt(&kp.public, &kp.public.n, &r).is_err());
248    }
249
250    #[test]
251    fn homomorphic_addition() {
252        let kp = make_keypair();
253        let m1 = BigUint::from(17u32);
254        let m2 = BigUint::from(25u32);
255        let c1 = encrypt(&kp.public, &m1, &random_below(&kp.public.n)).unwrap();
256        let c2 = encrypt(&kp.public, &m2, &random_below(&kp.public.n)).unwrap();
257        let c_sum = add(&kp.public, &c1, &c2);
258        let m_sum = decrypt(&kp.private, &kp.public, &c_sum).unwrap();
259        assert_eq!(m_sum, BigUint::from(42u32));
260    }
261
262    #[test]
263    fn homomorphic_addition_with_mod() {
264        let kp = make_keypair();
265        let m1 = BigUint::from(10u32);
266        let m2 = &kp.public.n - &BigUint::from(5u32);
267        let c1 = encrypt(&kp.public, &m1, &random_below(&kp.public.n)).unwrap();
268        let c2 = encrypt(&kp.public, &m2, &random_below(&kp.public.n)).unwrap();
269        let c_sum = add(&kp.public, &c1, &c2);
270        let m_sum = decrypt(&kp.private, &kp.public, &c_sum).unwrap();
271        assert_eq!(m_sum, BigUint::from(5u32));
272    }
273
274    #[test]
275    fn scalar_multiplication() {
276        let kp = make_keypair();
277        let m = BigUint::from(7u32);
278        let c = encrypt(&kp.public, &m, &random_below(&kp.public.n)).unwrap();
279        let c5 = scalar_mul(&kp.public, &c, &BigUint::from(5u32));
280        let m5 = decrypt(&kp.private, &kp.public, &c5).unwrap();
281        assert_eq!(m5, BigUint::from(35u32));
282    }
283
284    #[test]
285    fn scalar_mul_zero() {
286        let kp = make_keypair();
287        let m = BigUint::from(123u32);
288        let c = encrypt(&kp.public, &m, &random_below(&kp.public.n)).unwrap();
289        let c0 = scalar_mul(&kp.public, &c, &BigUint::from(0u32));
290        let m0 = decrypt(&kp.private, &kp.public, &c0).unwrap();
291        assert_eq!(m0, BigUint::from(0u32));
292    }
293
294    #[test]
295    fn public_key_consistent() {
296        let kp = make_keypair();
297        assert_eq!(kp.public.g, &kp.public.n + &BigUint::one());
298        assert_eq!(kp.public.n_squared, &kp.public.n * &kp.public.n);
299    }
300
301    #[test]
302    fn multiple_messages() {
303        let kp = make_keypair();
304        for m_val in [1u32, 100, 1000, 10000] {
305            let m = BigUint::from(m_val);
306            let c = encrypt(&kp.public, &m, &random_below(&kp.public.n)).unwrap();
307            let m_dec = decrypt(&kp.private, &kp.public, &c).unwrap();
308            assert_eq!(m_dec, m);
309        }
310    }
311
312    #[test]
313    fn additive_homomorphism_chained() {
314        let kp = make_keypair();
315        let c1 = encrypt(
316            &kp.public,
317            &BigUint::from(10u32),
318            &random_below(&kp.public.n),
319        )
320        .unwrap();
321        let c2 = encrypt(
322            &kp.public,
323            &BigUint::from(20u32),
324            &random_below(&kp.public.n),
325        )
326        .unwrap();
327        let c3 = encrypt(
328            &kp.public,
329            &BigUint::from(30u32),
330            &random_below(&kp.public.n),
331        )
332        .unwrap();
333        let c_sum = add(&kp.public, &c1, &c2);
334        let c_sum = add(&kp.public, &c_sum, &c3);
335        let m_sum = decrypt(&kp.private, &kp.public, &c_sum).unwrap();
336        assert_eq!(m_sum, BigUint::from(60u32));
337    }
338}
confium_tc/paillier.rs

confium_tc/
paillier.rs
