3
$\begingroup$

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 ?

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – 111 Sep 21 '19 at 23:06
0
$\begingroup$

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.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.