Homomorphic Encryption in Rust: Developing Secure Data Analysis

Homomorphic encryption allows computations to be performed on encrypted data without decrypting it first. This property is particularly useful for preserving privacy in data analysis.

In this article, we’ll walk through the development of homomorphic encryption using the Paillier cryptosystem in Rust, demonstrating a practical use case of securely calculating the sum of salaries.

Introduction to Homomorphic Cryptosystems

Homomorphic encryption schemes allow specific types of computations to be carried out on ciphertexts and obtain an encrypted result that, when decrypted, matches the result of operations performed on the plaintexts. There are several types of homomorphic encryption schemes:

Additive Homomorphic Encryption: Allows addition of encrypted values.
Multiplicative Homomorphic Encryption: Allows multiplication of encrypted values.
Fully Homomorphic Encryption: Allows both addition and multiplication on encrypted data.

The Paillier cryptosystem is an example of an additive homomorphic encryption scheme.

Understanding the Paillier Cryptosystem

The Paillier cryptosystem is an asymmetric encryption scheme known for its additive homomorphic properties. It allows the sum of encrypted values to be computed by simply multiplying the encrypted values, which when decrypted yields the sum of the original plaintexts.

Implementing the Paillier Cryptosystem in Rust

Key Generation

The first step in using the Paillier cryptosystem is to generate the necessary keys: the public key (used for encryption) and the private key (used for decryption).

extern crate num_bigint;
extern crate num_integer;
extern crate num_traits;
extern crate rand;
use num_bigint::{BigUint, RandBigInt, ToBigUint};
use num_integer::Integer;
use num_traits::{One, Zero};
use rand::{thread_rng, Rng};

// Larger prime numbers for p and q
const P: &str = "499";
const Q: &str = "547";

// Function to calculate LCM
fn lcm(a: &BigUint, b: &BigUint) -> BigUint {
    (a * b) / a.gcd(b)
}

fn main() {
    // Calculate n = p * q
    let p = BigUint::from_str_radix(P, 10).unwrap();
    let q = BigUint::from_str_radix(Q, 10).unwrap();
    let n = &p * &q;
    let n_squared = &n * &n;

    // Calculate lambda = lcm(p-1, q-1)
    let p_minus_1 = &p - BigUint::one();
    let q_minus_1 = &q - BigUint::one();
    let lambda = lcm(&p_minus_1, &q_minus_1);

    // Choose g such that it satisfies the conditions of the Paillier cryptosystem
    let g = &n + BigUint::one(); // Simple choice for g

    // Calculate mu = (L(g^lambda mod n^2))^(-1) mod n
    let g_lambda = g.modpow(&lambda, &n_squared);
    let l_g_lambda = (g_lambda.clone() - BigUint::one()) / &n;
    let mu = l_g_lambda.mod_inverse(&n).expect("Inverse should exist");

    println!("Public key (n, g): ({}, {})", n, g);
    println!("Private key (lambda, mu): ({}, {})", lambda, mu);
}

// Function to perform modular exponentiation (base^exp % modulus)
fn mod_exp(base: &BigUint, exp: &BigUint, modulus: &BigUint) -> BigUint {
    base.modpow(exp, modulus)
}

In the code above, we:

Generate large prime numbers p and q.
Calculate n = p * q and n^2.
Calculate lambda = lcm(p-1, q-1).
Choose g such that it satisfies the conditions of the Paillier cryptosystem.
Calculate mu which is the modular inverse of L(g^lambda mod n^2).

Encryption and Decryption

Next, we implement the encryption and decryption functions using the public and private keys generated.

// Function to generate a random BigUint below a given limit
fn gen_random_biguint_below(limit: &BigUint) -> BigUint {
    let mut rng = thread_rng();
    rng.gen_biguint_range(&BigUint::one(), limit) // Ensure r is not zero
}

// Function to encrypt a plaintext message using Paillier encryption
fn encrypt(message: &str, n: &BigUint, g: &BigUint) -> BigUint {
    let m = BigUint::from_str_radix(message, 10).unwrap(); // Convert message to BigUint
    let n_squared = n * n;
    let r = gen_random_biguint_below(n); // Random r where gcd(r, n) = 1

    // Encryption: c = g^m * r^n % n^2
    let gm = mod_exp(g, &m, &n_squared);
    let rn = mod_exp(&r, n, &n_squared);
    let ciphertext = (gm * rn) % &n_squared;
    ciphertext
}

Decryption

// L function: L(x) = (x - 1) / n
fn l_function(x: &BigUint, n: &BigUint) -> BigUint {
    (x - BigUint::one()) / n
}

// Function to decrypt a ciphertext back to plaintext using Paillier decryption
fn decrypt(ciphertext: &BigUint, n: &BigUint, lambda: &BigUint, mu: &BigUint) -> BigUint {
    let n_squared = n * n;
    let c_lambda = ciphertext.modpow(lambda, &n_squared); // c^lambda mod n^2
    let l_value = l_function(&c_lambda, n); // L(c^lambda mod n^2)
    let m = (l_value * mu) % n; // m = L(c^lambda mod n^2) * mu mod n
    m
}

Full Working Example

Here is the complete Rust code that ties everything together, demonstrating the entire process from key generation to encryption and decryption.

extern crate num_bigint;
extern crate num_integer;
extern crate num_traits;
extern crate rand;
use num_bigint::{BigUint, RandBigInt, ToBigUint};
use num_integer::Integer;
use num_traits::{One, Zero};
use rand::{thread_rng, Rng};

// Larger prime numbers for p and q
const P: &str = "499";
const Q: &str = "547";

// Function to calculate LCM
fn lcm(a: &BigUint, b: &BigUint) -> BigUint {
    (a * b) / a.gcd(b)
}
fn main() {
    // Calculate n = p * q
    let p = BigUint::from_str_radix(P, 10).unwrap();
    let q = BigUint::from_str_radix(Q, 10).unwrap();
    let n = &p * &q;
    let n_squared = &n * &n;

    // Calculate lambda = lcm(p-1, q-1)
    let p_minus_1 = &p - BigUint::one();
    let q_minus_1 = &q - BigUint::one();
    let lambda = lcm(&p_minus_1, &q_minus_1);

    // Choose g such that it satisfies the conditions of the Paillier cryptosystem
    let g = &n + BigUint::one(); // Simple choice for g

    // Calculate mu = (L(g^lambda mod n^2))^(-1) mod n
    let g_lambda = g.modpow(&lambda, &n_squared);
    let l_g_lambda = (g_lambda.clone() - BigUint::one()) / &n;
    let mu = l_g_lambda.mod_inverse(&n).expect("Inverse should exist");
    println!("Public key (n, g): ({}, {})", n, g);
    println!("Private key (lambda, mu): ({}, {})", lambda, mu);

    // Encrypt and decrypt a sample message
    let plaintext = "12345";
    let ciphertext = encrypt(plaintext, &n, &g);
    println!("Encrypted message: {}", ciphertext);
    let decrypted_message = decrypt(&ciphertext, &n, &lambda, &mu);
    println!("Decrypted message: {}", decrypted_message);
}

// Function to perform modular exponentiation (base^exp % modulus)
fn mod_exp(base: &BigUint, exp: &BigUint, modulus: &BigUint) -> BigUint {
    base.modpow(exp, modulus)
}

// Function to generate a random BigUint below a given limit
fn gen_random_biguint_below(limit: &BigUint) -> BigUint {
    let mut rng = thread_rng();
    rng.gen_biguint_range(&BigUint::one(), limit) // Ensure r is not zero
}

// Function to encrypt a plaintext message using Paillier encryption
fn encrypt(message: &str, n: &BigUint, g: &BigUint) -> BigUint {
    let m = BigUint::from_str_radix(message, 10).unwrap(); // Convert message to BigUint
    let n_squared = n * n;
    let r = gen_random_biguint_below(n); // Random r where gcd(r, n) = 1
    // Encryption: c = g^m * r^n % n^2
    let gm = mod_exp(g, &m, &n_squared);
    let rn = mod_exp(&r, n, &n_squared);
    let ciphertext = (gm * rn) % &n_squared;
    ciphertext
}

// L function: L(x) = (x - 1) / n
fn l_function(x: &BigUint, n: &BigUint) -> BigUint {
    (x - BigUint::one()) / n
}

// Function to decrypt a ciphertext back to plaintext using Paillier decryption
fn decrypt(ciphertext: &BigUint, n: &BigUint, lambda: &BigUint, mu: &BigUint) -> BigUint {
    let n_squared = n * n;
    let c_lambda = ciphertext.modpow(lambda, &n_squared); // c^lambda mod n^2
    let l_value = l_function(&c_lambda, n); // L(c^lambda mod n^2)
    let m = (l_value * mu) % n; // m = L(c^lambda mod n^2) * mu mod n
    m
}

Applying Paillier to a Real-World Example: Secure Salary Sum

Now that we have an understanding and implementation of the Paillier cryptosystem, let’s apply it to a real-world example. Imagine a scenario where a company wants to calculate the total sum of employees’ salaries without revealing individual salaries. The company can use Paillier homomorphic encryption to achieve this.

Steps to Implement

Encrypt Salaries: Each employee encrypts their salary using the public key.
Compute Encrypted Sum: The encrypted salaries are aggregated (multiplied) to compute the encrypted sum.
Decrypt the Sum: The company uses the private key to decrypt the total sum of salaries.

fn main() {
    // Calculate n = p * q
    let p = BigUint::from_str_radix(P, 10).unwrap();
    let q = BigUint::from_str_radix(Q, 10).unwrap();
    let n = &p * &q;
    let n_squared = &n * &n;

    // Calculate lambda = lcm(p-1, q-1)
    let p_minus_1 = &p - BigUint::one();
    let q_minus_1 = &q - BigUint::one();
    let lambda = lcm(&p_minus_1, &q_minus_1);

    // Choose g such that it satisfies the conditions of the Paillier cryptosystem
    let g = &n + BigUint::one(); // Simple choice for g

    // Calculate mu = (L(g^lambda mod n^2))^(-1) mod n
    let g_lambda = g.modpow(&lambda, &n_squared);
    let l_g_lambda = (g_lambda.clone() - BigUint::one()) / &n;
    let mu = l_g_lambda.mod_inverse(&n).expect("Inverse should exist");
    println!("Public key (n, g): ({}, {})", n, g);
    println!("Private key (lambda, mu): ({}, {})", lambda, mu);

    // Example salaries (encrypted by each employee)
    let salaries = vec!["50000", "60000", "70000"];

    // Encrypt the salaries
    let encrypted_salaries: Vec<BigUint> = salaries.iter()
        .map(|&salary| encrypt(salary, &n, &g))
        .collect();

    println!("Encrypted salaries: {:?}", encrypted_salaries);

    // Compute the encrypted sum of salaries
    let encrypted_sum = encrypted_salaries.iter().fold(BigUint::one(), |acc, x| (acc * x) % &n_squared);
    println!("Encrypted sum: {}", encrypted_sum);

    // Decrypt the sum of salaries
    let decrypted_sum = decrypt(&encrypted_sum, &n, &lambda, &mu);
    println!("Total sum of salaries (decrypted): {}", decrypted_sum);
}

Security Considerations

When implementing cryptographic systems, several security considerations must be taken into account:

Use Tested and Secure Algorithms: Always use well-established cryptographic algorithms and libraries that have been thoroughly tested and vetted by the security community. Avoid implementing your own cryptographic primitives unless absolutely necessary.
Large Key Sizes: The security of cryptographic algorithms often relies on the size of the keys used. Larger key sizes generally provide better security. In the case of the Paillier cryptosystem, using larger prime numbers for p and q increases the security of the encryption.
Randomness: The security of the encryption process in the Paillier cryptosystem relies on the quality of the random number generator used to select r. Ensure that a cryptographically secure random number generator is used.
Key Management: Proper key management practices are essential to maintaining the security of the cryptographic system. Ensure that private keys are stored securely and access is restricted to authorized users only.
Regular Audits and Updates: Regularly audit the cryptographic system for potential vulnerabilities and ensure that it is kept up to date with the latest security patches and best practices.

This example demonstrates how to implement homomorphic addition in Rust, preserving the privacy of individual inputs while allowing meaningful data analysis. This approach is invaluable in applications requiring data privacy, such as secure voting systems, confidential financial computations, and privacy-preserving data analytics.