# Security curves

To select secure cryptographic parameters for usage in Concrete, we utilize the [Lattice-Estimator](https://github.com/malb/lattice-estimator). In particular, we use the following workflow:

1. Data Acquisition
   * For a given value of $$(n, q = 2^{64}, \sigma)$$ we obtain raw data from the Lattice Estimator, which ultimately leads to a security level $$\lambda$$. All relevant attacks in the Lattice Estimator are considered.
   * Increase the value of $$\sigma$$, until the tuple $$(n, q = 2^{64}, \sigma)$$ satisfies the target level of security $$\lambda\_{target}$$.
   * Repeat for several values of $$n$$.
2. Model Generation for $$\lambda = \lambda\_{target}$$.
   * At this point, we have several sets of points $${(n, q = 2^{64}, \sigma)}$$ satisfying the target level of security $$\lambda\_{target}$$. From here, we fit a model to this raw data ($$\sigma$$ as a function of $$n$$).
3. Model Verification.
   * For each model, we perform a verification check to ensure that the values output from the function $$\sigma(n)$$ provide the claimed level of security, $$\lambda\_{target}$$.

These models are then used as input for Concrete, to ensure that the parameter space explored by the compiler attains the required security level. Note that we consider the `RC.BDGL16` lattice reduction cost model within the Lattice Estimator. Therefore, when computing our security estimates, we use the call `LWE.estimate(params, red_cost_model = RC.BDGL16)` on the input parameter set `params`.

## Usage

To generate the raw data from the lattice estimator, use::

```
make generate-curves
```

by default, this script will generate parameter curves for {80, 112, 128, 192} bits of security, using $$log\_2(q) = 64$$.

To compare the current curves with the output of the lattice estimator, use:

```
make compare-curves
```

this will compare the four curves generated above against the output of the version of the lattice estimator found in the [third\_party folder](https://github.com/zama-ai/concrete/tree/main/third_party).

To generate the associated cpp and rust code, use::

```
make generate-code
```

further advanced options can be found inside the Makefile.

## Example

To look at the raw data gathered in step 1., we can look in the [sage-object folder](https://github.com/zama-ai/concrete/tree/main/tools/parameter-curves/sage-object). These objects can be loaded in the following way using SageMath:

```
sage: X = load("128.sobj")
```

entries are tuples of the form: $$(n, log\_2(q), log\_2(\sigma), \lambda)$$. We can view individual entries via::

```
sage: X["128"][0]
(2366, 64.0, 4.0, 128.51)
```

To view the interpolated curves we load the `verified_curves.sobj` object inside the [sage-object folder](https://github.com/zama-ai/concrete/tree/main/tools/parameter-curves/sage-object).

```
sage: curves = load("verified_curves.sobj")
```

This object is a tuple containing the information required for the four security curves ({80, 112, 128, 192} bits of security). Looking at one of the entries:

```
sage: curves[2][:3]
(-0.026599462343105267, 2.981543184145991, 128)
```

Here we can see the linear model parameters $$(a = -0.026599462343105267, b = 2.981543184145991)$$ along with the security level 128. This linear model can be used to generate secure parameters in the following way: for $$q = 2^{64}$$, if we have an LWE dimension of $$n = 1536$$, then the required noise size is:

$$\sigma = a \* n + b = -37.85$$

This value corresponds to the logarithm of the relative error size. Using the parameter set $$(n, log(q), \sigma = 2^{64 - 37.85})$$ in the Lattice Estimator confirms a 128-bit security level.