2020 Выпуск №4

Гибридная атака на задачу обучения с ошибками (LWE) с разряженным секретом

Страницы / Pages

10-15

Аннотация

В 2007 г. Н. Хаугрейв-Грэм предложил атаку на криптосистему NTRU, которая заключается в совмещении техники редукции решеток и комбинаторного метода «встречи посередине» (атаки meet-in-the-middle, MiTM). В данной работе этот подход применяется к задаче Lear­ning with Errors (LWE) с секретом малой длины. Задача LWE явля­ется одной из самых важных в теории криптографии на решетках. Безопасность большого количества криптографических схем, начиная от простых подписей и схем и заканчивая продвинутыми схемами, такими как групповые подписи и полностью гомоморфное шифрование, основывается на предположениях о сложности LWE. В статье пред­ставлен обзор гибридной атаки, а также используемых в ней алгорит­мов. Это необходимо для дальнейшей практически значимой реализации атаки, главной целью которой является верификация корректности применения метода MiTM к гибридной атаке на LWE.

Abstract

In 2007, Howgrave-Graham proposed attack against NTRU cryptosys­tem, which consists of two parts, combining lattice reduction technique and a combinatorial method called meet-in-the-middle (MiTM). In this article, we apply hybrid attack to the Learning with Errors Problem (LWE) with sparse sec­ret. The LWE problem is considered to be one of the most important in lat­tice-based cryptography. Large number of cryprographic schemes ranging from basic signature and encryption schemes to advanced schemes like group sig­natures and fully homomorphic encryption, base their security on the hard­ness assumption of LWE. In this paper, we review the hybrid attack and the algorithms it is based on. It is required for further practical implementation of the attack, whose main objective is to verify correctness of MiTM to the hyb­rid attack against the LWE problem.

Список литературы

1. Howgrave-Graham N. A hybrid lattice-reduction and meet-in-the-middle attack against NTRU // Advances in Cryptology — CRYPTO 2007: Proceedings of 27^th Annual International Cryptology Conference. Springer, 2007. Vol. 4622. P. 150—169. (Lecture Notes in Computer Science).

2. Ajtai M. Generating hard instances of lattice problems // Proceedings of the 28^th annual ACM symposium on Theory of computing. Springer, 1996. P. 99—108.

3. Regev O. On lattices, learning with errors, random linear codes, and crypto­graphy // Journal of the ACM. 2009. Vol. 56, iss. 6. P. 1—40.

4. Fitzpatrick R., Bishof Ch. H., Buchmann J. et al. Tuning GaussSieve for speed // International Conference on Cryptology and Information Security in Latin America. Springer, 2014. P. 288—305.

5. Babai L. On Lovász’ lattice reduction and the nearest lattice point problem // Combinatorica. 1986. Vol. 6, iss. 1. P. 1—13.

6. Buchmann J., Göpfert F., Player R., Wunderer Th. On the hardness of LWE with bi­nary error: Revisiting the hybrid lattice-reduction and meet-in-the-middle attack // International Conference on Cryptology in Africa. Springer, 2016. P. 24—43.

8. Wunderer T. Revisiting the Hybrid Attack: Improved Analysis and Refined Security Estimates // Cryptology ePrint Archive, Report 2016/733. URL: https:// eprint.iacr.org/2016/733 (дата обращения: 15.10.2020).

9. Micciancio D., Goldwasser S. Complexity of lattice problems: a cryptographic perspective. Springer Science & Business Media, 2012. Vol. 671.

10. Micciancio D. Lattice-based cryptography // Encyclopedia of Cryptography and Security. Springer, 2011. P. 713—715.

11. Conway J. H., Sloane N. J. A. Sphere packings, lattices and groups. Springer Science & Business Media, 2013.