Implement a Fully Homomorphic Version of the AES-128 Cryptosystem using TFHE-rs

[zaccherinij]

Overview

The goal of this bounty is to implement a homomorphic version of the AES-128 cryptosystem using the TFHE-rs library. The primary focus of the implementation should be on performance optimization. The implementation is expected to consist of two main blocks: KeyExpansion and Encryption/Decryption. This split is motivated by the possibility of performing key expansion as an offline phase, which may not always be required for all use cases.

You are encouraged to utilize recent research results and optimization techniques. If new cryptographic primitives or parameters are introduced, they must ensure:

• A failure probability for operations lower than 2^-64.
• A security level of at least 2^128.

Alternatively, you may focus on achieving the fastest possible implementation using the existing parameter sets provided in TFHE-rs. If you decide to use the WoPBS primitives, the parameter sets might need adjustment to meet the requirements above, as the provided sets are only examples for an experimental feature.

What We Expect

We expect a complete FHE AES-128 implementation. For reference, you may consult:

• The ISO/IEC 18033-4 standard.
• The tfhe-csprng implementation.
• Other Rust implementations of AES, such as the aes crate.

You are allowed to use any API from the TFHE-rs library. The implementation must:

1. Be tested using standard test vectors as well as randomly generated test cases.
2. Use the noise-asserts feature (available only in main). We recommend starting with the commit 38a7e4feef7d398b8e7a6f8f8d02e285855396ec
   or any later commit that includes bug fixes or performance improvements.

Additionally, you are required to provide a small executable that:

• Takes as input a number of outputs, an IV, and a key.
• Generates the requested number of AES values using a cleartext implementation (e.g., the aes crate) as a reference.
• Produces the same values homomorphically in FHE, decrypts them, and verifies correctness.

Program Inputs

You can use the clap library to parse command-line flags. The program inputs should be named as follows:

• --number-of-outputs
• --iv
• --key

Runtime Output

The executable must print FHE runtime details (excluding encryption and decryption times) in the following format:

AES key expansion took: {key_expansion_elapsed:?}
AES of #{number_of_outputs} outputs computed in: {elapsed:?}

The elapsed variables should be computed using std::time::Instant::elapsed() on the relevant start instant.

Additional Requirements

A README file must accompany the submission, explaining:

• How to use the FHE implementation.
• How to run the provided executable.

Benchmarking

All benchmarks will be conducted on an AWS hpc7a.96xlarge instance. When benchmarking, ensure that:

• AVX512 is enabled by using the nightly-avx512 feature.
• The implementation is compiled with a modern nightly toolchain.

Reward

🥇Best submission: up to $5,000

To be considered best submission, a solution must be efficient, effective and demonstrate a deep understanding of the core problem. Alongside the technical correctness, it should also be submitted with a clean code, clear explanations and a complete documentation.

🥈Second-best submission: up to $3,000

For a solution to be considered the second best submission, it should be both efficient and effective. The code should be neat and readable, while its documentation might not be as exhaustive as the best submission, it should cover the key aspects of the solution.

🥉Third-best submission: up to $2,000

The third best submission is one that presents a solution that effectively tackles the challenge at hand, even if it may have certain areas of improvement in terms of efficiency or depth of understanding. Documentation should be present, covering the essential components of the solution.

Register

Step 1: Registration

Click here to register for the TFHE-rs Bounty. Fill out the registration form with your information. Once you fill out the form, you will receive a confirmation email with a link to the submission portal for when you are ready to submit your code.

Note

Check your spam folder in case you don't receive the confirmation email. If you haven't received it within 24 hour, please contact us by email at [email protected].

Step 2: Work on the Challenge

Read through the Bounty details and requirements carefully. Use the provided resources and create your own GitHub repository to store your code.
If you have any questions during your work, feel free to comment directly in the Bounty issue and our team will be happy to assist you.

Step 3: Submission

Once you have completed your work, upload your completed work to the submission portal using the link provided in the confirmation email.

Note

The deadline for submission is February, 9th 2025 (23:59, Anywhere On Earth). Late submissions will not be considered.

We wish you the best of luck with the challenge!

Support

• Comment on this issue with any questions regarding this bounty.
• Email for private questions: [email protected]
• Join the Zama community channels here.

[Jineshbansal]

Hi @zaccherinij, could you please explain where homomorphic encryption should be applied in this process? Are you suggesting encrypting the key and block using homomorphic encryption first, and then performing AES encryption?

[IceTDrinker]

hello @Jineshbansal

We expect the given IV and the key provided in command line to be encrypted in FHE, then as indicated in the summary we expect both KeyDerivation and Encrypt/Decrypt to be implemented and tested.

The Key derivation time must be measured standalone and then the time to run the AES in counter mode for the given key and IV for the given number of output is going to be measured, fully in FHE, we don't expect the encryption time of the IV and Key to FHE to be measured.

Does that clear things up for you ?

Cheers

[Jineshbansal]

Hey @IceTDrinker,

This clears up most of our doubts. However, I wanted to confirm: will we be getting the client key or a decryption key to access the encrypted data?

In AES, the S-Box is used during the encryption process. However, if the data is already encrypted, we can’t directly work with the S-Box without the decryption key, to access specific elements in the S-Box, we rely on indexes provided by the FHE-encrypted vector. Since these indexes are themselves encrypted, we cannot directly access the required elements in the S-Box by this way :

// [[  0,  1,  2,  3]
//  [  4,  5,  6,  7]
//  [  8,  9, 10, 11]
//  [ 12, 13, 14, 15]]
let xss: FheArrayBase<&[..], tfhe::FheUint32Id> = xs.slice(&[0..1, 0..0]);
   
//[[  1,  1,  1,  1]
//  [  1,  1,  1,  1]
//  [  1,  1,  1,  1]
//  [  1,  1,  1,  1]]
let yss:  FheArrayBase<&[..], tfhe::FheUint32Id> = ys.slice(&[0..xss(encrypted thing), 0..xss(encrypted thing)]);

Let me know your thoughts!

[lla-dane]

Like if we want to set a bool parameter in the while loop like this but it is of type FheBool

   while b != 0 (type: FheBool) {
        ..
        } 

Normally we would just decrpyt the FheBool and move forward, so can we use the client key with which the given IV and the key are Fhe encrypted with. Just a thought :) @IceTDrinker

[IceTDrinker]

Hello @Jineshbansal and @lla-dane,

You likely don't know the following primitives:

https://docs.rs/tfhe/latest/tfhe/prelude/trait.IfThenElse.html

and match_value: https://docs.rs/tfhe/latest/tfhe/struct.FheUint.html#method.match_value

Cheers

[IceTDrinker]

Note that the number of outputs is in clear, so you can iterate n times knowing how many values we want as output

[a104995]

nice work *** *** ***@***.***> 于2025年1月17日周五 17:13写道：

…

Note that the number of outputs is in clear, so you can iterate n times knowing how many values we want as output — Reply to this email directly, view it on GitHub <#135 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/A3YIDCDXKSGZC4QJNUHEHH32LDCSDAVCNFSM6AAAAABTEOZJFKVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZDKOJXG43DQNRXGI> . You are receiving this because you are subscribed to this thread.Message ID: ***@***.***>

[lla-dane]

What is the meaning of number-of-outputs that will be sent in the command line, and also in benchmarking, there is a little bit confusion. Do we have to provide all the benchmarking on AWS hpc7a.96xlarge instance, or you guys will do it while testing/judging ? @IceTDrinker

[lla-dane]

Do we had to build a library in which a user can call the function like aes_encryption. So does this mean that user will call the set_server_key by their own before using our library. Is it right? @IceTDrinker