Алгоритмы сокращения базиса решетки в криптоанализе

Abstract

Reducing the basis of the lattice is a fundamental tool in cryptanalysis and is used to successfully attack many cryptosystems based on both lattices and other mathematical problems. The success of lattice methods in cryptanalysis is largely specified reduction algorithms work much better in practice than their theoretical worst-case analysis predicts. Over the past 30 years, basic reduction algorithms have been studied in many works, but the gap between theoretical analysis and practical efficiency is still largely inexplicable.