IKBFU's Vestnik

2020 Issue №4

Back to the list Download an article

Finding optimal BKZ parametrs for NTRU lattice reduction



This article is devoted to selection of optimal parameters for lattice reduction attack against lattice-based cryptosystems that use lattices with low rank sublattices. It illustrates design flaws caused by current approach to buiding these types of cryptosystems. Its relevance and novelty lies in the description of the conditions for the existence of a polynomial attack and in constructing an efficient algorithm that allows us to find optimal reduction attack parameters. The algorithm developed during the work on this article is quite fast and requires O(log2n) log of time to return results where n is the dimension of lattice. Its correctness has been verified by numerical experiments. As a result, graphs are shown connecting the parameters of the lattice and the minimum smallest parameters necessary for its successful reduction.