Аналіз фактора Ерміта алгоритму BKZ на решітках малої розмірності
Анотація
Криптографія на решітках є одним з перспективних напрямів досліджень у сучасній криптографії. Електронні підписи та механізми інкапсуляції ключів на решітках вже використовуються на практиці. У перспективі такі квантово-стійкі перетворення на решітках замінять усі стандарти, що не мають стійкості до атак на квантових комп’ютерах. Це робить аналіз їх безпеки надзвичайно актуальним. Аналіз безпеки криптографічних перетворень на решітках часто зводиться до оцінки мінімального розміру блоку у алгоритмах редукції решіток. Щоб визначити наскільки малі вектори може отримати алгоритм редукції для заданого розміру блоку часто використовується модель GSA, яка використовує так званий фактор Ерміта для передбачення розміру векторів, які може отримати алгоритм редукції решіток при заданих параметрах. Для його оцінки на практиці використовуються асимптотичні формули, проте питання їх точності на криптографічних решітках не до кінця досліджено. В роботі було отримано оцінки точності існуючих асимптотичних оцінок фактору Ерміта для решіток розмірностей 120, 145, 170 для класичного алгоритму BKZ. Дослідження проводились з використанням бібліотеки fpylll. Було показано, що існуючі оцінки з практичної точки зору є еквівалентними та мають достатньо мале середньоквадратичне відхилення від істинних значень. Було отримано формулу, що прив’язує середньоквадратичну похибку апроксимації фактору Ерміта до криптографічних параметрів решіток. Отримані результати є корисними для уточнення оцінок безпеки існуючих криптографічних перетворень.
Завантаження
Посилання
Computer Security Division, Information Technology Laboratory, National Institute of Standards and Technology, U.S. Department of Commerce. (n.d.). Post-Quantum Cryptography | CSRC | CSRC. Retrieved from https://csrc.nist.gov/projects/post-quantum-cryptography
Information technologies. Cryptographic protection of information. Algorithms for asymmetric encryption and key encapsulation: DSTU 8961:2019. (2019). Kiev: State Committee for Standardization of Ukraine.
Information technologies. Cryptographic protection of information. Algorithm for electronic signature on algebraic lattices with wicks: DSTU 9212:2023. (2023). Kiev: State Committee for Standardization of Ukraine.
Acar, A., Aksu, H., Uluagac, A. S., & Conti, M. (2018). A survey on homomorphic encryption schemes. ACM Computing Surveys, 51(4), 1–35. https://doi.org/10.1145/3214303
Albrecht, M. R., Göpfert, F., Virdia, F., & Wunderer, T. (2017). Revisiting the expected cost of solving USVP and applications to LWE. In Lecture notes in computer science (pp. 297–322). https://doi.org/10.1007/978-3-319-0694-8_11
Albrecht, M. R., Bai, S., Li, J., & Rowell, J. (2021). Lattice Reduction with Approximate Enumeration Oracles. In Lecture notes in computer science (pp. 732–759). https://doi.org/10.1007/978-3-030-84245-1_25
Chen, Y., & Nguyen, P. Q. (2011). BKZ 2.0: Better Lattice Security Estimates. In Lecture notes in computer science (pp. 1–20). https://doi.org/10.1007/978-3-642-25385-0_1
Li, J., & Nguyen, P. Q. (2022, March 5). A complete analysis of the BKZ Lattice Reduction algorithm. Retrieved from https://eprint.iacr.org/2020/1237
Nguyen, P. Q., & Valle, B. (2010). The LLL algorithm. Information security and cryptography. https://doi.org/10.1007/978-3-642-02295-1
Schnorr, C. P. (2003). Lattice reduction by random sampling and birthday methods. In Lecture notes in computer science (pp. 145–156). https://doi.org/10.1007/3-540-36494-3_14
Alkim, E., Ducas, L., Pöppelmann, T., & Schwabe, P. (2019, July 10). Post-quantum key exchange - a new hope. Retrieved from https://eprint.iacr.org/2015/1092
Авторське право (c) 2024 Комп’ютерні науки та кібербезпека
Цю роботу ліцензовано за Міжнародня ліцензія Creative Commons Attribution 4.0.
