scicrypt_he/cryptosystems/
paillier.rs

1//! Here is an example of how to generates a key pair and encrypt a plaintext integer using the Paillier public key.
2//! ```
3//! use scicrypt_traits::randomness::GeneralRng;
4//! use scicrypt_he::cryptosystems::paillier::Paillier;
5//! use scicrypt_traits::security::BitsOfSecurity;
6//! use scicrypt_traits::cryptosystems::{AsymmetricCryptosystem, EncryptionKey};
7//! use scicrypt_bigint::UnsignedInteger;
8//! use rand_core::OsRng;
9//!
10//! let mut rng = GeneralRng::new(OsRng);
11//! let paillier = Paillier::setup(&BitsOfSecurity::ToyParameters);
12//! let (public_key, secret_key) = paillier.generate_keys(&mut rng);
13//! let ciphertext = public_key.encrypt(&UnsignedInteger::from(5), &mut rng);
14//! ```
15use scicrypt_bigint::UnsignedInteger;
16use scicrypt_numbertheory::gen_rsa_modulus;
17use scicrypt_traits::cryptosystems::{
18    Associable, AsymmetricCryptosystem, DecryptionKey, EncryptionKey,
19};
20use scicrypt_traits::homomorphic::HomomorphicAddition;
21use scicrypt_traits::randomness::GeneralRng;
22use scicrypt_traits::randomness::SecureRng;
23use scicrypt_traits::security::BitsOfSecurity;
24use serde::{Deserialize, Serialize};
25
26/// The Paillier cryptosystem.
27#[derive(Copy, Clone)]
28pub struct Paillier {
29    modulus_size: u32,
30}
31
32/// Public key for the Paillier cryptosystem.
33#[derive(PartialEq, Eq, Debug, Serialize, Deserialize, Clone)]
34pub struct PaillierPK {
35    /// Public modulus n for encryption
36    pub n: UnsignedInteger,
37    /// Public generator g for encryption
38    pub g: UnsignedInteger,
39}
40/// Decryption key for the Paillier cryptosystem.
41pub struct PaillierSK {
42    lambda: UnsignedInteger,
43    mu: UnsignedInteger,
44}
45
46/// Ciphertext of the Paillier cryptosystem, which is additively homomorphic.
47#[derive(PartialEq, Eq, Debug, Serialize, Deserialize, Clone)]
48pub struct PaillierCiphertext {
49    /// Encrypted message (Ciphertext)
50    pub c: UnsignedInteger,
51}
52
53impl Associable<PaillierPK> for PaillierCiphertext {}
54
55impl AsymmetricCryptosystem for Paillier {
56    type PublicKey = PaillierPK;
57    type SecretKey = PaillierSK;
58
59    fn setup(security_param: &BitsOfSecurity) -> Self {
60        Paillier {
61            modulus_size: security_param.to_public_key_bit_length(),
62        }
63    }
64
65    /// Generates a fresh Paillier keypair.
66    /// ```
67    /// # use scicrypt_traits::randomness::GeneralRng;
68    /// # use scicrypt_he::cryptosystems::paillier::Paillier;
69    /// # use scicrypt_traits::security::BitsOfSecurity;
70    /// # use scicrypt_traits::cryptosystems::AsymmetricCryptosystem;
71    /// # use rand_core::OsRng;
72    /// let mut rng = GeneralRng::new(OsRng);
73    /// let paillier = Paillier::setup(&BitsOfSecurity::ToyParameters);
74    /// let (public_key, secret_key) = paillier.generate_keys(&mut rng);
75    /// ```
76    fn generate_keys<R: SecureRng>(&self, rng: &mut GeneralRng<R>) -> (PaillierPK, PaillierSK) {
77        let (n, lambda) = gen_rsa_modulus(self.modulus_size, rng);
78
79        let g = n.clone() + 1;
80        let mu = (lambda.clone() % &n).invert(&n).unwrap();
81
82        (PaillierPK { n, g }, PaillierSK { lambda, mu })
83    }
84}
85
86impl EncryptionKey for PaillierPK {
87    type Input = UnsignedInteger;
88    type Plaintext = UnsignedInteger;
89    type Ciphertext = PaillierCiphertext;
90    type Randomness = UnsignedInteger;
91
92    fn encrypt_without_randomness(&self, plaintext: &Self::Plaintext) -> Self::Ciphertext {
93        let n_squared = self.n.square();
94        PaillierCiphertext {
95            c: self.g.pow_mod(plaintext, &n_squared),
96        }
97    }
98
99    fn randomize<R: SecureRng>(
100        &self,
101        ciphertext: Self::Ciphertext,
102        rng: &mut GeneralRng<R>,
103    ) -> Self::Ciphertext {
104        let n_squared = self.n.square();
105        let r = UnsignedInteger::random_below(&n_squared, rng);
106
107        self.randomize_with(ciphertext, &r)
108    }
109
110    fn randomize_with(
111        &self,
112        ciphertext: Self::Ciphertext,
113        randomness: &Self::Randomness,
114    ) -> Self::Ciphertext {
115        let n_squared = self.n.square();
116        let randomizer = randomness.pow_mod(&self.n, &n_squared);
117
118        PaillierCiphertext {
119            c: (&ciphertext.c * &randomizer) % &n_squared,
120        }
121    }
122}
123
124impl DecryptionKey<PaillierPK> for PaillierSK {
125    /// Decrypts a rich Paillier ciphertext using the secret key.
126    /// ```
127    /// # use scicrypt_traits::randomness::GeneralRng;
128    /// # use scicrypt_he::cryptosystems::paillier::Paillier;
129    /// # use scicrypt_traits::security::BitsOfSecurity;
130    /// # use scicrypt_traits::cryptosystems::{AsymmetricCryptosystem, EncryptionKey, DecryptionKey};
131    /// # use scicrypt_bigint::UnsignedInteger;
132    /// # use rand_core::OsRng;
133    /// # let mut rng = GeneralRng::new(OsRng);
134    /// # let paillier = Paillier::setup(&BitsOfSecurity::ToyParameters);
135    /// # let (public_key, secret_key) = paillier.generate_keys(&mut rng);
136    /// # let ciphertext = public_key.encrypt(&UnsignedInteger::from(5), &mut rng);
137    /// println!("The decrypted message is {}", secret_key.decrypt(&ciphertext));
138    /// // Prints: "The decrypted message is 5".
139    /// ```
140    fn decrypt_raw(
141        &self,
142        public_key: &PaillierPK,
143        ciphertext: &PaillierCiphertext,
144    ) -> UnsignedInteger {
145        let n_squared = public_key.n.square();
146
147        let mut inner = ciphertext.c.pow_mod(&self.lambda, &n_squared);
148        inner -= 1;
149        inner = inner / &public_key.n;
150        inner = &inner * &self.mu;
151
152        inner % &public_key.n
153    }
154
155    fn decrypt_identity_raw(
156        &self,
157        public_key: &PaillierPK,
158        ciphertext: &<PaillierPK as EncryptionKey>::Ciphertext,
159    ) -> bool {
160        // TODO: This can be optimized
161        self.decrypt_raw(public_key, ciphertext).is_zero_leaky()
162    }
163}
164
165impl HomomorphicAddition for PaillierPK {
166    fn add(
167        &self,
168        ciphertext_a: &Self::Ciphertext,
169        ciphertext_b: &Self::Ciphertext,
170    ) -> Self::Ciphertext {
171        PaillierCiphertext {
172            c: (&ciphertext_a.c * &ciphertext_b.c) % &self.n.square(),
173        }
174    }
175
176    fn mul_constant(&self, ciphertext: &Self::Ciphertext, input: &Self::Input) -> Self::Ciphertext {
177        let modulus = self.n.square();
178
179        PaillierCiphertext {
180            c: ciphertext.c.pow_mod(input, &modulus),
181        }
182    }
183
184    fn sub(
185        &self,
186        ciphertext_a: &Self::Ciphertext,
187        ciphertext_b: &Self::Ciphertext,
188    ) -> Self::Ciphertext {
189        let modulus = self.n.square();
190        PaillierCiphertext {
191            c: (&ciphertext_a.c * &ciphertext_b.c.clone().invert(&modulus).unwrap()) % &modulus,
192        }
193    }
194
195    fn add_constant(
196        &self,
197        ciphertext: &Self::Ciphertext,
198        constant: &Self::Plaintext,
199    ) -> Self::Ciphertext {
200        let modulus = self.n.square();
201        PaillierCiphertext {
202            c: (&ciphertext.c * &self.g.pow_mod(constant, &modulus)) % &modulus,
203        }
204    }
205
206    fn sub_constant(
207        &self,
208        ciphertext: &Self::Ciphertext,
209        constant: &Self::Plaintext,
210    ) -> Self::Ciphertext {
211        let modulus = self.n.square();
212        PaillierCiphertext {
213            c: (&ciphertext.c * &self.g.pow_mod(constant, &modulus).invert(&modulus).unwrap())
214                % &modulus,
215        }
216    }
217}
218
219#[cfg(test)]
220mod tests {
221    use crate::cryptosystems::paillier::Paillier;
222    use rand_core::OsRng;
223    use scicrypt_bigint::UnsignedInteger;
224    use scicrypt_traits::cryptosystems::{
225        Associable, AsymmetricCryptosystem, DecryptionKey, EncryptionKey,
226    };
227    use scicrypt_traits::randomness::GeneralRng;
228    use scicrypt_traits::security::BitsOfSecurity;
229
230    #[test]
231    fn test_encrypt_decrypt() {
232        let mut rng = GeneralRng::new(OsRng);
233
234        let paillier = Paillier::setup(&BitsOfSecurity::ToyParameters);
235        let (pk, sk) = paillier.generate_keys(&mut rng);
236
237        let ciphertext = pk.encrypt(&UnsignedInteger::from(15u64), &mut rng);
238
239        assert_eq!(UnsignedInteger::from(15u64), sk.decrypt(&ciphertext));
240    }
241
242    #[test]
243    fn test_encrypt_decrypt_identity() {
244        let mut rng = GeneralRng::new(OsRng);
245
246        let paillier = Paillier::setup(&BitsOfSecurity::ToyParameters);
247        let (pk, sk) = paillier.generate_keys(&mut rng);
248
249        let ciphertext = pk.encrypt(&UnsignedInteger::from(0), &mut rng);
250
251        assert!(sk.decrypt_identity(&ciphertext));
252    }
253
254    #[test]
255    fn test_homomorphic_add() {
256        let mut rng = GeneralRng::new(OsRng);
257
258        let paillier = Paillier::setup(&BitsOfSecurity::ToyParameters);
259        let (pk, sk) = paillier.generate_keys(&mut rng);
260
261        let ciphertext_a = pk.encrypt(&UnsignedInteger::from(7u64), &mut rng);
262        let ciphertext_b = pk.encrypt(&UnsignedInteger::from(7u64), &mut rng);
263        let ciphertext_twice = &ciphertext_a + &ciphertext_b;
264
265        assert_eq!(UnsignedInteger::from(14u64), sk.decrypt(&ciphertext_twice));
266    }
267
268    #[test]
269    fn test_homomorphic_sub() {
270        let mut rng = GeneralRng::new(OsRng);
271
272        let paillier = Paillier::setup(&BitsOfSecurity::ToyParameters);
273        let (pk, sk) = paillier.generate_keys(&mut rng);
274
275        let ciphertext_a = pk.encrypt(&UnsignedInteger::from(7), &mut rng);
276        let ciphertext_b = pk.encrypt(&UnsignedInteger::from(5), &mut rng);
277        let ciphertext_res = &ciphertext_a - &ciphertext_b;
278
279        assert_eq!(UnsignedInteger::from(2), sk.decrypt(&ciphertext_res));
280    }
281
282    #[test]
283    fn test_homomorphic_scalar_mul() {
284        let mut rng = GeneralRng::new(OsRng);
285
286        let paillier = Paillier::setup(&BitsOfSecurity::ToyParameters);
287        let (pk, sk) = paillier.generate_keys(&mut rng);
288
289        let ciphertext = pk.encrypt(&UnsignedInteger::from(9u64), &mut rng);
290        let ciphertext_twice = &ciphertext * &UnsignedInteger::from(16u64);
291
292        assert_eq!(UnsignedInteger::from(144u64), sk.decrypt(&ciphertext_twice));
293    }
294
295    #[test]
296    fn test_homomorphic_add_constant() {
297        let mut rng = GeneralRng::new(OsRng);
298
299        let paillier = Paillier::setup(&BitsOfSecurity::ToyParameters);
300        let (pk, sk) = paillier.generate_keys(&mut rng);
301
302        let ciphertext = pk.encrypt(&UnsignedInteger::from(7), &mut rng);
303        let ciphertext_res = &ciphertext + &UnsignedInteger::from(5);
304
305        assert_eq!(UnsignedInteger::from(12), sk.decrypt(&ciphertext_res));
306    }
307
308    #[test]
309    fn test_homomorphic_sub_constant() {
310        let mut rng = GeneralRng::new(OsRng);
311
312        let paillier = Paillier::setup(&BitsOfSecurity::ToyParameters);
313        let (pk, sk) = paillier.generate_keys(&mut rng);
314
315        let ciphertext = pk.encrypt(&UnsignedInteger::from(7), &mut rng);
316        let ciphertext_res = &ciphertext - &UnsignedInteger::from(5);
317
318        assert_eq!(UnsignedInteger::from(2), sk.decrypt(&ciphertext_res));
319    }
320
321    #[test]
322    fn test_randomize() {
323        let mut rng = GeneralRng::new(OsRng);
324
325        let paillier = Paillier::setup(&BitsOfSecurity::ToyParameters);
326        let (pk, sk) = paillier.generate_keys(&mut rng);
327
328        let ciphertext = pk.encrypt_raw(&UnsignedInteger::from(21), &mut rng);
329        let ciphertext_randomized = pk.randomize(ciphertext.clone(), &mut rng);
330
331        assert_ne!(ciphertext, ciphertext_randomized);
332
333        assert_eq!(
334            UnsignedInteger::from(21),
335            sk.decrypt(&ciphertext_randomized.associate(&pk))
336        );
337    }
338}
scicrypt_he/cryptosystems/paillier.rs

scicrypt_he/cryptosystems/
paillier.rs
