Знаменитый алгоритм криптографии получает обновление | Журнал Кванта

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

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

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

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

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

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

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

Это работа для LLL: дайте ему (или его собратьям) основу многомерной решетки, и он выдаст лучшую. Этот процесс известен как редукция базиса решетки.

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

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

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

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

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

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

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

Quanta проводит серию опросов, чтобы лучше обслуживать нашу аудиторию. Возьми наш опрос читателей по информатике и вы будете участвовать в бесплатном выигрыше Quanta товар.