Нахождение оптимальных BKZ-параметров для редукции NTRU-решеток
- Страницы / Pages
- 16-25
Аннотация
Рассмотрен вопрос подбора оптимальных параметров для атаки методом редукции решетки с применением BKZ-алгоритма на решетчатые криптосистемы, использующие решетки с подрешетками малого ранга. Иллюстрируются проблемы некоторых подходов к организации таких решетчатых криптосистем. Описаны условия для существования полиномиальной атаки, представлен эффективный алгоритм, находящий параметры для данной атаки. Разработанный алгоритм является довольно быстрым и работает за время, оцениваемое как O(log2n), где n — размерность решетки. Его корректность проверена численными эксперементами. Также приведены графики, связывающие параметры решетки и минимальные необходимые для ее успешной редукции параметры.
Abstract
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 of time to return results where 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.
Список литературы
1. Hoffstein J., Pipher J., Silverman J. H. An Introduction to Mathematical Cryptography. Springer, 2014.
2. Bernstein D. J., Chuengsatiansup Ch., Lange T., van Vredendaal Ch. NTRU Prime: reducing attack surface at low cost. URL: https://eprint.iacr.org/2016/461.pdf (дата обращения: 15.10.2020).
3. Lee Ch., Wallet A. Lattice analysis on MiNTRU problem. URL: https://www. semanticscholar.org/paper/Lattice-analysis-on-MiNTRU-problem-Lee-Wallet/d922d 602c196bebb2057b734fd8012b1bbb3cb9a (дата обращения: 15.10.2020).
4. Monteverde M. NTRU software implementation for constrained devices. Leuven, 2007.
5. Micciancio D., Voulgaris P. Faster exponential time algorithms for the shortest vector problem // 21st Annual ACM-SIAM Symposium on Discrete Algorithms. Austin, 2010. Р. 1468—1480.
6. Chen Yu. Réduction de réseau et sécurité concrete du chiffrement completement homomorphe : PhD Thesis. P., 2013.