Предположим, что $n$ является степенью двойки, $q=3\pmod 8$, простой и $R=\mathbb{Z}[X]/(X^n+1)$. Обозначать $\Верт\cdot\Верт$ как норма бесконечности в $R_q=R/qR$ на коэффициенты элементов в $R_q$. Предполагается, что коэффициенты находятся в $[-\frac{q-1}{2},\frac{q-1}{2}]$. Я просто приведу некоторые факты, которые буду использовать в своем доказательстве:
- $Х^n+1$ делит на два неприводимых множителя по модулю $q$, где каждый фактор имеет степень $n/2$ см. лемму 3 здесь
- Вследствие указанного выше факта при фиксированном $s\в R_q$, $s\neq 0$, количество различных $a\cdot s\in R_q$, в целом $a\в R_q$ по крайней мере $q^{n/2}$, как утверждается, но без строгих доказательств от стр. 7.
Теперь я утверждаю, что при заданном равномерно случайном $a\в R_q$, образец RLWE $b=как+е$ (куда $с,е$ выбираются из дискретного распределения Гаусса на $\mathbb{Z}^n$ так что с большой вероятностью $\Vert s\Vert, \Vert e\Vert\leq \beta$, для некоторых $\бета$) имеет уникальный секрет $s$.
Итак, доказательство идет от противного:
- Предположим, что задано равномерно случайное $a\в R_q$, Предположим, что $b=as+e=as^\prime+e^\prime$, куда $s\neqs^\prime$ и $s,s^\prime,e,e^\prime$ выбираются из приведенного выше дискретного гауссовского распределения так, что все их нормы равны $\leq\бета$ с подавляющей вероятностью.
- Таким образом, мы можем переписать приведенное выше уравнение как $a(s-s^\prime)=(e^\prime-e)$ и мы утверждаем, что это происходит с пренебрежимо малой вероятностью для всех таких $a,s,s^\prime,e,e^\prime$.
- Работаем в несколько шагов: Сначала фиксируем $е,е^\прим,с,с^\прим$ и спросите вероятность того, что приведенное выше уравнение выполняется для всех $a\в R_q$, то есть какова вероятность того, что $a(s-s^\prime)=(e^\prime-e)$ для равномерно случайного $a\в R_q$? Мой ответ на этот вопрос таков: поскольку $ а (s-s ^ \ простое число) $ занимает по крайней мере $q^{n/2}$ везде разные значения $a\в R_q$, то приведенное выше уравнение выполняется с вероятностью $\leq \dfrac{1}{q^{n/2}}$.
- Наконец, мы берем объединение, связанное по всем $s,s^\prime,e,e^\prime$ взятые из дискретного распределения Гаусса так, что все они имеют нормы $\leq\бета$ с подавляющей вероятностью, то общая вероятность того, что $a(s-s^\prime)=(e^\prime-e)$ является $\leq \dfrac{(2\beta+1)^{4n}}{q^{n/2}}$, так как количество элементов в $R_q$ что имеет норму бесконечности меньше, чем $\бета$ является $(2\бета+1)^n$ и по неравенству треугольника.
Я показал это доказательство своему профессору, но оно не имеет для него смысла, и сказал, что я делаю глупую ошибку, особенно на шаге 3 моего доказательства.
Прямо сейчас я не понимаю, почему мое доказательство неверно, и он не упомянул, почему мое доказательство неверно. Я попытался объяснить ему свое доказательство, но был закрыт, так как для него я сделал ужасную ошибку.
Так что любой, кто может помочь и пролить свет на этот вопрос, очень ценится.
