12.02.2024

Знаменитый алгоритм, устроивший революцию в криптографии, только что был усовершенствован

Двое исследователей усовершенствовали известную технологию редукции основания замощений, открыв новые возможности для практических экспериментов в криптографии и математике.

Мэдисон Голдберг

Рисунок: Меррил Шерман/Quanta Magaine

В нашей цифровой жизни безопасность зависит от криптографии. Отправляя личное сообщение или оплачивая счет в Интернете, вы полагаетесь на алгоритмы, призванные сохранить ваши данные в тайне. Естественно, некоторые люди хотят раскрыть эти секреты, поэтому исследователи работают над проверкой прочности этих систем, чтобы убедиться, что они не дрогнут от рук умного злоумышленника.

Одним из важных инструментов в этой работе является алгоритм LLL, названный в честь исследователей, опубликовавших его в 1982 году - Арджена Ленстры, Хендрика Ленстры-младшего и Ласло Ловаша. LLL и его многочисленные потомки в некоторых случаях могут взламывать криптографические схемы; изучение их поведения помогает исследователям разрабатывать системы, менее уязвимые для атак. Но достоинства алгоритма выходят за рамки криптографии: Он также является полезным инструментом в передовых математических областях, таких как вычислительная теория чисел.

На протяжении многих лет исследователи совершенствовали варианты LLL, чтобы сделать метод более практичным - но только до определенного момента. Теперь пара криптографов построила новый алгоритм в стиле LLL, значительно повысив его эффективность. Новая технология, получившая награду за лучший доклад на Международной криптологической конференции 2023 года, расширяет спектр сценариев, в которых компьютерщики и математики могут использовать LLL-подобные подходы.

«Это действительно потрясающе», - сказал Крис Пейкерт, криптограф из Мичиганского университета. По его словам, этот инструмент был предметом изучения на протяжении десятилетий. «Всегда приятно, когда объект, над которым так долго работали... показывает, что он еще способен удивлять».

Алгоритмы типа LLL работают в мире графов: бесконечных сборок регулярно расположенных точек. Чтобы представить это наглядно, вообразите, что вы укладываете плитку на пол. Вы можете покрыть его квадратными плитками, и углы этих плиток составят одно замощение. В качестве альтернативы можно выбрать плитку другой формы - например, длинный параллелограмм - и создать другое замощение.

Замощение можно описать с помощью ее «основы». Это набор векторов (по сути, списки чисел), которые можно комбинировать различными способами, чтобы получить каждую точку замощения. Представим себе замощение с базисом, состоящим из двух векторов: [3, 2] и [1, 4]. Замощение - это все точки, которые можно получить, складывая и вычитая копии этих векторов.

Эта пара векторов - не единственный базис замощения. У каждого замощения, имеющей хотя бы два измерения, есть бесконечно много возможных базисов. Но не все базисы одинаковы. С базисом, векторы которого короче и расположены под прямым углом друг к другу, обычно легче работать и он более полезен для решения некоторых вычислительных задач, поэтому исследователи называют такие базисы «хорошими». Примером может служить пара синих векторов на рисунке ниже. Базисы, состоящие из более длинных и менее ортогональных векторов, таких как красные векторы, можно считать «плохими».

Рисунок: Меррил Шерман/Quanta Magaine

Какое отношение все это имеет к криптографии? Оказывается, задача взлома криптографической системы в некоторых случаях может быть переформулирована в другую задачу: найти относительно короткий вектор в замощении. И иногда этот вектор можно извлечь из сокращенного базиса, сгенерированного алгоритмом в стиле LLL. Эта стратегия помогла исследователям взломать системы, которые, на первый взгляд, имеют мало общего с замощениями.

В теоретическом смысле исходный алгоритм LLL работает быстро: Время его работы не увеличивается экспоненциально с размером входных данных, то есть с размерностью замощения и размером (в битах) чисел в базисных векторах. Но оно увеличивается как полиномиальная функция, а «если вы действительно хотите добиться результата, то полиномиальное время не всегда реализуемо», - говорит Лео Дюкас, криптограф из национального исследовательского института CWI в Нидерландах.

На практике это означает, что оригинальный алгоритм LLL не может справиться со слишком большими входными данными. «Математики и криптографы хотели иметь возможность делать больше», - говорит Киган Райан, аспирант Калифорнийского университета в Сан-Диего. Исследователи работали над оптимизацией алгоритмов в стиле LLL для работы с большими входными данными, и часто добивались хорошей производительности. Тем не менее, некоторые задачи оставались по-прежнему недостижимыми.

В новой работе, авторами которой являются Райан и его консультант Надя Хенингер, сочетаются несколько стратегий для повышения эффективности алгоритма в стиле LLL. С одной стороны, методика использует рекурсивную структуру, которая разбивает задачу на более мелкие фрагменты. С другой стороны, алгоритм тщательно управляет точностью чисел, находя баланс между скоростью и правильным результатом. Новая работа делает возможным сокращение оснований замощений с тысячами измерений.

В предыдущих работах использовался аналогичный подход: В работе 2021 года также сочетались рекурсия и управление точностью для быстрой работы с большими замощениями, но это работало только для определенных видов замощений, а не для всех важных в криптографии. Новый алгоритм хорошо себя ведет в гораздо более широком диапазоне. «Я очень рад, что кто-то сделал это», - сказал Томас Эспитау, исследователь криптографии в компании PQShield и автор версии 2021 года. По его словам, работа его команды была «доказательством концепции»; новый результат показывает, что «вы можете делать очень быстрое сокращение замощений разумным способом».

Новая методика уже начала приносить пользу. Аурел Паж, математик из французского национального исследовательского института Inria, рассказал, что он и его команда использовали адаптацию алгоритма для решения некоторых вычислительных задач теории чисел.

Алгоритмы в стиле LLL также могут сыграть свою роль в исследованиях, связанных с системами криптографии на основе замощений, которые должны оставаться безопасными даже в будущем с мощными квантовыми компьютерами. Они не представляют угрозы для таких систем, поскольку для их взлома требуется найти более короткие векторы, чем это могут сделать эти алгоритмы. Но лучшие из известных исследователям атак используют алгоритм типа LLL в качестве «базового строительного блока», - говорит Вессель ван Ворден, криптограф из Университета Бордо. В практических экспериментах по изучению таких атак этот строительный блок может замедлить работу. С помощью нового инструмента исследователи смогут расширить спектр экспериментов, которые они могут проводить с алгоритмами атак, и получить более четкое представление о том, как они работают.

Источник: wired.com