Paillier

Paillier#

The Paillier class implements the Paillier public-key encryption algorithm, whose security is based on the Decisional Composite Residuosity Assumption (DCRA).

class Paillier#

Creates a new Paillier instance.

Parameters:

  • bits (int) – Number of bits for the modulus. Primes are generated having half the bits. Default is 2048.

  • force (bool) – Argument to force computations with higher orders of numbers, irrespective of resultant performance.

Attention

The Paillier signature scheme has not been implemented yet, and hence, the sign and verify functions do not yield any result. Use the Paillier cryptosystem accordingly.

Introduction#

The Paillier cryptosystem is a probabilistic asymmetric encryption algorithm that is semantically secure under the decisional composite residuosity assumption. It is particularly known for its homomorphic properties, allowing operations to be performed on encrypted data without decrypting it. Specifically, Paillier supports both additive homomorphism and partial homomorphism, which is useful for secure computations on encrypted data.

Note

The implementation of Paillier cryptosystem in this module uses a simpler variant, recommended to faster computation time for implementation purposes. The details can be found here

Mathematical Details#

Paillier Key Generation#

The Paillier key generation process involves the following steps:

  1. Choose two large prime numbers: Two large prime numbers, \(p\) and \(q\), are chosen randomly.

  2. Compute the modulus: The modulus, \(n\), is computed as:

\[n = p \cdot q\]

  1. Compute the Carmichael’s totient: The Carmichael’s totient \(\lambda(n)\) is computed as:

\[\lambda(n) = \text{lcm}(p-1, q-1)\]

However, using the simplified version of the Paillier algorithm, we use:

\[\lambda(n) = \phi(n) = (p-1) \cdot (q-1)\]

  1. Choose the public key: A random integer \(g\) is selected such that its order is \(n^2\). The public key is then the pair \((n, g)\).

  2. Compute the private key: The private key \(\mu\) is computed as:

\[\mu = (L(g^\lambda \mod n^2))^{-1} \mod n\]

where \(L(x) = \frac {(x-1)}{n}\) is the L-function.

Paillier Encryption/Decryption Process#

  1. Encryption: The plaintext message, \(m\), is encrypted using the public key \((n, g)\) as follows:

\[c = g^m \cdot r^n \mod n^2\]

where \(r\) is a random integer chosen from the range \(1 < r < n\).

  1. Decryption: The ciphertext message, \(c\), is decrypted using the private key \((n, \lambda(n), \mu)\) as follows:

\[m = L(c^\lambda \mod n^2) \cdot \mu \mod n\]

where \(L(x)\) is the L-function, defined as \(L(x) = \frac {(x-1)}{n}\).

Paillier Homomorphic Property#

Paillier is additively homomorphic, meaning that given two ciphertexts \(c_1\) and \(c_2\) of messages \(m_1\) and \(m_2\), the following holds:

\[c_1 \cdot c_2 \mod n^2 = g^{m_1 + m_2} \cdot r^n \mod n^2\]

This allows for the addition of encrypted messages without decrypting them.

Usage#

# Example usage of Paillier to encrypt, decrypt, and perform homomorphic addition
from cryptosystems import Paillier
cipher = Paillier()
public_key, private_key = cipher.generate_keys()  # Generate Paillier keys
ciphertext = cipher.encrypt(42, public_key)
print(ciphertext)  # Encrypted form of 42
plaintext = cipher.decrypt(ciphertext, private_key)
print(plaintext)  # 42
ciphertext2 = cipher.encrypt(58, public_key)
result = cipher.homomorphic_add(ciphertext, ciphertext2, public_key)
print(result)  # Encrypted form of 100 (42 + 58)
print(cipher.decrypt(result, private_key))  # 100

Methods#

generate_keypair() → tuple#

Generates a new Paillier key pair, in the form \((n, g)\) for the public key and \((n, y, u)\) for the private key.

Returns:

A tuple containing the public key and private key.

Return type:

tuple

encrypt(plaintext: int | str | bytes, public_key: tuple) → int#

Encrypts the given plaintext using the Paillier algorithm and returns the ciphertext.

Parameters:

  • plaintext (int | str | bytes) – The plaintext message to be encrypted.

  • public_key (tuple) – The public key used for encryption, in the form \((n, g)\).

Returns:

The encrypted ciphertext.

Return type:

int

decrypt(ciphertext: int, private_key: tuple, return_type: str)#

Decrypts the given ciphertext using the Paillier algorithm and returns the deciphered plaintext.

Parameters:

  • ciphertext (int) – The ciphertext message to be decrypted.

  • private_key (tuple) – The private key used for decryption, in the form \((n, y, u)\).

Returns:

The decrypted plaintext.

Return type:

int

homomorphic_add(ciphertext1: int, ciphertext2: int, public_key: tuple) → int#

Adds two ciphertexts together using the homomorphic properties of the Paillier algorithm.

Parameters:

  • ciphertext1 (int) – The first ciphertext message to be added.

  • ciphertext2 (int) – The second ciphertext message to be added.

  • public_key (tuple) – The public key used for encryption, in the form \((n, g)\).

Returns:

The resulting ciphertext of the sum of the plaintexts.

Return type:

int

Attention

Below functions are not implemented yet. Documentation is created only for reference.

sign(message: int | str | bytes, private_key: tuple) → int#

Signs the given message using the Paillier algorithm and returns the signature.

Parameters:

  • message (int | str | bytes) – The plaintext message to be signed.

  • private_key (tuple) – The private key used for signing, the form \((n, y, u)\).

Returns:

The signature (int) and the SHA256 hash (bytes) of the message.

Return type:

int

verify(signature: int, signature: (int | str | bytes), message_hash: bytes, public_key: tuple) → bool#

Verifies the given signature using the Paillier algorithm and returns True or False.

Parameters:

  • signature (int) – The signature to be verified.

  • message (int | str | bytes) – The message whose signature is to be verified.

  • public_key (tuple) – The public key used for verification, in the form \((n, g)\).

Returns:

True or False, the result of whether the signature is valid.

Return type:

bool

References#