Improved progressive BKZ algorithms and their precise cost estimation by sharp simulator

DOI10.1007/978-3-662-49890-3_30MaRDI QIDQ2820508zbMATH OpenOpenAlexFDO

Authors Yoshinori Aono, Yun-Tao Wang, Takuya Hayashi, Tsuyoshi Takagi

Publication date 9 September 2016

Published in Advances in Cryptology – EUROCRYPT 2016 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-662-49890-3_30

zbMATH Keywords

lattice basis reductiongeometric series assumptionGram-Schmidt orthogonal basisprogressive BKZ

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Cryptography (94A60)

Recommendations

• Measuring, simulating and exploiting the head concavity phenomenon in BKZ
• Improving the BKZ reduction algorithm by quick reordering technique
• BKZ 2.0: Better lattice security estimates
• A lattice reduction algorithm based on sublattice BKZ
• Analyzing blockwise lattice algorithms using dynamical systems

Cited in

(33)

• On the measurement and simulation of the BKZ behavior for \(q\)-ary lattices
• Improved lattice enumeration algorithms by primal and dual reordering methods
• Lattice reduction with approximate enumeration oracles. Practical algorithms and concrete performance
• An extension of Kannan's embedding for solving ring-based LWE problems
• A survey of solving SVP algorithms and recent strategies for solving the SVP challenge
• Improving convergence and practicality of slide-type reductions
• Vulnerable public keys in NTRU cryptosystem
• Finding short integer solutions when the modulus is small
• Analysis of DeepBKZ reduction for finding short lattice vectors
• Revisiting orthogonal lattice attacks on approximate common divisor problems
• Dynamic self-dual DeepBKZ lattice reduction with free dimensions and its implementation
• Generalized attack on ECDSA: known bits in arbitrary positions
• Random sampling revisited: lattice enumeration with discrete pruning
• A new polynomial-time variant of LLL with deep insertions for decreasing the squared-sum of Gram-Schmidt lengths
• NTRU Fatigue: How Stretched is Overstretched?
• Concrete analysis of quantum lattice enumeration
• A detailed analysis of the hybrid lattice-reduction and meet-in-the-middle attack
• Lattice-based public key cryptosystems invoking linear mapping mask
• An experimental study of Kannan's embedding technique for the search LWE problem
• Second order statistical behavior of LLL and BKZ
• Improving the BKZ reduction algorithm by quick reordering technique
• Faster enumeration-based lattice reduction: root Hermite factor \(k^{1/(2k)}\) time \(k^{k/8+o(k)}\)
• A refined hardness estimation of LWE in two-step mode
• On the success probability of solving unique SVP via BKZ
• The convergence of slide-type reductions
• BS: Blockwise Sieve Algorithm for Finding Short Vectors from Sublattices
• Quantum lattice enumeration in limited depth
• New NTRU Records with Improved Lattice Bases
• Worst case short lattice vector enumeration on block reduced bases of arbitrary blocksizes
• Revisiting the Sparsification Technique in Kannan’s Embedding Attack on LWE
• A complete analysis of the BKZ lattice reduction algorithm
• Solving the search-LWE problem over projected lattices
• A lattice reduction algorithm based on sublattice BKZ

This page was built for publication: Improved progressive BKZ algorithms and their precise cost estimation by sharp simulator

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2820508)