Я просто хочу знать, верно ли мое доказательство, которое заключается в доказательстве того, что если секрет Ring-LWE невелик, то он уникален. Прежде чем приводить доказательства, вот факт:
Факт 1: $\Pr [\Vert r \Vert_\infty \leq \beta: r\xleftarrow{\$} R_q]\leq \left(\dfrac{2\beta+1}{q}\right)^n$, куда $R_q=\mathbb{Z}_q[X]/(X^n+1)$, куда $n$ является степенью двойки, $q$ является простым и $\бета$ некоторое положительное действительное число.
Теперь позвольте $D_\сигма$ – дискретное распределение Гаусса на $R=\mathbb{Z}[X]/(X^n+1)$ (которую также можно рассматривать как дискретную гауссиану на $\mathbb{Z}^n$ через вложение коэффициентов из $R$ к $\mathbb{Z}^n$. Другой факт:
Факт 2: $\Pr[\Vert z\Vert_\infty \leq \mathcal{O}(\sigma\sqrt{n}): z\leftarrow D_\sigma]>1-2^{-n}$ для правильного выбора $\сигма$.
Теперь предположим, что $a\xleftarrow{\$}R_q$ и $s,e\leftarrow D_\sigma$ так что $b=как+е$, следовательно $(а,б)$ это образец RLWE для секрета $s$. Таким образом, $\Верт с\Верт_\infty,\Верт е\Верт_\infty$ оба меньше, чем $\beta=\mathcal{O}(\sigma\sqrt{n})$ с подавляющей вероятностью по Факту 2.
Теперь я хочу доказать, что невозможно найти другого $s^\prime, s^\prime\neq s$, $\Verts^\prime\Vert_\infty\leq\beta$ такой, что $b=as^\prime+e^\prime$, $\Vert e^\prime \Vert_\infty\leq \beta$ с подавляющей вероятностью. Вот мой аргумент:
Действуйте от противного. Предполагать $b=as^\prime+e^\prime$. (Предположим, что $а$ является обратимым элементом $R_q$, это имеет место с подавляющей вероятностью для случая $q=3\pmod{8}$). затем $s^\prime=a^{-1}(b-e^\prime)=a^{-1}(e-e^\prime)+s$. Таким образом, $(а^{-1},с^\простое число)$ это образец RLWE для секрета $е^\прим-е$ поскольку $а^{-1}$ является равномерно случайным в силу того, что $а$ является равномерно случайным. Следовательно, такие $s^\prime$ неотличим от равномерно случайного элемента в $R_q$ по предположению о принятии решений RLWE. Но по факту 1 для $q>4\бета +2$, вероятность того, что $\Verts^\prime\Vert_\infty\leq\beta$ является $<2^{-n}$. Отсюда такие маленькие $s$ уникален с подавляющей вероятностью. (Это также говорит о том, что если мы не накладываем никаких ограничений на норму $s$, секрет RLWE для $б$ не уникален, так как мы можем просто построить такие $s^\prime$).
Итак, я хотел бы знать, верен ли мой аргумент или нет, и был бы признателен за любую полезную обратную связь от кого-либо.
