Using Paillier Library

The Paillier cryptosystem is a probabilistic asymmetric encryption scheme commonly cited in the literature related to encrypted databases. The main reason for that is the additive homomorphic property offered by it. Given two plaintext messages $m_1$ and $m_2$, which can be encrypted ($E()$) and decrypted ($D()$) using the Paillier cryptosystem, it is possible to multiply the ciphertexts in order to obtain the sum of the plaintexts: $D(E(m_1) * E(m_2)) = m_1 + m_2$.

This property is useful to database systems because it allows the summation (e.g., SQL’s $SUM()$) of values in a column to be executed in a secure way. In fact, CryptDB implements this cryptosystem to allow this kind of operation.

Among the various implementations of the Paillier cryptosystem, I tried a C++ library called Paillier Library. It offers the features of key generation, encryption, decryption, homomorphic additon and import/export of keys and ciphertexts.

Although the library has only a few functions, I could not find a more step-by-step set of examples that might help get used to the library. For this reason, in this post I’ll give an overview on how to use the above features through samples. The complete samples are available at GitHub.

This post assumes the Paillier Library and its dependencies (e.g., GMP) are available on the system. This can be done either by installing the package in the official page or by just downloading the files paillier.h and paillier.c.

Generating, Exporting and Importing Keys

Since all the operations need either the public or the secret key, let’s start by creating those. After that, we export them to files to emulate someone sharing the public key with others.

First, we define the security parameter ($n$) that represents the number of bits of the modulus used in the cryptosytem:

```// Security parameter (number of bits of the modulus)
const long n = 1024;
```

This library is built on top of GMP and uses some of its data structures (e.g., $mpz\_t$), but wraps them using some structs. This is the case for the public and secret keys, which are presented as the structs $paillier\_pubkey\_t$ and $paillier\_prvkey\_t$. The $paillier\_keygen$ function then generates the keys by taking the number of bits of the modulo and random input from the file $/dev/urandom$:

```// Generate public and secret keys
paillier_pubkey_t* pubKey;
paillier_prvkey_t* secKey;
paillier_keygen(n, &pubKey, &secKey, paillier_get_rand_devurandom);
```

And this is all that is needed for generating the keys. After that, we can transform them to the hexadecimal notation (using the library’s functions $paillier\_pubkey\_to\_hex()$ and $paillier\_prvkey\_to\_hex()$) and export them to files:

```// Export keys to file
std::fstream secKeyFile("seckey.txt", std::fstream::out|std::fstream::trunc);
std::fstream pubKeyFile("pubkey.txt", std::fstream::out|std::fstream::trunc);

char* hexSecKey = paillier_prvkey_to_hex(secKey);
char* hexPubKey = paillier_pubkey_to_hex(pubKey);

secKeyFile << hexSecKey;
pubKeyFile << hexPubKey;
```

The file for the public key can then be given to others to allow encryption of messages which can be decrypted using the private key.

The steps to recover keys from a file are similar to the ones used to export them. First we read the files and then convert the keys from hexadecimal notation (using the functions $paillier\_pubkey\_from\_hex()$ and $paillier\_prvkey\_from\_hex()$):

```// Read public key from disk and initialize it
std::fstream pubKeyFile("pubkey.txt", std::fstream::in);
std::fstream secKeyFile("seckey.txt", std::fstream::in);

std::string hexPubKey;
std::string hexSecKey;
std::getline(pubKeyFile, hexPubKey);
std::getline(secKeyFile, hexSecKey);

paillier_pubkey_t* pubKey = paillier_pubkey_from_hex(&hexPubKey[0]);
paillier_prvkey_t* secKey = paillier_prvkey_from_hex(&hexSecKey[0], pubKey);
```

Encryption and Decryption

After generating the keys, we can use them to encrypt plaintext messages and decrypt ciphertexts. Paillier Library offers the $paillier\_plaintext\_t$ struct which will hold plaintexts, and the $paillier\_ciphertext\_t$ which will hold ciphertexts.

Suppose the first plaintext we want to encrypt is the integer $2$. The first step to do that is the initialization of the plaintext as follows:

```// Plaintext initialization
paillier_plaintext_t* m;
m = paillier_plaintext_from_ui(2);
```

The $paillier\_plaintext\_from\_ui()$ function is used for integers, but similar functions are available for array of bytes or strings.

Next, the encryption itself is done with the $paillier\_enc$ function, which also receives a pointer to where the result ciphertext should be stored (if it is $NULL$, then the functions allocates the ciphertext and return it), the public key, the number of bits of the security parameter and the randomness from $/dev/urandom$:

```// Encrypt the message
paillier_ciphertext_t* ctxt;
ctxt = paillier_enc(NULL, pubKey, m, paillier_get_rand_devurandom);
```

The decryption follows a similar pattern:

```// Decrypt the ciphertext
paillier_plaintext_t* dec;
dec = paillier_dec(NULL, pubKey, secKey, ctxt);
```

Exporting and Importing Ciphertexts

After creating a ciphertext, we might want to send it to someone else, like to the person who holds the secret key. Paillier Library supports exporting ciphertexts by provides the function $paillier\_ciphertext\_to\_bytes()$ to convert the ciphertext into bytes. The first parameter of this function is the length of the ciphertext to be exported. In the Paillier cryptosystem, the plaintext space is $Z_n$ and the ciphertext space is $Z_{n^2}$. This means that the length of the ciphertext is twice the length of the plaintext (hence the multiplication by 2 in the sample code). Since the length should be passed in bytes, we use the macro $PAILLIER\_BITS\_TO\_BYTES()$ provided by Paillier Library to make this conversion:

```std::fstream ctxt1File("ciphertext1.txt", std::fstream::out|std::fstream::trunc|std::fstream::binary);

// The length of the ciphertext is twice the length of the key
char* byteCtxt1 = (char*)paillier_ciphertext_to_bytes(PAILLIER_BITS_TO_BYTES(pubKey->bits)*2, ctxt1);

ctxt1File.write(byteCtxt1, PAILLIER_BITS_TO_BYTES(pubKey->bits)*2);
```

To import the ciphertext from a file, we do some similar steps:

```std::fstream ctxt1File("ciphertext1.txt", std::fstream::in|std::fstream::binary);

// The length of the ciphertext is twice the length of the key
char* byteCtxt1 = (char*)malloc(PAILLIER_BITS_TO_BYTES(pubKey->bits)*2);

paillier_ciphertext_t* ctxt1 = paillier_ciphertext_from_bytes((void*)byteCtxt1, PAILLIER_BITS_TO_BYTES(pubKey->bits)*2);
```

One of the best features of the Paillier cryptosystem is its homomorphic additive property. The Paillier Library provides the $paillier\_mul()$ function to multiply two ciphertexts, which, after decryption, will give us the sum of the corresponding plaintext messages ($D(E(m_1) * E(m_2)) = m_1 + m_2$). The parameters for the $paillier\_mul()$ are the public key, the ciphertext which will hold the result, and the two ciphertexts to be multiplied. To initialize the result ciphertext, we just create a encryption of zero ($0$) using the auxiliary function $paillier\_create\_enc\_zero()$:

```// Initialize the ciphertext that will hold the sum with an encryption of zero
paillier_ciphertext_t* encryptedSum = paillier_create_enc_zero();

// Sum the encrypted values by multiplying the ciphertexts
paillier_mul(pubKey, encryptedSum, ctxt1, ctxt2);
```

After this, the sum will be stored in the $encryptedSum$ ciphertext, which can be decrypted as explained before.

Printing Values

We might want to check the values of plaintext messsages and ciphertexts in any point of our programs, but the way to print it is not so straightforward. This is because they are represented with GMP’s $mpz\_t$ struct, so we should also use GMP’s way to print them with the $gmp\_printf()$ function:

```// Decrypt and print the ciphertext (encryptedSum)
paillier_plaintext_t* dec;
dec = paillier_dec(NULL, pubKey, secKey, encryptedSum);
gmp_printf("Decrypted sum: %Zd\n", dec);
```

Final Notes

This tutorial covered basic operations that can be done using Paillier Library. As always, the source code for all the samples is available on GitHub, and questions and other comments are welcome.