#paillier #key #implementation #composite #cryptosystem #degree #public #classes

libpaillier

The Paillier cryptosystem is a public key crytosystem based on composite degree residuosity classes. Paillier ciphertexts are homorphic in that the can be added

3 unstable releases

new 0.2.1 Jul 21, 2021
0.2.0 Jul 14, 2021
0.1.0 May 25, 2021

#179 in Cryptography

Apache-2.0

24KB
360 lines

Paillier-rs

Crates.io Documentation License-Image minimum rustc 1.50 dependency status

An implementation of the Paillier cryptosystem based on P99.

Paillier supports homomorphic encryption and is computationally comparable to RSA.

This crate uses the unknown-order crate which allows switching the underlying big number implementation based on license preferences and performance. As such, this crate reexports unknown_order so consumers of this crate do not have to have a separate dependency.

Why this crate?

There are other implementations of Paillier in rust, but none of them offer everything I needed like implementing ops traits, or the flexibility to choose a big number backend. Also, some of them do not even have documentation which means users are expected to look at code which is not ideal, or are outdated and not current with 2018 or newer edition. My goal was to create a simple Paillier library with an easy-to-understand misuse resistant API.

This implementation has not been reviewed or audited. Use at your own risk.

Efforts have been made to mitigate some side channel attacks but ultimately there are many factors involved. For a good read, see Thomas Pornin's Why Constant-Time Crypto article.

Encryption

Encrypting messages requires that the messages be less than the composite modulus n. If messages > n, encrypt will return None. Paillier ciphertexts are probabilistic in that a random nonce is used during encryption, thus a message encrypts to multiple ciphertexts. This nonce can optionally be provided externally, or generated by the method. The nonce is returned to callers in case it is needed. The nonce is not needed for decryption.

Example Encryption/Decryption

use libpaillier::{
    unknown_order::BigNumber,
    *
};


fn main() {
    // Generate a new random key from two safe-primes
    let res = DecryptionKey::random();
    let sk = res.unwrap();
    let pk = EncryptionKey::from(&sk);

    let m = b"this is a test message";
    let res = pk.encrypt(m, None);

    let (c, _) = res.unwrap();
    let res = sk.decrypt(&c);
    let m1 = res.unwrap();
    assert_eq!(m1, m);

    // bad messages
    let nn1: BigNumber = pk.nn() + 1;
    let nn = pk.nn().to_bytes();
    let nn1_bytes = nn1.to_bytes();
    let bad_messages: [&[u8]; 3] = [b"", nn.as_slice(), nn1_bytes.as_slice()];

    for b in &bad_messages {
        let res = pk.encrypt(&b, None);
        assert!(res.is_none());
    }
}

Example Multiply Ciphertext

use libpaillier::{
    unknown_order::BigNumber,
    *
};

fn main() {
    let res = DecryptionKey::random();
    let sk = res.unwrap();
    let pk = EncryptionKey::from(&sk);
    let m1 = BigNumber::from(7);
    let m2 = BigNumber::from(6);

    let res1 = pk.encrypt(&m1.to_bytes(), None);

    let (c1, _) = res1.unwrap();
    
    // Multiply the ciphertext
    let res = pk.mul(&c1, &m2);
    assert!(res.is_some());
    let c2 = res.unwrap();
    let res = sk.decrypt(&c2);
    assert!(res.is_some());
    let bytes = res.unwrap();
    let m3 = BigNumber::from_slice(bytes.as_slice());
    // Prove homomorphic properties worked
    assert_eq!(m3, BigNumber::from(42));
}

Example Add Two Ciphertexts

use libpaillier::{
    unknown_order::BigNumber,
    *
};

fn main() {
    let res = DecryptionKey::random();
    let sk = res.unwrap();
    let pk = EncryptionKey::from(&sk);
    let m1 = BigNumber::from(7);
    let m2 = BigNumber::from(6);

    let res1 = pk.encrypt(&m1.to_bytes(), None);
    let res2 = pk.encrypt(&m2.to_bytes(), None);
    assert!(res1.is_some());
    assert!(res2.is_some());

    let (c1, _) = res1.unwrap();
    let (c2, _) = res2.unwrap();
    let res = pk.add(&c1, &c2);
    assert!(res.is_some());
    let c3 = res.unwrap();
    let res = sk.decrypt(&c3);
    assert!(res.is_some());
    let bytes = res.unwrap();
    let m3 = BigNumber::from_slice(bytes);
    assert_eq!(m3, BigNumber::from(13));
}

Proofs

Paillier has become more common in protocols like threshold ECDSA signing like GG20 and Lin17. When generating Paillier keys, these protocols use proofs that the modulus is square free. This crate includes this proof as a convenience and to provide a common implementation that uses reasonable parameters to achieve 128-bit security.

use libpaillier::{
    unknown_order::BigNumber,
    *
};


fn main() {
    let res = DecryptionKey::random();
    let sk = res.unwrap();
    let pk = EncryptionKey::from(&sk);
    
    // Commonly used proof for tECDSA
    let signing_key = k256::DecryptionKey::random(rand::rngs::OsRng::default());
    let verification_key = signing_key.public_key();
    let mut nonce = Vec::new();
    nonce.extend_from_slice(
        k256::AffinePoint::generator()
            .to_encoded_point(true)
            .as_bytes(),
    );
    nonce.extend_from_slice(
        &hex::decode("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F").unwrap(),
    );
    nonce.extend_from_slice(verification_key.as_affine().to_encoded_point(true).as_bytes());
    nonce.push(1u8);

    let res = ProofSquareFree::generate::<sha2::Sha256>(&sk, nonce.as_slice());
    assert!(res.is_some());
    let proof = res.unwrap();

    assert!(proof.verify::<sha2::Sha256>(&pk, nonce.as_slice()));

    let mut bytes = proof.to_bytes();
    let res = ProofSquareFree::from_bytes(bytes.as_slice());
    assert!(res.is_ok());
    let proof1 = res.unwrap();
    assert_eq!(proof1.to_bytes(), proof.to_bytes());

    bytes[0] = bytes[1];
    let res = ProofSquareFree::from_bytes(bytes.as_slice());
    assert!(res.is_err());
}

License

Apache License, Version 2.0

Contribution

Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in the work by you, as defined in the Apache-2.0 license, shall be licensed as above, without any additional terms or conditions.

Dependencies

~1–2.3MB
~51K SLoC