- Регистрация
- 17 Окт 2015
- Сообщения
- 11.618
- Репутация
- 4.228
- Реакции
- 15.380
LLL 2.0: исследователи представили алгоритм криптографии нового поколения
12 февраля, 2024Инновация сулит качественные изменения в подходе к безопасности данных.
В эпоху цифровизации нашей жизни безопасность во многом зависит от криптографии: от отправки личных сообщений до оплаты счетов в Интернете. Исследователи неустанно работают над проверкой надёжности криптографических систем, чтобы обеспечить их устойчивость к атакам.
Важным инструментом в этой работе является алгоритм Алгоритм LLL, представленный миру в 1982 году и названный в честь создателей Арьена Ленстры, Хендрика Ленстры-младшего и Ласло Ловаса, представляет собой метод сокращения базиса решетки, который находит применение в различных областях, включая вычислительную математику и криптографию, где помогает исследователям анализировать и улучшать безопасность криптографических систем.
Алгоритм LLL позволяет оптимизировать и упрощать базис решетки, делая его более удобным для вычислений и анализа. Это достигается за счёт преобразования исходного базиса в такой, который состоит из более коротких и более ортогональных почти перпендикулярных друг другувекторов.
LLL, названный в честь его создателей Арьена Ленстры, Хендрика Ленстры-младшего и Ласло Ловаса, представленный и опубликованный в далёком 1982 году. Этот алгоритм и его производные способны в некоторых случаях взламывать криптографические схемы, что помогает разработчикам создавать более защищённые системы. Алгоритм LLL также используется в продвинутых математических областях, например, в вычислительной теории чисел.
На недавней международной конференции по криптологии исследователями был представлен новый алгоритм в стиле LLL, который значительно повышает эффективность и расширяет область применения подобных методов.
Алгоритмы типа LLL работают с решётками — бесконечными совокупностями точек, расположенных с регулярными интервалами. Они могут описываться с помощью «базиса» — набора векторов, которые можно комбинировать для получения любой точки решётки. Процесс сокращения базиса решётки позволяет в некоторых случаях взламывать криптографические системы, переформулируя задачу взлома как поиск относительно короткого вектора в решётке.
Исходный алгоритм LLL не может обрабатывать слишком большие входные данные, именно это и стало причиной вести исследования в данном направлении.
Новая работа, автором которой является Райан и его научный советник, Надя Хенингер, сочетает в себе несколько стратегий для повышения эффективности своего алгоритма в стиле LLL. Во-первых, в методе используется рекурсивная структура, которая разбивает задачу на более мелкие части. Во-вторых, алгоритм тщательно управляет точностью используемых чисел, находя баланс между скоростью и правильным результатом. Новая работа позволяет исследователям уменьшать основания решёток с тысячами измерений.
Такие алгоритмы также играют важную роль в исследованиях криптосистем на основе решёток, которые предназначены для обеспечения безопасности даже в условиях будущего с существованием мощных квантовых компьютеров. Новый инструмент может расширить возможности экспериментов по изучению атак на эти системы, предоставляя более чёткое представление об их эффективности.
