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

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 '19 at 23:06

## 1 Answer

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.

• Can you comment on which commands of Sage be useful? – hola May 14 at 2:59