FHE Compression

[RasoulAM]

Zama Bounty Program: FHE Compression

Bounty type:

major_bounty

Category:

Engineering + Research

Overview:

Implementation and integration of FHE Compression for LWE ciphertexts into TFHE-rs

Description:

We implement the compression technique that was proposed in this paper. Using this technique, LWE ciphertexts are converted into ciphertexts of an additive scheme, such as Paillier. This will result in a significant size reduction. The server performs compression before it sends the ciphertexts to the client. The client performs a modified decryption to obtain the correct plaintext result. To enable this, we generate a compression key for the server, and a modified decryption key for the client.
Compression is possible for both a single LWE ciphertext, and a vector of LWE ciphertexts.

We will use the appropriate additive encryption scheme to achieve maximum compression. One potential library which implements Paillier in Rust is rust-paillier but we will use the library which provides the best performance.

In the final product, a user should be able to run the following code, where compression happens on the server, and a modified decryption is done by the client.

use tfhe::boolean::prelude::*;

fn main() {
    // We generate a set of client/server keys, using the default parameters:
    // We add a parameter specifying whether the server should be able to compress or not
    // in which case, the compression key will be included in the server_key, and the 
    // modified decryption key will be included in the client_key
    let compress = true;
    let (client_key, server_key) = gen_keys(compress);

    // We use the client secret key to encrypt two messages:
    let ct_1 = client_key.encrypt(true);
    let ct_2 = client_key.encrypt(false);

    // We use the server public key to execute some operations:
    let ct_3 = server_key.nand(&ct_1, &ct_2);
    let ct_4 = server_key.nand(&ct_2, &ct_3);

    // The server compresses the ciphertext using the server_key
    let ct_3_compressed = server_key.compress(&ct_3);

    // We use the client_key to perform a modified decryption of the output
    let output = client_key.decrypt_modified(&ct_3_compressed);

    // The server can also compress a vector of ciphertexts into the same additive ciphertext
    let ct_vec = vec![&ct_3, &ct_4];
    let ct_vec_compressed = server_key.compress_batched(&ct_vec);

    // We use the client_key to perform a modified decryption of the output
    let output_vec = client_key.decrypt_batched_modified(&ct_vec_compressed);

}

Library targeted:

TFHE-rs

Reward:

16000 Euros

Related links and reference:

• https://arxiv.org/abs/2303.09043
• https://github.com/RasoulAM/CompressLWE
• https://github.com/mortendahl/rust-paillier

[aquint-zama]

postponed as not sure it will be outsourced