written by Taekyung Kim

As of today (February 21, 2023), the only list of parameters according to their security levels which is gained a public trust in some extent is that from homomorphicencryption.org. Their white paper is available:

https://drive.google.com/file/d/1_kpLAP6LsSAoUt67O79OTPApT7gUTOCG/view?usp=drivesdk

One drawback of this paper is that it only describes security levels of parameters with $10 \le \log N \le 15$. Considering the de-facto default parameter in CryptoLab is of $\log N = 16$, although it is a bootstrappable one so we don’t use a true ternary distribution for the secret key generation, we are required to fill in the gaps of parameters with $\log N =16, 17$.

The Experiments

We use Albrecht’s lattice estimator with sagemath:

OS: Ubuntu 22.04
SageMath version 9.5, release date 2022-01-30
Lattice Estimator (commit 15ae3f4b2e47b2c51f8347af20c421db51c1020a): https://github.com/malb/lattice-estimator/commit/15ae3f4b2e47b2c51f8347af20c421db51c1020a

The following is a list of default parameters

Secret key is chosen from ND.Uniform(-1,1), the ternary uniform distribution with possible values -1, 0, or 1.
Error distribution is ND.DiscreteGaussian(3.2), the discrete Gaussian distribution with mean zero and the standard deviation 3.2 (a common choice).

Summary

n	Security Level	logq	primal (usvp)	dual	dual (hybrid)	dual (hybrid, mitm)
65536 (2^16)	128	1750	128.0	128.9	129.0	129.6
	192	1199	192.2	193.2	193.2	194.7
	256	929	256.4	257.5	257.2	259.9
131072 (2^17)	128	3523	128.1	128.5	129.2	129.5
	192	2411	192.1	192.9	192.9	193.7
	256	1867	256.0	257.1	257.1	258.3

Code

Example: Logarithmic dimension 16, modulus bits 1750

from estimator import *

params16_1750 = LWE.Parameters(n=2**16, q=2**1750, Xs=ND.Uniform(-1,1), Xe=ND.DiscreteGaussian(3.2))

print("(logn, logq) = (16, 1750), primal_usvp\\n")
print(LWE.primal_usvp(params16_1750, red_shape_model="gsa"))

print("\\n(logn, logq) = (16, 1750), dual\\n")
print(LWE.dual(params16_1750))

print("\\n(logn, logq) = (16, 1750), dual_hybrid\\n")
print(LWE.dual_hybrid(params16_1750))

print("\\n(logn, logq) = (16, 1750), dual_hybrid with mitm\\n")
print(LWE.dual_hybrid(params16_1750, mitm_optimization=True))

Result:

(logn, logq) = (16, 1750), primal_usvp

         rop: ≈2^128.0
         red: ≈2^128.0
           δ: 1.004628
           β:      321
           d:   126230
         tag:     usvp

(logn, logq) = (16, 1750), dual

         rop: ≈2^128.9
         mem:        1
           m: ≈2^16.0
           β:      324
           d:   131549
           ↻:        1
         tag:     dual

(logn, logq) = (16, 1750), dual_hybrid

         rop: ≈2^129.0
         mem: ≈2^110.5
           m: ≈2^16.0
           β:      321
           d:   131078
           ↻:        1
           ζ:       61
         tag: dual_hybrid

(logn, logq) = (16, 1750), dual_hybrid with mitm

         rop: ≈2^129.6
         mem: ≈2^111.4
           m: ≈2^16.0
           k:       66
           ↻:        1
           β:      323
           d:   131298
           ζ:      114
         tag: dual_mitm_hybrid