confium_crypto_vss/
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
107fn generate_prime(bits: u32) -> BigUint {
108    let mut rng = OsRng;
109    loop {
110        let candidate = rng.gen_biguint(bits as u64);
111        if candidate < BigUint::from(2u32) {
112            continue;
113        }
114        let candidate = candidate | BigUint::one();
115        if miller_rabin(&candidate, 20) {
116            return candidate;
117        }
118    }
119}
120
121fn miller_rabin(n: &BigUint, rounds: u32) -> bool {
122    let two = BigUint::from(2u32);
123    let three = BigUint::from(3u32);
124    if n == &two || n == &three {
125        return true;
126    }
127    if (n & &BigUint::one()) == BigUint::from(0u32) || n < &three {
128        return false;
129    }
130
131    let one = BigUint::one();
132    let n_minus_one = n - &one;
133
134    let mut d = n_minus_one.clone();
135    let mut r: u32 = 0;
136    loop {
137        let test = &d & &one;
138        if test == BigUint::from(0u32) {
139            d >>= 1;
140            r += 1;
141        } else {
142            break;
143        }
144    }
145
146    let mut rng = OsRng;
147    'outer: for _ in 0..rounds {
148        let a = rng.gen_biguint_range(&two, &n_minus_one);
149        if a < two || a >= n_minus_one {
150            continue;
151        }
152        let mut x = a.modpow(&d, n);
153        if x == one || x == n_minus_one {
154            continue;
155        }
156        for _ in 0..r.saturating_sub(1) {
157            x = (&x * &x) % n;
158            if x == n_minus_one {
159                continue 'outer;
160            }
161        }
162        return false;
163    }
164    true
165}
166
167fn modinv_biguint(a: &BigUint, m: &BigUint) -> Option<BigUint> {
168    let a_int = a.to_bigint()?;
169    let m_int = m.to_bigint()?;
170    let result = modinv(&a_int, &m_int)?;
171    result.to_biguint()
172}
173
174fn modinv(a: &BigInt, m: &BigInt) -> Option<BigInt> {
175    let (g, x, _) = extended_gcd(a, m);
176    if g != BigInt::one() {
177        None
178    } else {
179        let r = &x % m;
180        if r.sign() == num_bigint::Sign::Minus {
181            Some(r + m)
182        } else {
183            Some(r)
184        }
185    }
186}
187
188fn extended_gcd(a: &BigInt, b: &BigInt) -> (BigInt, BigInt, BigInt) {
189    if b == &BigInt::zero() {
190        (a.clone(), BigInt::one(), BigInt::zero())
191    } else {
192        let (g, x1, y1) = extended_gcd(b, &(a % b));
193        (g, y1.clone(), x1 - (a / b) * &y1)
194    }
195}
196
197#[cfg(test)]
198mod tests {
199    use super::*;
200
201    fn make_keypair() -> PaillierKeypair {
202        generate_keypair(128)
203    }
204
205    fn random_below(n: &BigUint) -> BigUint {
206        let mut rng = OsRng;
207        loop {
208            let r = rng.gen_biguint(n.bits());
209            if r < *n && r > BigUint::from(0u32) {
210                return r;
211            }
212        }
213    }
214
215    #[test]
216    fn keypair_generates() {
217        let kp = make_keypair();
218        assert!(kp.public.n > BigUint::from(0u32));
219        assert_eq!(kp.public.g, &kp.public.n + &BigUint::one());
220    }
221
222    #[test]
223    fn encrypt_decrypt_round_trips() {
224        let kp = make_keypair();
225        let m = BigUint::from(42u32);
226        let r = random_below(&kp.public.n);
227        let c = encrypt(&kp.public, &m, &r).unwrap();
228        let m_dec = decrypt(&kp.private, &kp.public, &c).unwrap();
229        assert_eq!(m_dec, m);
230    }
231
232    #[test]
233    fn different_randomness_different_ciphertexts() {
234        let kp = make_keypair();
235        let m = BigUint::from(100u32);
236        let c1 = encrypt(&kp.public, &m, &random_below(&kp.public.n)).unwrap();
237        let c2 = encrypt(&kp.public, &m, &random_below(&kp.public.n)).unwrap();
238        assert_ne!(c1, c2);
239    }
240
241    #[test]
242    fn encrypt_message_geq_n_fails() {
243        let kp = make_keypair();
244        let r = random_below(&kp.public.n);
245        assert!(encrypt(&kp.public, &kp.public.n, &r).is_err());
246    }
247
248    #[test]
249    fn homomorphic_addition() {
250        let kp = make_keypair();
251        let m1 = BigUint::from(17u32);
252        let m2 = BigUint::from(25u32);
253        let c1 = encrypt(&kp.public, &m1, &random_below(&kp.public.n)).unwrap();
254        let c2 = encrypt(&kp.public, &m2, &random_below(&kp.public.n)).unwrap();
255        let c_sum = add(&kp.public, &c1, &c2);
256        let m_sum = decrypt(&kp.private, &kp.public, &c_sum).unwrap();
257        assert_eq!(m_sum, BigUint::from(42u32));
258    }
259
260    #[test]
261    fn homomorphic_addition_with_mod() {
262        let kp = make_keypair();
263        let m1 = BigUint::from(10u32);
264        let m2 = &kp.public.n - &BigUint::from(5u32);
265        let c1 = encrypt(&kp.public, &m1, &random_below(&kp.public.n)).unwrap();
266        let c2 = encrypt(&kp.public, &m2, &random_below(&kp.public.n)).unwrap();
267        let c_sum = add(&kp.public, &c1, &c2);
268        let m_sum = decrypt(&kp.private, &kp.public, &c_sum).unwrap();
269        assert_eq!(m_sum, BigUint::from(5u32));
270    }
271
272    #[test]
273    fn scalar_multiplication() {
274        let kp = make_keypair();
275        let m = BigUint::from(7u32);
276        let c = encrypt(&kp.public, &m, &random_below(&kp.public.n)).unwrap();
277        let c5 = scalar_mul(&kp.public, &c, &BigUint::from(5u32));
278        let m5 = decrypt(&kp.private, &kp.public, &c5).unwrap();
279        assert_eq!(m5, BigUint::from(35u32));
280    }
281
282    #[test]
283    fn scalar_mul_zero() {
284        let kp = make_keypair();
285        let m = BigUint::from(123u32);
286        let c = encrypt(&kp.public, &m, &random_below(&kp.public.n)).unwrap();
287        let c0 = scalar_mul(&kp.public, &c, &BigUint::from(0u32));
288        let m0 = decrypt(&kp.private, &kp.public, &c0).unwrap();
289        assert_eq!(m0, BigUint::from(0u32));
290    }
291
292    #[test]
293    fn public_key_consistent() {
294        let kp = make_keypair();
295        assert_eq!(kp.public.g, &kp.public.n + &BigUint::one());
296        assert_eq!(kp.public.n_squared, &kp.public.n * &kp.public.n);
297    }
298
299    #[test]
300    fn multiple_messages() {
301        let kp = make_keypair();
302        for m_val in [1u32, 100, 1000, 10000] {
303            let m = BigUint::from(m_val);
304            let c = encrypt(&kp.public, &m, &random_below(&kp.public.n)).unwrap();
305            let m_dec = decrypt(&kp.private, &kp.public, &c).unwrap();
306            assert_eq!(m_dec, m);
307        }
308    }
309
310    #[test]
311    fn additive_homomorphism_chained() {
312        let kp = make_keypair();
313        let c1 = encrypt(
314            &kp.public,
315            &BigUint::from(10u32),
316            &random_below(&kp.public.n),
317        )
318        .unwrap();
319        let c2 = encrypt(
320            &kp.public,
321            &BigUint::from(20u32),
322            &random_below(&kp.public.n),
323        )
324        .unwrap();
325        let c3 = encrypt(
326            &kp.public,
327            &BigUint::from(30u32),
328            &random_below(&kp.public.n),
329        )
330        .unwrap();
331        let c_sum = add(&kp.public, &c1, &c2);
332        let c_sum = add(&kp.public, &c_sum, &c3);
333        let m_sum = decrypt(&kp.private, &kp.public, &c_sum).unwrap();
334        assert_eq!(m_sum, BigUint::from(60u32));
335    }
336}
confium_crypto_vss/paillier.rs

confium_crypto_vss/
paillier.rs
