Develop a Fixed-point Arithmetic API Using Homomorphic Integers within TFHE-rs

[zaccherinij]

Overview

Fixed-point arithmetic is essential for many applications, but performing such operations efficiently in a Fully Homomorphic Encryption (FHE) setting remains a challenge. This bounty focuses on developing a fixed-point arithmetic API using homomorphic integers (tfhe::integer) within TFHE-rs, avoiding the use of WoPBS (Without Padding Programmable Bootstrapping) while ensuring correctness, efficiency, and precision.

The goal is to create an API similar in clarity and usability to the fixed crate but operating on encrypted data. The API should enable encrypted fixed-point arithmetic while leveraging homomorphic integer operations effectively.

What we expect

Participants must implement a fixed-point arithmetic API using homomorphic integers in TFHE-rs. The API should:

• Mimic the features of the fixed crate;
• Support common fixed-point arithmetic operations;
• Offer configurable precision and scaling factors;
• Avoid using WoPBS (Without Padding Programmable Bootstrapping);
• Include unit tests to validate correctness and docstrings for usage;
• The Homomorphic Types should be called FheFixed where the type in the fixed crate is itself called Fixed.

For parameters we expect:

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

You can use parameter sets already provided by the library.

Required features

Operations

• Basic operations: Addition, subtraction, multiplication, and division.
• Comparison operations: <, <=, >, >=, ==, !=.
• Unary operations: Negation, absolute value, rounding functions (floor, ceil, trunc, round).
• Square root (sqrt(x)).
• Integer base-2 logarithm (ilog2(x)).
• Configurable scaling factor for different fixed-point representations.
• The implementation must include unit tests covering all arithmetic operations and edge cases.

Misc.

• A README file must accompany the submission, explaining:
  • How to use the FHE implementation;
  • How to run the provided executable;
• Use the noise-asserts feature;
• If you are working on non-x86 CPUs, make sure that clippy runs by using a cross-compilation toolchain, using cargo +nightly clippy --target x86_64-unknown-linux-gnu -D warnings. More details here.

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.
• We expect you to use criterion for the benchmarks and provide benchmarks for FheFixed<U16>, FheFixed<U32>, FheFixed<U64> with even integer and fractional part, meaning U16 will have 8 bits for the integer part and 8 bits for the fractional part. The benchmark name must follow this format: FheType::operation_snake_case

Judging criteria

• Correctness: The implementation must produce mathematically accurate results following fixed-point arithmetic rules;
• Performance: The solution should minimize computational overhead, optimizing for practical usage in TFHE-rs;
• Precision Handling: The API should allow configurable precision levels, similar to the fixed crate;
• Usability: The implementation should be well-structured and documented, with a clear API design and example usage;
• Compliance: The implementation must use TFHE-rs and must not rely on WoPBS (Without Padding Programmable Bootstrapping);
• Testing: The solution must include unit tests to verify correctness and edge cases, include extensive tests with trivial encryptions as inputs, and smaller tests with properly encrypted data. Inputs must be random.

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.

Reward amounts are decided based on code quality, model accuracy scores and speed performance on a m6i.metal AWS server. When multiple solutions of comparable scope are submitted they are compared based on the accuracy metrics and computation times.

Related links and references

• TFHE-rs documentation

👉 Register

Step 1: Registration

Click here to register for the fhEVM 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 durig 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 18th May, 2025 (Midnight, 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.

[etimofeeva]

For sqrt and ilog2, are Taylor series or iterative methods ok if I can't use WoPBS?

[infiniteemptyness]

Hello, I am not sure I understand correctly what you want. Since all has to be encrypted, all operations between ciphertexts might just call a bivariate PBS no? Do you expect a work on the way operations are performed or do you want an implementation of the fixed crate but in FHE?

[mtotbagi]

Hi, I have a couple of questions about the requirements of the bounty.

1. I am not an expert in the inner workings of the TFHE-rs library. Are there any integer operations that use WoPBS in themselves?

2. What is the expected configurability? Is it okay if I only allow even numbers of bits as fractional parts?

3. What flavors of operations should be supported? The fixed crate has 5 types of flawors:

   • wrapping
   • saturating
   • overflowing
   • checked
   • unwrapped

Of these checked and unwrapped I don't think are possible to do in FHE. However TFHE-rs also has it's own flavors for operations. As any kind pairing of the two flavoring could be implemented, should I also implement every possible flavor combination (9 or 12 in total)? Also should I implement parallel/non-parallel version of each function(variation) too?

[IceTDrinker]

For sqrt and ilog2, are Taylor series or iterative methods ok if I can't use WoPBS?

Hello @B1n4ryR41nb0w

Sure, anything that works within the given framework, though it is encouraged to find methods that will be as fast as possible, taylor expansion might be slow, also I believe ilog2 can be done more efficiently

[IceTDrinker]

Hello, I am not sure I understand correctly what you want. Since all has to be encrypted, all operations between ciphertexts might just call a bivariate PBS no? Do you expect a work on the way operations are performed or do you want an implementation of the fixed crate but in FHE?

hello @infiniteemptyness

If you do a bivariate PBS for all types you will be very very slow, also it's uncomputable for 64 bits I would think, the size of lookup table would be insanely large...

Also if you find a way to solve this with a bivariate PBS in a reasonable time then you may want to claim a millenium prize 😄

[IceTDrinker]

Hi, I have a couple of questions about the requirements of the bounty.

1. I am not an expert in the inner workings of the TFHE-rs library. Are there any integer operations that use WoPBS in themselves?

2. What is the expected configurability? Is it okay if I only allow even numbers of bits as fractional parts?

3. What flavors of operations should be supported? The fixed crate has 5 types of flawors:

   • wrapping
   • saturating
   • overflowing
   • checked
   • unwrapped

Of these checked and unwrapped I don't think are possible to do in FHE. However TFHE-rs also has it's own flavors for operations. As any kind pairing of the two flavoring could be implemented, should I also implement every possible flavor combination (9 or 12 in total)? Also should I implement parallel/non-parallel version of each function(variation) too?

Hello @mtotbagi

1. the wopbs is only enabled with the experimental feature so as long as you don't enable it you are fine
2. why do you want to enable only an even number of bits as factional parts?
3. You have the list of operations given, the arithmetic ones correpsond to the rust traits Add/Sub/Mul/Div and then the other ones we requires

We want the fastest possible so parallel is recommended