# Introduction

This challenge was developed by [IBM Research](https://research.ibm.com/).

The objective of the challenge is to sort an array under CKKS.

Sorting is a fundamental tool used in many algorithms and systems. In **comparison model** it was proven that sorting an array $A$ of $n$ values takes at least $\Omega(n)$ time. The proof considers a binary tree with $n!$ leaves, representing the different permutations of $A$. The optimal algorithms traverses the tree to find the leaf (permutation) that sorts $A$. At every step the optimal sorting algorithm makes a single comparison and rules out half of the remaining leaves leading to at least $\log n! = n\log n$ steps.

Naively translating plaintext algorithms to FHE leads to inefficient algorithms because FHE runs in *circuit model*. Still, sorting networks such as Batcher and Bitonic sorting can sort $n$ values in $O(n\log ^2 n)$ time. The more recent AKS sorting network can sort $n$ values in only $O(n\log n)$, achieving the theoretically optimal time bound (asymptotically).

Sorting $A$ under CKKS is even more complicated due to the noise added by CKKS and grows with every operation and the inaccurate (polynomial approximation for) comparison.

## Challenge info

1. **Challenge type**: this challenge is a White Box challenge. Participants are required to submit the project with their source code. You can learn more about this type of challenges in our [Participation guide](https://fherma.io/how_it_works).
2. **Encryption scheme**: CKKS.
3. **Supported libraries**: [OpenFHE](https://github.com/openfheorg/openfhe-development), [Lattigo](https://github.com/tuneinsight/lattigo).
4. **Input**: encrypted vector $A=[x_1, \ldots, x_n]$, where $x_i∈[0,255]$ are real numbers.
5. **Output**: the outcome should be an encrypted vector of the sorted values of $A$.

## Timeline

- **May 30, 2024** - Start Date.
- **July 1, 2024** - Submission deadline.
- **July 16, 2024** - Prize awarded.

## Parameters of the key

1. **Bootstrapping**: enabling bootstrapping support.
2. **Number of slots**: $2^{16}$
3. **Multiplication depth**: 29.
4. **Fractional part precision (ScaleModSize)**: 59 bits.
5. **First Module Size**: 60 bits.

## Parameters of the input

1. **Array and its packing**: the values of the array will be written in slots $0,\ldots, (n-1)$ of the ciphertext. Slot $i$ will contain the value $x_{i+1}$.
3. **Input range**: for each element $x_i$ is a real number with at most 2 non-zero digits after the decimal point.
4. **Uniqueness**: you can assume the numbers in $A$ are unique (i.e., no number appears twice) and the minimal distance between any 2 numbers is at least $0.01$ (before adding CKKS noise).

You will find an example below.

## Requirements of the output

1. **Packing**: each slot should contain one value $y_i$ (where slot $(i-1)$ will contain the value $y_i$) sorted in ascending order. That is, $y_1=\min_i x_i$, $y_2$ is the second smallest number, etc.
2. **Accuracy**: the values in the output must not incur an error of more than $0.0001$.

You will find an example below.

## Test environment
### Hardware

**CPU**: 12 core
**RAM**: 54 GB

### Software

The following libraries/packages will be used for generating test case data and for testing solutions:

- **OpenFHE:** v1.1.4
- **OpenFHE-Python:** v0.8.6
- **Lattigo:** v5.0.2

## Submission

To address this challenge, participants can utilize one of the two libraries, OpenFHE or Lattigo.

The executable should be named `sort`.

### OpenFHE

If the solution is developed using the OpenFHE library, we expect it to have a CMake project. The CMakeLists.txt file should be placed in the project's root directory. Please adhere to the following format when submitting your solution:

1. **File format:**
- Your submission should be packed into a ZIP archive.
2. **Structure of the archive:**
- Inside the ZIP archive, ensure there is a directory titled `app`.
- Within the `app` directory, include your main `CMakeLists.txt` file and other necessary source files.

graph TD;
    app_zip[app.zip] --> app_folder[app]
    app_folder --> CMakeLists[CMakeLists.txt]
    app_folder --> main.cpp[main.cpp]
    app_folder --> config.json[config.json]
    app_folder --> ...[...]

#### Config file

You can use a config file to set parameters for generating a context on the server for testing the solution. An example of such a config and detailed description of each parameter is given below.

{
    "indexes_for_rotation_key": [
        1
    ],
    "mult_depth": 29,
    "ring_dimension": 131072,
    "scale_mod_size": 59,
    "first_mod_size": 60,
    "batch_size": 65536,
    "enable_bootstrapping": false,
    "levels_available_after_bootstrap": 10,
    "level_budget": [4,4]
}

##### Config file parameters

- **indexes_for_rotation_key**: if an application requires the use of a rotation key, this option allows specifying indexes for the rotation key. If the rotation key is not used, it should be an empty array: `indexes_for_rotation_key=[]`.
- **mult_depth**: the user can set the ring dimension. However, if a minimum ring dimension is set for the challenge, then the user can only increase this value; decreasing it is not possible.
- **scale_mod_size**: this parameter is used to configure`ScaleModSize`, default value is `51`.
- **first_mod_size**: this parameter allows setting up `FirstModSize`, default value is `60`.
- **batch_size**: if the bootstrapping is not used, this parameter allows to set the batch size. Default value is `ring_dimension/2`.
- **enable_bootstrapping**: if you need bootstrapping, set this option to `true`.
- **levels_available_after_bootstrap**: this parameter allows setting up levels available after the bootstrapping if it's used. Note that the actual number of levels available after bootstrapping before next bootstrapping will be `levels_available_after_bootstrap - 1`, because an additional level is used for scaling the ciphertext before next bootstrapping (in 64-bit CKKS bootstrapping).
- **level_budget**: the bootstrapping procedure needs to consume a few levels to run. This parameter is used to call `EvalBootstrapSetup`. Default value is `[4,4]`.

### Lattigo

If the project is built using the Lattigo library, a `Makefile` is expected in the root directory of the project. Check out the project's template [on GitHub](https://github.com/Fherma-challenges).

## Command-line interface for application testing

The application must support the Command Line Interface (CLI) specified below.

### General options

- **--array** [path]: specifies the path to the file containing the encrypted vector.
- **--output** [path]: specifies the path to the file where the result should be written.
- **--cc** [path]: indicates the path to the crypto context file serialized in **BINARY** form.

### Additional keys for OpenFHE

- **--key_public** [path]: the path to the Public Key file.
- **--key_mult** [path]: the path to the Evaluation (Multiplication) Key file.
- **--key_rot** [path]: the path to the Rotation Key file.

### Additional keys for Lattigo

- **--key_eval** [path]: the path to the file where `MemEvaluationKeySet` object is serialized. `MemEvaluationKeySet` contains evaluation key and Galois keys.

## Example

The executable will be run as follows:

./app --cc cc.bin --key_public pub.bin --key_mult mult.bin --array in.bin --output out.bin

An example for the message encrypted in `in.bin`: `Input = [203.23, 102.83, 3.68, 77.46]` (this does not include the noise added by CKKS during encryption).

An example output for this input: `Output = [3.68, 77.46, 102.83, 203.23]`

## Evaluation criteria

Submissions will be evaluated using an array of size $n=2048$ and scored with these criteria:

1. **Correctness and accuracy:** the output of the program for valid input, i.e., numbers in the range $[0,255]$, **must** be correct (in ascending order) with an error of no more than $0.0001$ for each element.
2. **Execution time:** the running time of the application on the provided input data.

That is, the winner will be the fastest application whose output is correct and accurate.

## Scoring & awards

Solutions implemented with OpenFHE and Lattigo libraries will be scored separately. The winner in each group and category will be awarded **$2,500**.

One participant can be the winner in two groups. Total prize fund is **$5,000**.

## Challenge committee

- [Gurgen Arakelov](https://www.linkedin.com/in/gurgen-arakelov-943172b9/), Fair Math
- [Jean-Philippe Bossuat](https://www.linkedin.com/in/jean-philippe-bossuat-9136024b/), Lattigo
- [Nikita Kaskov](https://www.linkedin.com/in/nikita-kaskov-07029812a/), Fair Math
- [Yuriy Polyakov](https://www.linkedin.com/in/yuriy-polyakov-796b84a/), Duality
- [Hayim Shaul](https://www.linkedin.com/in/hayim-shaul-b2658/), IBM Research

## Useful Links

- [FHERMA participation guide](https://fherma.io/how_it_works)—more about FHERMA challenges.
- [OpenFHE](https://github.com/openfheorg/openfhe-development) repository, README, and installation guide.
- [OpenFHE Python](https://github.com/openfheorg/openfhe-python) repository, README, and installation guide.
- [Lattigo](https://github.com/tuneinsight/lattigo)
- A vast collection of resources collected by [FHE.org](http://fhe.org/), [FHE resources](https://fhe.org/resources), including tutorials and walk-throughs, use-cases and demos.
- [OpenFHE AAAI 2024 Tutorial](https://openfheorg.github.io/aaai-2024-lab-materials/)—Fully Homomorphic Encryption for Privacy-Preserving Machine Learning Using the OpenFHE Library.

## Help

If you have any questions, you can:

- Contact us by email: [[e-mail]](mailto:[e-mail])
- Join our [Discord](https://discord.gg/NfhXwyr9M5) server, and ask your questions in the [#fherma channel](https://discord.com/channels/1163764915803279360/1167875954392187030).
- Open an issue in the [GitHub Repository](https://github.com/Fherma-challenges/parity).
- Use [OpenFHE Discourse](https://openfhe.discourse.group/) for OpenFHE related issues.