Analyzing Pump and Jump BKZ Algorithm Using Dynamical Systems

The analysis of the reduction effort of the lattice reduction algorithm is important in estimating the hardness of lattice-based cryptography schemes. Recently many lattice challenge records have been cracked by using the Pnj-BKZ algorithm which is the default lattice reduction algorithm used in G6K, such as the TU Darmstadt LWE and SVP Challenges. However, the previous estimations of the Pnj-BKZ algorithm are simulator algorithms rather than theoretical upper bound analyses. In this work, we present the first dynamic analysis of Pnj-BKZ algorithm. More precisely, our analysis results show that let L is the lattice spanned by \((\textbf{a}_i)_{i\le d}\) . The shortest vector \(\textbf{b}_1\) output by running \(\varOmega \left( \frac{2Jd^2}{\beta (\beta -J)}\left( \ln _{}{d} +\ln _{} \ln _{}{\max _{i}\frac{\left\| \textbf{a}_i^{*} \right\| }{(\textrm{det}L )^{1/d} } } \right) \right) \) tours reduction of pnj-BKZ \((\beta ,J)\) , \(\textbf{b}_1\) satisfied that \(\left\| \textbf{b}_1 \right\| \le {\gamma }_{\beta }^{\frac{d-1}{2(\beta -J)}+2 } \cdot \left( \textrm{det}L \right) ^{\frac{1}{d} } \) .