SIS против проблемы LWE

Односторонняя функция Ajtai определяется как

$$f_A(x)= Ах \; мод\; д $$ где х $\в \{0,1\}^м$ и А $\in \mathbb{Z_q}^{n \times m}$. $f_A(x)$ односторонняя функция ( Ajtai 96)

В то время как функция Regev One way (Regev 05) определена для x $\in\mathbb{Z_q}^k$ и $e \in \mathscr{E}^m$ и А $\in\mathbb{Z_q}^{m \times k}$ .Односторонняя функция определяется как

$$g_A(x,e) =Ax +e \; мод\; д \; (LWE) $$

$г_А(х,е)$ является односторонней функцией.Мой вопрос заключается в том, обеспечивает ли односторонняя функция Regev преимущество перед односторонней функцией Ajtai с точки зрения разработки новых схем шифрования или они эквивалентны в отношении вариантов их использования? И эквивалентны ли они по твердости?

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

Напротив, режим Регева обычно используется в инъективном режиме. И мы знаем, как построить и схему шифрования из него.

Что касается твердости, решение SIS над $A^t$ совершенно прямо позволяет решить LWE над $А$. В другом направлении тоже есть редукция, которая является квантовой. Так что, по крайней мере, для квантовых компьютеров проблемы эквивалентны.

К этому следует относиться с долей скептицизма: при таком сокращении есть огромные потери. В частности, LWE с некоторый огромные параметры доказуемо квантово сложнее, чем SIS с некоторыми более разумными параметрами.