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
  • 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, 2019 at 23:06

1 Answer 1

1
$\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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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