Что означает работа «Эффективный квантовый алгоритм для задач с решеткой, обеспечивающий субэкспоненциальный коэффициент аппроксимации»?

В Эффективный квантовый алгоритм для задач с решеткой, обеспечивающий коэффициент субэкспоненциальной аппроксимации, автор утверждает, что они дают квантовый алгоритм с полиномиальным временем для решения проблемы декодирования на ограниченном расстоянии с субэкспоненциальным коэффициентом аппроксимации в классе целочисленных решеток. Что означает этот результат? Будет ли это означать ненадежность решетчатой ​​криптографии? Так ли это важно, как квантовый алгоритм факторинга Питер Шор?

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

tl;dr это: особая проблема, к которой обращаются авторы, классически легко решить с помощью стандартных алгоритмов решетки (квант не требуется), как показано в этой заметке. Более того, основной новый квантовый шаг может быть реализован классически (и гораздо проще и эффективнее). Итак, работа не показывает ни квантового преимущества по сравнению с тем, что мы уже знали, как делать классически, ни чего-то нового в том, что мы можем делать классически. Подробности следуют.

Предложение «об одном классе целочисленных решеток» является очень важным уточнением. Проблема BDD, к которой обращаются авторы, заключается в том, что решетка$q$-ary” и генерируется одним $n$-размерный мод-$q$ вектор (или их небольшое количество), модуль $q \gg 2 ^ {\ sqrt {n}} $, а целевой вектор находится в $\ll 2^{-\sqrt{n}}$ фактор минимального расстояния решетки. Этот параметр далек от всего, что когда-либо использовалось в решетчатой ​​криптографии (насколько мне известно), поэтому результат не окажет прямого влияния на предлагаемые решетчатые системы. Конечно, более широкий вопрос заключается в том, могут ли методы привести к более сильным результатам, которые действительно влияют на решетчатую криптографию.

Основываясь на описании, данном в докладе, несколько экспертов считают весьма вероятным, что проблема специальной решетки, к которой обращаются авторы, уже легко решается с помощью известных классический методы (квант не требуется). ОБНОВИТЬ: это оказалось так, и это подтверждается в эта записка. Другими словами, особая форма проблемы BDD позволяет легко решить ее известными и неудивительными способами. Алгоритм представляет собой просто стандартную последовательность редукции базиса LLL, за которой следует декодирование ближайшей плоскости Бабаи, но демонстрация того, что это действительно работает, зависит от некоторых более глубоких (но ранее известных) свойств LLL, чем те, которые обычно вызываются.

А как насчет более широкого вопроса: могут ли основные методы привести к более сильным результатам, которые мы не можем получить в настоящее время классическими методами? Оказывается, то, что выполняет основной квантовый шаг, преобразование «наихудшего случая в средний», может быть выполнено. классически (и более просто и эффективно) с использованием хорошо известного метода рандомизации — так называемой «саморедукции LWE» или — ($q$-ary) редукция BDD к LWE». См. раздел 5 и теорему 5.3 Эта бумага и более ранние работы, цитируемые там для деталей.

Точнее, $n$-размерный $q$-ary BDD для относительного расстояния $\альфа$ (рассматриваемая авторами задача) классически сводится к LWE с частотой ошибок $\альфа\cdot O(\sqrt{n})$. Хотя это сокращение кажется ненужным для решения исходной рассматриваемой проблемы BDD, оно показывает, что основной новый квантовый шаг может быть заменен чем-то классическим, что работает, по крайней мере, так же хорошо (и, вероятно, даже лучше с точки зрения параметров). Это указывает на то, что основная квантовая техника, вероятно, не обладает какой-либо новой или удивительной силой в этом контексте.

Я создал веб-сайт для краудсорсинга того, что известно об алгоритмах для задач решетки в NP, пересекающих CoNP:

https://решетчатыеалгоритмы.xyz

Наша газета готова:

https://arxiv.org/abs/2201.13450

Для справки, вот временная шкала, которой мы следовали:

До 17.08.21 мы довольно основательно прошлись по классической литературе. Классический алгоритм также был бы хорош, чтобы мы могли передать его обратно в квантовые алгоритмы. Но поскольку базовый случай представляет собой наихудший тип хорошо изученной проблемы скрытых чисел, казалось разумным, что ничего не известно.

17.08.21-21.09.21: Мы опросили 5 экспертов, что известно о проблеме. В одном случае мы указали наилучший классический подход, который смогли найти. Мы не получили ответов с новой информацией.

21.09.21: Было принято решение использовать специальный базовый случай с одним вектором в докладе, потому что (1) это поможет людям решить его, и (2) это коллоквиум на квантовом семинаре и, следовательно, необходимо быть доступным для широкой аудитории. Разговор только с решетками или только с квантовым уже вызов, а совместить и то, и другое, ну попробуй! 21.09.21: Оживленная дискуссия о возможностях во время панели, но без алгоритмов.

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

31.01.22: Классического ответа для нашей границы Шнорра пока не получено.

Шон

На этот вопрос можно было бы дать гораздо более длинный ответ (и мне было бы очень интересно увидеть точку зрения кого-то вроде Криса), но следующих двух моментов, вероятно, будет достаточно для неспециалиста.

Факторы приближения: Основной способ, с помощью которого эту атаку следует рассматривать как (потенциальную) угрозу для криптографии на основе решетки, — это возможность будущих улучшений. Коэффициент аппроксимации, на который нацелена эта цель (который, как я полагаю, равен $2^{n^{1/2}}$) достаточно велико, что даже если LWE классически слабо в этом диапазоне, можно было бы построить такие вещи, как:

• ПКЕ
• Цифровые подписи
• ФТО

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

Возможность деквантования: Атака состоит из двух частей:

1. Шаг (квантового) уменьшения размерности (от $n\to \sqrt{n}$)
2. Используйте стандартные классические методы для решения $\sqrt{n}$-экземпляр измерения.

Ряд людей предложили возможность деквантования первого шага с помощью таких вещей, как взятие случайных линейных комбинаций (скажем, с коэффициентами Гаусса) базисных векторов. Если это уменьшение размерности работает, получается BDD с коэффициентом аппроксимации. $2^{n^{1/2}}$ за полиномиальное время (я полагаю).

Хотя это сделало бы сам алгоритм сильнее, это также сделало бы его менее тревожным в определенном смысле. Это потому, что у нас (классически) есть довольно приличное представление о том, насколько сложными являются проблемы решетки. При этом я, в частности, имею в виду такие вещи, как:

1. Различные «мелкозернистые» результаты твердости, которые существуют (скажем, в соответствии с экспоненциальной гипотезой времени или ее вариантами),
2. недавний нижние границы решетчатого просеивания, и
3. результаты твердости при наличии предварительной обработки (например, результаты твердости CVPP).

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