LWE с повторяющейся матрицей A

Рассмотрим следующую версию обучения с ошибками.

Вам либо дано $(A, As_1 + e_1, As_2 + e_2, \ldots, As_k + e_k)$ или же $(А, и_1, и_2, \ldots, и_к)$, куда

• $А$ является $м \раз п$ матрица, элементы которой берутся из поля $\mathbb{Z}_q$ --- записи выбираются равномерно случайным образом.
• $u_1, u_2, \ldots, u_k$ находятся $м\раз 1$, каждая из записей которого исходит из поля $\mathbb{Z}_q$ равномерно случайным образом.
• Каждый $e_1$, $e_2$, $\ldots$, $e_k$ является $м\раз 1$ Гауссовский вектор шума.
• Каждый $s_1, s_2, \ldots, s_k$ является $n \раз 1$ секретная строка.

Вам говорят различать эти два случая.

Предполагая, что стандартная LWE сложна, эта проблема также сложна?

В общем, другая матрица $А$ отбирается для каждого образца LWE. Здесь у нас та же матрица $А$ но $к$ разные секреты.Это что-то меняет в настройках?

Да, это все еще сложно с помощью простого гибридного аргумента. По существу, для $i\in[k]$ определить «смешанное распределение»

$$H_i = (A, A\vec s_1 + \vec e_1,\dots, A\vec s_i + \vec e_i, \vec u_{i+1},\dots, \vec u_k).$$

Тогда проблема различения $H_i$ и $H_{i+1}$ можно свести к проблеме LWE. При использовании этого для конкретного анализа вещей это позволяет ограничить преимущество различения между $H_0$ и $H_k$ к $к$ раз превосходит различитель LWE.

Этот аргумент (и, в более общем смысле, техника повторного использования $А$) датируется как минимум Функции лазейки с потерями и их приложения Пайкерт и Уотерс в 2008 году. Он имеет некоторые умеренные правдоподобные преимущества, а именно:

1. в принципе можно стандартизировать единую матрицу $А$ которые используют все пользователи (подобно тому, как были стандартизированы группы DDH), или даже
2. можно "повторно использовать" сингл $А$ за относительно короткий, но все же нетривиальный период времени, скажем, 1 час.

Хотя, как правило, это уже не очень нравится. Это по двум основным причинам

1. можно получить сопоставимые сокращения размера $А$ путем обращения к структурированным версиям LWE (при одновременном повышении эффективности соответствующих операций) и
2. на практике не часто посылают $A\in\mathbb{Z}_q^{n\times m}$ по цене $nm\log_2q$ бит (который велик, что приводит к поиску аргументов амортизации, подобных тому, который вы предлагаете). Вместо этого вы можете просто отправить «seed» $\{0,1\}^\лямбда$, которая разлагается в случайную матрицу $А$ используя расширяемую функцию вывода в пункте назначения. Большинство кандидатов NIST PQC используют этот подход.

Также стоит упомянуть, что приведенная выше идея «стандартизированного экземпляра LWE» имеет несколько практических причин, по которым она, возможно, не подходит для больших временных масштабов, а именно:

1. он делает вас уязвимыми для атак с предварительным вычислением (аналогично другим стандартизациям группы DDH, скажем, атаке LogJam) и, что более важно,

2. можно построить «экземпляры LWE с бэкдором» — примерно распределение случайных матриц $А$ которые вычислительно неотличимы от случайных, но имеют «лазейку», которая позволяет взломать LWE.

Экземпляр LWE с бэкдором относительно прост (не помню, к сожалению, кому его приписать). Напомним, что предположение NTRU генерирует ключи открытым ключом $ч$, и секретный ключ $f$, такой, что $hf = g$ маленький". Используя соответствующую «матричную» форму вещей, мы получаем матрицы $Ч, Ф$ так что:

• $HF = G$ маленький, и
• $Ч$ вычислительно неотличима от равномерно случайной.

Тогда, если мы используем $H^t$ как случайная матрица экземпляра LWE, например. получить образец $(H^t, H^ts + E)$, мы можем легко разрушить предположение LWE, используя эту случайную матрицу, поскольку $F^t H^t s + F^t E = Gs + F^t E$ это "маленький" (я полагаю). Это все с матрицей $Ч$ быть вычислительно неотличимым от случайного в соответствии с NTRU, например. этот черный ход $Ч$ трудно обнаружить.