Tôi chỉ muốn biết liệu chứng minh của tôi có chính xác hay không, tức là chứng minh rằng nếu bí mật Ring-LWE là nhỏ, thì nó là duy nhất. Trước khi đưa ra bằng chứng của tôi, đây là một sự thật:
Sự thật 1: $\Pr [\Vert r \Vert_\infty \leq \beta: r\xleftarrow{\$} R_q]\leq \left(\dfrac{2\beta+1}{q}\right)^n$, ở đâu $R_q=\mathbb{Z}_q[X]/(X^n+1)$, ở đâu $n$ là lũy thừa của hai, $q$ là một số nguyên tố và $\beta$ là một số thực dương.
Bây giờ, hãy để $D_\sigma$ là phân phối Gaussian rời rạc trên $R=\mathbb{Z}[X]/(X^n+1)$ (cũng có thể được xem như là Gaussian rời rạc trên $\mathbb{Z}^n$ thông qua hệ số nhúng từ $R$ đến $\mathbb{Z}^n$. Một thực tế khác:
Sự thật 2: $\Pr[\Vert z\Vert_\infty \leq \mathcal{O}(\sigma\sqrt{n}): z\leftarrow D_\sigma]>1-2^{-n}$ để có sự lựa chọn phù hợp $\sigma$.
Bây giờ giả sử rằng $a\xleftarrow{\$}R_q$ và $s,e\leftarrow D_\sigma$ để có thể $b=as+e$, vì thế $(a,b)$ là một mẫu RLWE cho bí mật $s$. Như vậy, $\Vert s\Vert_\infty,\Vert e\Vert_\infty$ cả hai đều ít hơn $\beta=\mathcal{O}(\sigma\sqrt{n})$ với xác suất áp đảo bởi Thực tế 2.
Bây giờ tôi muốn chứng minh rằng không thể tìm thấy cái khác $s^\số nguyên tố, s^\số nguyên tố\neq s$, $\Vert s^\prime\Vert_\infty\leq \beta$ như vậy mà $b=as^\prime+e^\prime$, $\Vert e^\prime \Vert_\infty\leq \beta$ với xác suất áp đảo. Đây là lập luận của tôi:
Tiến hành bằng mâu thuẫn. Giả sử $b=as^\prime+e^\prime$. (Giả sử $a$ là một phần tử khả nghịch của $R_q$, đây là trường hợp có xác suất áp đảo đối với trường hợp $q=3\pmod{8}$). sau đó $s^\prime=a^{-1}(b-e^\prime)=a^{-1}(e-e^\prime)+s$. Như vậy, $(a^{-1},s^\số nguyên tố)$ là một mẫu RLWE cho bí mật $e^\prime-e$ từ $a^{-1}$ là ngẫu nhiên thống nhất bởi thực tế là $a$ là ngẫu nhiên đều. Do đó, như vậy $s^\prime$ không thể phân biệt được với một yếu tố ngẫu nhiên thống nhất trong $R_q$ bởi giả định quyết định-RLWE. Nhưng bởi Thực tế 1, cho $q>4\beta +2$, xác suất mà $\Vert s^\prime \Vert_\infty \leq \beta$ Là $<2^{-n}$. Do đó, nhỏ như vậy $s$ là duy nhất với xác suất áp đảo. (Điều này cũng nói lên rằng nếu chúng ta không đặt bất kỳ hạn chế nào đối với định mức của $s$, bí mật RLWE cho $b$ không phải là duy nhất vì chúng ta có thể đơn giản xây dựng như vậy $s^\prime$).
Vì vậy, tôi muốn biết liệu lập luận của mình có đúng hay không và sẽ đánh giá cao bất kỳ phản hồi hữu ích nào từ bất kỳ ai.
