Вы непреднамеренно наткнулись на особенно сложную/поляризующую тему в криптографии на основе решетки, а именно на то, что известно как теснота сокращения поиска к решению.
Короче говоря, заявление формы
Любой алгоритм $А$ против проблемы $А$ который работает во времени $T_A$ с преимуществом $\эпсилон_А$ подразумевает алгоритм $В$ против проблемы $В$ который работает во времени $T_B$ преимущества $\эпсилон_B$.
это упрощенный способ подытожить криптографическую редукцию.
В идеале сокращение в обтяжку, что означает, что оба:
- $T_A\приблизительно T_B$ (лучше всего, когда $T_B = T_A$ плюс небольшие накладные расходы на сокращение), и
- $\epsilon_A\приблизительно \epsilon_B$.
Есть (примерно) два понятия герметичности, асимптотический (где сказать $T_B= О(T_A)$, и конкретный.
Обратите внимание, что сокращение времени работы $T_A = 2^{512}T_B$ является асимптотически плотным, но не конкретно плотным.
Редукция Регева определенно «не тугая». Технически сложно точно указать, что это означает, поэтому я буду ссылаться исключительно на соответствующую литературу.
Еще один взгляд на герметичность 2, что изначально поднимало вопросы герметичности редукции (кажется в разделе 6 или 7, но не помню).
А Дипломная работа утверждал, что дает более жесткое сокращение (и параметризует криптосистему, основанную на SVP напрямую, как вы обсуждаете), но
(Подмножество) авторы первой статьи выпустили еще одна газета в этом месяце, утверждая, что вычисления тезиса неверны, а редукция все еще неточна. Здесь есть и другие интересные утверждения: редукция Регева — это алгоритм BQP. Они замечают, что это нетривиально, в частности, алгоритм Шора (конкретно) намного проще в исполнении, что, возможно, не очень хорошо.
Также было некоторое обсуждение в группе Google NIST-PQC, которое может представлять интерес.
Грубо говоря, Дэн Бернстайн считает, что разрыв в герметичности проблематичен.
Крис Пейкерт набросал различие между «ограничением преимуществ» ($\epsilon_A\приблизительно \epsilon_B$) и "напряжённость наработки" ($T_A\приблизительно T_B$).
Хотя это звучит так, как будто можно попытаться формализовать это различие, я не знаю никаких публикаций по этому вопросу, кроме связанной ветки электронной почты.
Все это говорит о том, что многие авторы предполагают, что конкретные последствия редукции наихудшего к среднему случаю до SVP не приводят к осмысленным представлениям о безопасности, если только не выбрать невероятно большие параметры, которые на практике не используются.
«Наименьшие параметры», которые людям удалось получить с помощью этой стратегии, по-прежнему велики (см. магистерскую диссертацию), и недавно некоторые авторы заявили, что эти «большие, но только в 2-3 раза» параметры неверны.
Хотя все эти работы содержат описания преобразования LWE в SVP, я не уверен, что что-то из этого будет особенно полезно с точки зрения пояснения.
Тем не менее, ваше предложение имеет наибольший смысл в предположении, что редукция является жесткой --- это, к сожалению, не так (при условии правильности первой и третьей статей выше, которые я не читал внимательно), поэтому ваше предложение может быть более сложно, чем вы предполагаете.
Обратите внимание, что наличие зазора нет означают, что LWE небезопасен, просто невозможно (конкретно) основывать безопасность LWE на SVP.
Таким образом, большинство сторонников криптографии на основе решетки поступили следующим образом:
использовать существование наихудшего случая к среднему случаю, чтобы аргументировать качественно что «распределение LWE» не является «структурно ошибочным». В качестве примера «структурно ошибочного» распределения для задачи известно, что RSA является простым, если $N = pq$ таков, что $|p-q|$ небольшой (через Алгоритм факторинга Ферма). На самом деле этого никогда не должно происходить, если все сгенерировано правильно, но предыдущая ссылка обнаружила некоторые неправильно сгенерированные ключи.
конкретно установить параметры на основе прямого криптоанализа LWE, скажем, используя LWE оценщик.
Если вашей основной целью является исключительно атака экземпляра LWE, я бы посоветовал прочитать оценщик LWE.
Грубо говоря, он используется для параметризации экземпляров LWE.
Это достигается путем оценки (конкретной) стоимости различных известных атак против LWE.
Вероятно, для вас имеет смысл изучить эти известные атаки.
Существует множество хороших ресурсов по известным атакам против LWE, однако документация по оценке LWE, вероятно, является самой актуальной.
