Hello! I was reading the paper that the recently released optimizer is based on (https://eprint.iacr.org/2022/704.pdf) and I’m wondering how the security oracle (definition 6) is built from the lattice estimator. I had a quick look here (concrete/compilers/concrete-optimizer at 065e4d7b401e38d3237f21b8413ee9999a84e933 · zama-ai/concrete · GitHub) but I couldn’t easily find it, maybe I’m looking in the wrong place.

From the paper, I’m guessing that what you do is pick k (GLWE dimension) and N (poly size), put this in the lattice estimator with a given initial noise, and see if the security is what you want. If not then increase the noise until you get the desired security. Is this what is happening? If so, how do you make the initial guess of the noise and how do you define the increase? If you point me to the corresponding code that would be great!

Thanks!

Hi @sergirovira!

The code for the parameter curves can be found here:

Your intuition on how the code works is correct, we use many calls to the lattice estimator in order to find secure parameters (starting from some sensible (N, k, q, sigma) and e.g. increasing sigma until security is satisfied). We then use this raw data to generate “curves” which the optimizer takes as an input.

The code is set-up to use a previous version of the curves as the starting point for any new curve generation (which may be required when there are changes to the lattice estimator).

Feel free to follow-up with any other questions you may have.

Ben

Hello @bencrts,

I understand how the security oracle works now, thank you for your help!

After checking the verification of the curve, I see that the obtained curves are checked against a line (function f_model from verify_curves.py). Do you have any theoretical reason for this approximation or it is just the best and simplest fit and it is enough for the purposes of the optimizer?

Sergi

Hi @sergirovira!

We used a fitting function and the linear model was the best choice to fit the raw data. We could use other types of input (say, a look-up-table), but the linear curve was nicer due to the compact representation.

Ben