This repo contains the implementation of the Fully Homomorphic version of the AES-128 Cryptosystem in Rust using the TFHE-rs library. The execution does the following steps:

1. AES128-KeyExpand(fhe_key)
2. AES128-Encrypt(fhe_key, fhe_iv), AES128-Encrypt(fhe_key, fhe_iv + 1), ..., AES128-Encrypt(fhe_key, fhe_iv + n - 1)

As confirmed over email, the bounty did not specify plaintext input, so the implementation will only output the ciphertexts of the encrypted IVs, i.e. it will not do padding and XOR of plaintext (unlike complete AES modes).

Originally, I attempted the implementation using the integer/shortint primitives of the TFHE library; this early implementation can be found in src/int_fhe_aes.rs for reference and it follows the software implementation of AES (in src/plain_aes.rs). I made a few optimizations for FHE (e.g. for the multiplication in the finite field in FHE), but its performance was not satisfactory. While it has a potential room for more optimizations, e.g. more parallelism in some operations, it did not seem that much improvement can be gained from it.

I observed the smaller LUT operations etc. had a better performance. Therefore, I explored a bit more low-level approach using the boolean primitives of the TFHE library where FHE-booleans would represent bits in the AES-128 computation. I looked for a boolean logic circuit representing the AES-128 computation and came across Nigel Smart's page with MPC circuits which were created from VHDL sources. With that, each bit-level gate can be executed in parallel as long as the values on its input wires are available. I tried and it indeed seems to work much better (e.g. on my laptop, my new boolean circuit-based implementation would execute within a minute, whereas my original implementation took over ten minutes).

The usage is the following for computing N blocks in FHE is as follows:

// inputs
let n = 2;
let key = [0u8; 16];
let iv = [1u8; 16];
let (bool_client_key, bool_server_key) = tfhe::boolean::gen_keys();
// client
let fhekey = BoolFheAes::encrypt_key(&bool_client_key, &key);
let fheinput = BoolFheAes::encrypt_iv(&bool_client_key, &iv);

// server
let fhe_aes = BoolFheAes::new(bool_server_key);
fhe_aes.expand_key(fhekey);
let outputs = fhe_aes.aes_ctr_blocks(fheinput, n);

// client
let decrypted_outputs: Vec<[u8; 16]> = outputs.iter().map(|output| BoolFheAes::decrypt_output(&bool_client_key, output)).collect();

The Rust default stack size (2MB) may lead to a stack overflow issue, so please make sure to set RUST_MIN_STACK higher (e.g. 32MB).

The executable can be run as follows

RUST_MIN_STACK=33554432  cargo run --release -- -k $AES128_KEY -i $AES128_IV -n $NO_OF_OUTPUTS

For example:

RUST_MIN_STACK=33554432  cargo run --release -- -k 000102030405060708090a0b0c0d0e0f -i 00112233445566778899aabbccddeeff -n 2

For reference, the older (slow) implementation can be executed with -s.

As with the binary executable, make sure to set RUST_MIN_STACK higher:

RUST_MIN_STACK=33554432  cargo test --release

The older (slow) implementation tests can be executed as follows:

cargo test --release -- int --ignored