13/02/24
В эпоху цифровизации нашей жизни безопасность во многом зависит от криптографии: от отправки личных сообщений до оплаты счетов в Интернете. Важным инструментом в этой работе является алгоритм LLL, названный в честь его создателей Арьена Ленстры, Хендрика Ленстры-младшего и Ласло Ловаса, представленный и опубликованный в далёком 1982 году. Этот алгоритм и его производные способны в некоторых случаях взламывать криптографические схемы, что помогает разработчикам создавать более защищённые системы. Алгоритм LLL также используется в продвинутых математических областях, например, в вычислительной теории чисел.
На недавней международной конференции по криптологии исследователями был представлен новый алгоритм в стиле LLL, который значительно повышает эффективность и расширяет область применения подобных методов, передаёт Securitylab.
Алгоритмы типа LLL работают с решётками — бесконечными совокупностями точек, расположенных с регулярными интервалами. Они могут описываться с помощью «базиса» — набора векторов, которые можно комбинировать для получения любой точки решётки. Процесс сокращения базиса решётки позволяет в некоторых случаях взламывать криптографические системы, переформулируя задачу взлома как поиск относительно короткого вектора в решётке.
Исходный алгоритм LLL не может обрабатывать слишком большие входные данные, именно это и стало причиной вести исследования в данном направлении.
Новая работа, автором которой является Райан Киган и его научный советник, Надя Хенингер, сочетает в себе сразу несколько стратегий для повышения эффективности своего алгоритма в стиле LLL. Во-первых, в методе используется рекурсивная структура, которая разбивает задачу на более мелкие части. Во-вторых, алгоритм тщательно управляет точностью используемых чисел, находя баланс между скоростью и правильным результатом. Новая работа позволяет исследователям уменьшать основания решёток с тысячами измерений.
Такие алгоритмы играют важную роль в исследованиях криптосистем на основе решёток, которые предназначены для обеспечения безопасности даже в условиях будущего с существованием мощных квантовых компьютеров. Новый инструмент может расширить возможности экспериментов по изучению атак на эти системы, предоставляя более чёткое представление об их эффективности.
