search

malb / lattice-estimator

An attempt at a new LWE estimator
215 stars 49 forks source link

include chaloy bkz time estimation in the form as LaaMosPol14 #122

Open gong-cr opened 3 weeks ago

gong-cr commented 3 weeks ago

Add BKZ total time estimation for ChaLoy21 as ChaLoy21_BKZ. Two cost models: ChaLoy21: time estimation for quantum sieving algorithm (single SVP call within BKZ) based on the work [AC:ChaLoy21]. ChaLoy21_BKZ: total time estimation for BKZ including multiple calls to SVP oracle using sieving algorithm from [AC:ChaLoy21].

malb commented 3 weeks ago

Where does this formula come from? I'd be surprised if (0.2570 * beta + 16.4 + log(self.svp_repeat(beta, d), 2)) was correct.

gong-cr commented 3 weeks ago

The BKZ cost cost follows the same structure as in BDGL16 (classical) and LaaMosPol14 (quantum), but the coefficient is adjusted to align with the time complexity of the ChaLoy21 quantum sieving algorithm. I agree that the factor 16.4 may not be very solid, and other terms might also be questionable under the quantum regime. I’m not sure if there are any better alternatives at this point.

malb commented 3 weeks ago

Mhhh, now that I think about it, I don't think we should cost Quantum BKZ, i.e. change LaaMosPol14.