Create a string library that works on encrypted data using TFHE-rs

[zaccherinij]

Winners

🥇 1st place: A submission by JoseSK999
🥈 2nd place A submission by Tomtau
🥉 3rd place : A submission by M-Bln

---

Overview

This TFHE-rs bounty looks to provide a set of APIs working over encrypted string reproducing APIs from the rust std library str type (see documentation at https://doc.rust-lang.org/std/primitive.str.html)

This document will specify the expected structure of the example that you will produce and specify various constraints on the types that will be introduced and the APIs that are expected on the primitives.

How to participate?

1️⃣ Register here.
2️⃣ When ready, submit your code here.
🗓️ Submission deadline: December 17, 2023.

Description

String encoding

The input string encoding is expected to be ASCII.

To avoid leaking the length of the input string we may want to encrypt zeros after the string actual content, to easily mark the end of the string we will make the FheString null terminated, i.e., it must always end by the value 0u8 encrypted, like C Strings are null terminated.

Note
[ADDED 23.10.2023]
A null character "\0" may mark the early end of a string but is not required (as was first asked in the bounty) as it can make some algorithms more complicated and slower.
The option to have encrypted strings with a padding made with 0s is still required (to leave the option to the user to obfuscate the string's length), differentiating between the two kind of strings (padded or not) can and should be used to chose better algorithms when possible.

Functions to implement

Your submission should at least implement, the following method for an encrypted string:

• contains with clear / encrypted pattern
• ends_with with clear pattern / encrypted pattern
• eq_ignore_case
• find with clear pattern / encrypted pattern
• is_empty
• len
• repeat with clear / encrypted number of repetitions
• replace with clear pattern / encrypted pattern
• replacen with clear pattern / encrypted pattern
• rfind with clear pattern / encrypted pattern
• rsplit with clear pattern / encrypted pattern
• rsplit_once with clear pattern / encrypted pattern
• rsplitn with clear pattern / encrypted pattern
• rsplit_terminator with clear pattern / encrypted pattern
• split with clear pattern / encrypted pattern
• split_ascii_whitespace
• split_inclusive with clear pattern / encrypted pattern
• split_terminator with clear pattern / encrypted pattern
• splitn with clear pattern / encrypted pattern
• starts_with with clear pattern / encrypted pattern
• strip_prefix with clear pattern / encrypted pattern
• strip_suffix with clear pattern / encrypted pattern
• to_lowercase
• to_uppercase
• trim
• trim_end
• trim_start
• + (concatenation)
• Comparisons between strings >=, <=, !=, ==

API to use for the bounty

This bounty should make use of the integer API from TFHE-rs, more precisely we expect you to use RadixCiphertexts with the default parallelized functions available in the crate.

Structure of the example directory

You will put your code in the directory tfhe/src/examples/fhe_strings

This directory will contain the following:

main.rs:

The code for a command line executable that will take an input string to be encrypted and a pattern for string functions which require it. This executable will encrypt the first string and run all the available APIs on the input string using the pattern when necessary. The results will be compared to the clear APIs provided by rust’s std::str, the ouptuts will be nicely formatted for the user to see that the results match (if there are errors then the bounty would not be considered valid) with timing information for the FHE version.

Use clap (the version pinned in TFHE-rs) to build the command line.

ciphertext.rs:

This module will contain:

• FheAsciiChar: a wrapper type that will hold a RadixCiphertext from integer which must be able to store at least 8 bits of data to be able to fit a single ASCII char;
• FheString: a wrapper type around a Vec<FheAsciiChar>, the last FheAsciiChar of the string always encrypts a 0u8, it is possible to have 0u8 earlier than the last char, this would allow the user to hide the actual length of the string that is encrypted, accessors should be made to be able to iterate easily on the inner vec both mutably and immutably, do not provide a from_blocks primitives as it would be easy to misuse, a new function should be enough to construct the type at encryption time with a client key, see for example tfhe/src/integer/ciphertext/mod.rs to see how Integer RadixCiphertext are built to give access to their content for use by algorithms.

client_key.rs:

Provide a ClientKey type that can be built from shortint parameters (that are also used by the integer API) or from an IntegerClientKey directly, realistically this ClientKey type will wrap the IntegerClientKey and provide primitives to encrypt a rust str (validating before encryption that the str is a valid ASCII str), decrypt it in a fresh String. There should be an encryption primitive that allows the user to specify how many “padding” encryption of zeros should be appended after the 0-terminated string that will be encrypted from the provided input string.

ClientKey must derive serde::Serialize, serde::Deserialize and Clone.

directory server_key:

mod.rs:
Provide a ServerKey that wraps an Integer ServerKey that can be built from a ClientKey from client_key.rs or directly from an Integer ServerKey.

ServerKey must derive serde::Serialize, serde::Deserialize and Clone.

Create files for families of functions that share similar algorithmic needs, e.g., IF IT MAKES SENSE (here we are speculating, this is just an example supposing similar functions will require similar algorithms)

split.rs

Will contain an impl Block for the above ServerKey dedicated to split functions like

• rsplit
• rsplit_terminator
• split
• split_inclusive
• split_terminator

and all relevant helper functions. If some functions are needed everywhere then those functions can be put in the mod.rs file from the directory.

trim.rs

Will contain an impl Block for the above ServerKey dedicated to trim functions like

• trim
• trim_end
• trim_start

Note that the above functions will not literally trim blocks off of the provided FheAsciiString but rather will zero out the correct blocks to make the null terminated string the trimmed version as appropriate.

Also, it could make sense to separate functions depending on the type of the pattern (i.e., encrypted or clear) in separate files.

Other requirements

Each function should have a docstring describing what it does (those can be adapted from the rust std docs) with a doctest demonstrating the usage on simple hard coded cases.
We expect standard algorithms if it makes sense (with links to the papers describing them or publicly available content on the web like a Wikipedia page for example), if some tricks are used proper comments are expected to be provided in the code.

Note

As submissions are evaluated on a 64 cores machine, your code should heavily use parallelization

A Makefile target (see Makefile for the template of our targets) for running the tests of the example is expected. A command to run the binary easily from the terminal is also requested.
The code must compile on the latest stable rust. No #[allow(clippy::...)] are authorized unless absolutely necessary but that should never be required.
The code must pass the make pcc (pre commit check) available from our Makefile, if you get errors then the code needs to be fixed to satisfy the pcc checks.
Good luck!

Reward

🥇Best submission: up to €10,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,500.

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 €1,500.

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 and speed performance on a m6i.metal AWS server.

Related links and references

• std::str reference
• TFHE-rs documentation
• TFHE-rs repository

Submission

Apply directly to this bounty by opening an application here.

Questions?

Do you have a specific question about this bounty? Join the live conversation on the FHE.org discord server here. You can also send us an email at: bounty@zama.ai

[leyuskckiran1510]

Could you provide me the time frame,I will be working on it after two weeks; will that be okay?

[aquint-zama]

Could you provide me the time frame,I will be working on it after two weeks; will that be okay?

Deadline for submission is 17th December (you could see it with the associated milestone

[tomtau]

I have a few questions:

1. patterns: I assume it should compile on the stable Rust, right? So in that case, it's not possible to use the pattern feature Tracking issue for string patterns rust-lang/rust#27721 so we'd just need to make a custom type or trait for it -- I also assume the patterns could only be ASCII (like strings in that bounty), is that correct? And should empty patterns be allowed?
2. All those functions should be on the ServerKey, or should they also be on FheString? And they will all need ServerKey anyway, so it's not possible to implement e.g. std::ops traits (like for +) directly on FheString... hence those functions would be just standalone methods on ServerKey, is that correct or should those traits be somehow implemented (e.g. implement them for (ServerKey, FheString) or something like that)?
3. split: similarly to patterns, I guess it's ok to create custom types for those different Split return types / iterators (RSplit, RSplitN, SplitAsciiWhitespace, SplitInclusive...), is that correct? For splitn and rsplitn, only the pattern can either be clear or encrypted, n is always clear, right?
4. outputs: (I'm new to tfhe and) I assume outputs of all those functions would be encrypted, right? Should they use some special types from tfhe, or ok just to use a type alias or a wrapper around RadixCiphertext? And for methods that "branch" (i.e. I assume one cannot know with a ServerKey if a pattern was matched or not in a ciphertext, so needs to compute both options), should it return a vector of all computed ciphertexts (while ClientKey would have a method that can process it and pick the correct output)? I saw that in the regex tutorial: https://docs.zama.ai/tfhe-rs/application-tutorials/regex#matching. so I was wondering whether that's what's expected... and if not, do you have an example of a way how to handle it, e.g. somehow combine boolean and integer circuits for this kind of branching output aggregation?
5. trim:

Note that the above functions will not literally trim blocks off of the provided FheAsciiString but rather will zero out the correct blocks to make the null terminated string the trimmed version as appropriate.

this makes sense for me with trim_end, but I'm not sure about trim or trim_start... is it ok to just treat 0-byte as empty anywhere in the string (rather than just at its end / null-termination), so ClientKey's decryption would just filter out these 0s to get a string? Or should it still respect C-style and what to do in that case? Should it use a special value to mark empty places (e.g. 256 outside of u8's range) before 0-termination?

[tomtau]

@aquint-zama one follow-up question depending on the answer to 4. about function outputs:

6. repeat: how should the encrypted number of repetitions be handled? Again, based on my newbie understanding, one cannot know with a ServerKey whether a given string should be repeated 1-time or 1000000000-times... is it in that situation ok to return a "lazy" repeated string iterator (which will most likely return two encrypted values: a flag whether the number of repetitions was reached and the repeated encrypted string constructed up to that point)? ClientKey can then get the final string by iterating and checking the decrypted flags?

[IceTDrinker]

hello @tomtau

1. Yes this should compile on stable rust, ASCII patterns indeed, empty patterns should be handled the same way the std rust library handles them I guess ?
2. On the ServerKey is perfectly fine, managing traits are not in the scope of this bounty
3. n could be encrypted but with obvious limitations to small integer types (probably u8) as oblivious execution would mean a worst case scenario with respect to n which becomes impossible for large integers, if it proves impossible to implement or has very bad runtime this would be taken into account. Custom return types are fine as long as they are easy to manipulate and make sense (the std rust library has been built the way it is for good reasons), but in the FHE world some of those may not be expressible as you don't know where some of the sub strings end, this is part of why this is a bounty, some unknowns around the algorithms/data handling
4. For the branching you have the if_then_else function for integer ciphertexts, we expect the return types to be FheStrings where it makes sense, and RadixCiphertexts for boolean values which will in the end (if the algorithm is correct) just encrypt a 0 or a 1
5. This is a good point, so trim_end can fill with 0s while trim_start may probably need to shuffle blocks back to the start of the string to be valid, there may be something smarter to do with special characters but that may not be encodable if rust uses extended ascii (8 bits) vs standard ascii (7 bits)
6. For encrypted n several ways, the one you propose seems interesting, to note that depending on the type of n (u8 is doable, u16 less so already, u32 is probably impossible on commodity hardware and would be way too slow) it could be doable fully

[tomtau]

Thanks @IceTDrinker . And for "replace" / "replacen" functions, should the "to" argument be FheString or a plain string/slice?

[IceTDrinker]

I believe both are doable, with a complication/performance degradation if "to" is also encrypted