Gentry-Halevi’s Fully-Homomorphic Encryption and hermite factor

Question

In section 7.2, page 18 in Chen-Nguyen paper regarding BKZ 2.0, they point out different Hermite factors related to Gentry-Halevi FHE.

More precisely, it is said that the critical Hermite factor for the "large" challenge with lattice dimension $n=32768$ is $\delta = 1.0081^n$.

How is this Hermite factor computed ?

I think it has the following meaning. Each column corresponds to a specific challenge of Gentry-Halevi’s main challenges. You have to find the specific challenge (the links of the challenges are dead) and then calculate $||{\bf b}_1||/vol(L)^{1/n}.$ Then write it in the form $\delta^{n}.$ This form is useful, because many experiments have been made with different algorithms, and for the specific challenge, BKZ-130 (experimentally) outputs a basis with $\delta^n$ Hermite factor. — 111, Sep 21, 2019 at 23:06

helios_ · Accepted Answer · 2019-08-22 16:33:58Z

1

It is computed like that: L is lattice with dimension i. B is BKZ reduction of lattice L.

$$Root Hermite Factor=( B[0].norm() / ( L.volume() )^{(1/i)})^{(1/i)}$$

If you want to calculate RHF, you can use Sage Math.

answered Aug 22, 2019 at 16:33

helios_

213 bronze badges

$\begingroup$ Can you comment on which commands of Sage be useful? $\endgroup$
– hola
May 14, 2021 at 2:59

Add a comment |

1 Answer 1