# Introduction

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

The objective of the challenge is to design an algorithm that evaluates the function `parity(x)` under CKKS.

The function `parity(x)` gets an integer and returns its least significant bit (LSB). In other words,

$$parity(x) = x \mod 2,$$

where $x \in \mathbb{Z}.$

The `parity` function is closely related to the bit extraction problem, where given an integer $x$ the goal is to find its bit representation $x =\sum 2^i b_i$ which is useful in many cases, e.g., comparisons.
An efficient implementation to `parity(x)` would lead to an efficient implementation of bit extraction.

Evaluating this function under FHE is not trivial because it is not polynomial. The approximated nature of CKKS adds an additional layer of complexity as the noise levels need to be accounted for.

## Challenge Info

1. **Challenge type:** This challenge is a White Box challenge. Participants are required to submit the project with their source code.
2. **Encryption Scheme:** CKKS.
3. **FHE Library:** OpenFHE, Lattigo.
4. **Input Data:** Encrypted vector $x = (x_1, \ldots)$, where $x_i \in [0,255]$.
5. **Output Data:** The outcome should be an encrypted vector $parity(x)= \left(parity\left(x_1\right), \ldots\right)$.

## Parameters of the Key
1. **Bootstrapping:** The key will support bootstrapping.
2. **Number of slots:** $2^{16}$.
3. **Multiplication depth:** 29.
4. **Fractional part precision (ScaleModSize):** ~~51~~ 59 bits.
5. **First Module Size:** 60 bits.

## Parameters of the input
1. **Packing:** Each slot will contain one value $x_i$.
2. **Input range:** For each element $x_i=n_i + e_i$, where $n_i\in [0,255]$ is an integer, and $|e_i| < 10^{-5}$ is a small noise.

## Requirements of the output
1. **Packing:** Each slot will contain one value $y_i = parity(x_i)$, the parity of the corresponding slot in the input.
2. **Ouput range:** For each element $y_i=b_i + E_i$, where $y_i\in [0,1]$ is an integer, and $|E_i| < 10^{-2}$ is a small noise.

## Timeline
* **March 13, 2024** - Start Date.
* **June 15, 2024** - Submission deadline.
* **June 30, 2024** - Prize awarded.

## Test Environment
### Hardware

**CPU**: ~~1~~ 12 core

**RAM**: ~~48~~ 54GB

### 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
- **HElayers:** v1.5.3.1 [Download](https://ibm.github.io/helayers/ 'Download HElayers')
- **pyhelayers:** v1.5.3.1 [Download](https://ibm.github.io/helayers/ 'Download pyhelayers')

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

The executable should be named `parity` .

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

1. **File Format:**
- Your submission should be contained within 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
User can use config file to set parameters for generating a context on the server for testing the solution.
An example of the 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]
}

**indexes_for_rotation_key**:
If an application requires the use of a rotation key, this option allows to specify indexes for the rotation key. If the rotation key is not used, `indexes_for_rotation_key=[]` should be equal to empty array.

**mult_depth**:
The user can set the ring dimension. Howeve 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 for `scale_mod_size` is 51.

**first_mod_size**:
This parameter allows to setup FirstModSize.
Default value for `first_mod_size` is 60.

**batch_size**:
if bootstrapping is not used, this parameter allows to set the batch size. Default value is `ring_dimension/2`.

**enable_bootstrapping**:
If bootstraping is required, this option should be set to `true`.

**levels_available_after_bootstrap**:
If bootstrapping is used, this parameter allows to setup Levels available after boostrapping. Note that the actual number of levels avalailable 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.

The project must support the Command Line Interface (CLI) specified in the section below.

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

{
    "log_n": 15,
    "log_q": [60, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50],
    "log_p": [56, 55, 55, 55],
    "log_default_scale": 50
}

**log_n**
The polynomial degree in log₂

**log_p** and **log_q**
The desired moduli size

**log_default_scale**
The default initial scale for the plaintext

## Command-Line Interface for Application Testing
### OpenFHE
The application should support the following command-line interface (CLI) options:

- **--input** [path]: Specifies the path to the file containing encrypted test image.
- **--output** [path]: Specifies the path to the file where the result should be written.
- **--cc** [path]: Indicates the path to the Cryptocontext file serialized in **BINARY** form.
- **--key_public** [path]: Specifies the path to the Public Key file.
- **--key_mult** [path]: Specifies the path to the Evaluation (Multiplication) Key file.
- **--key_rot** [path]: Specifies the path to the Rotation Key file.

### Lattigo
The application should support the following command-line interface (CLI) options:

- **--input** [path]: Specifies the path to the file containing encrypted test image.
- **--output** [path]: Specifies the path to the file where the result should be written.
- **--cc** [path]: Indicates the path to the Cryptocontext file serialized in **BINARY** form.
- **--key_eval** [path]: defines 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 --input in.bin --output out.bin

An example for the message encrypted in `in.bin`:

`Input = [203.0000005, 102.0000008, 3.0000002, 56.9999994, 77.9999993, ...]`

An example output for this input:

`Output = [0.995, 0.008, 1.002, 1.004, -0.003, ...]`

## Evaluation Criteria
Submissions will be evaluated based on the following criteria:

1. **Correctness and accuracy:** The output of the program for valid input (i.e., numbers in the range $[0,255]$ and noise smaller than $10^{-5}$) **must** be correct with a noise within the allowed limit.
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.

## Scorring & Awards

Solutions implemented with OpenFHE and Lattigo libraries will be scorred separately.

The winner in each group and category will be awarded **$2500**.

One participant can be the winner in two groups.
Total prize fund **$5000**.

## 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

## Help
If you have any questions, you can:
- Contact us by email: [e-mail]
- Ask a question in our [Discord](https://discord.gg/NfhXwyr9M5).
- Open an issue on the [GitHub Repository]().
- Use [OpenFHE Discourse](https://openfhe.discourse.group).