Design of Optimal Progressive BKZ with Increasing Success-Probabilities and Increasing Block-Sizes

Former studies on progressive-BKZ almost focus on increasing block sizes. Our work in IJCNIS ۹.۹, ۲۰۱۸, introduces a new version of progressive-BKZ based on increasing success probabilities, while its results are not sufficiently hopeful! This paper introduces two algorithms of “BKZ with optimal progressive block sizes” and “BKZ with optimal progressive success probabilities”, while their time-complexities are proved to be optimal. However these two proposed algorithms are designed to solve exact-SVP for an input basis, they can be used as an SVP-solver in the body of another BKZ algorithm for practical attacks! Also, our proposed algorithms can be used as reasonable representatives of two approaches of “increasing block sizes” and “increasing success probabilities” in the progressive-BKZ family to be compared with each other for the first time. For dimension n≥۹۰, BKZ with optimal progressive success probabilities shows better runtime than corresponding instances of BKZ with optimal progressive block sizes, so that for Gentry-Halevi’s main lattice challenges, these speedups include: “۲^۱۴.۱ times for Toy challenge of n=۵۱۲”, “۲^۶۷.۲ times for Small challenge of n=۲۰۴۸”, “۲^۲۳۵.۵ times for Medium challenge of n=۸۱۹۲” and “۲^۱۲۰۷.۷ times for large challenge of n=۳۲۷۶۸”. Also, the time cost of BKZ with optimal progressive success probabilities and optimal progressive block sizes as two exact-SVP solvers are compared with some main claimants of exact-SVP solvers such as sieve algorithm, extreme-pruned enumeration, full-enumeration, and so on, for the dimensions of ۱۰۰≤β≤۲۴۰, and our results show hopeful time cost against these claimants. Moreover, two Cost-Models are approximated for these two optimal progressive BKZ.

Keywords:

Optimal Progressive BKZ , Progressive block size , Progressive success probability , Time cost , GNR Enumeration