Giả sử rằng $n$ là lũy thừa của hai, $q=3\pmod 8$, số nguyên tố và $R=\mathbb{Z}[X]/(X^n+1)$. Chứng tỏ $\Vert\cdot\Vert$ như chuẩn vô cực trong $R_q=R/qR$ về hệ số của các phần tử trong $R_q$. Các hệ số được giả định là trong $[-\frac{q-1}{2},\frac{q-1}{2}]$. Tôi sẽ chỉ trích dẫn một số sự thật mà tôi sẽ sử dụng trong bằng chứng của mình:
- $X^n+1$ thừa số thành hai thừa số bất khả quy modulo $q$, trong đó mỗi yếu tố có mức độ $n/2$ xem Bổ đề 3 của đây
- Như một hệ quả của thực tế trên, đưa ra một cố định $s\in R_q$, $s\neq 0$, số lượng khác biệt $a\cdot s\in R_q$, tổng thể $a\trong R_q$ là ít nhất $q^{n/2}$, như đã tuyên bố nhưng không có bằng chứng chặt chẽ từ trang 7.
Bây giờ yêu cầu của tôi là được đưa ra một cách ngẫu nhiên thống nhất $a\trong R_q$, một mẫu RLWE $b=as+e$ (ở đâu $s,e$ được chọn từ một phân phối Gaussian rời rạc trên $\mathbb{Z}^n$ để với xác suất áp đảo, $\Vert s\Vert, \Vert e\Vert\leq \beta$, đối với một số $\beta$) có một bí mật độc đáo $s$.
Vì vậy, bằng chứng đi theo mâu thuẫn:
- Giả sử rằng đã cho một ngẫu nhiên thống nhất $a\trong R_q$, giả sử $b=as+e=as^\prime+e^\prime$, ở đâu $s\neq s^\prime$ và $s,s^\prime,e,e^\prime$ được chọn từ phân phối Gaussian rời rạc ở trên để tất cả các chỉ tiêu của chúng là $\leq \beta$ với xác suất áp đảo.
- Do đó, chúng ta có thể viết lại phương trình trên dưới dạng $a(s-s^\prime)=(e^\prime-e)$ và chúng tôi tuyên bố rằng điều này chỉ xảy ra với xác suất không đáng kể trên tất cả các $a,s,s^\prime,e,e^\prime$.
- Chúng tôi tiến hành theo một số bước: Đầu tiên, sửa $e,e^\prime,s,s^\prime$ và hỏi xác suất để phương trình trên đúng với tất cả $a\trong R_q$, nghĩa là, xác suất mà $a(s-s^\prime)=(e^\prime-e)$ cho một thống nhất ngẫu nhiên $a\trong R_q$? Câu trả lời của tôi cho câu hỏi này là vì $a(s-s^\prime)$ mất ít nhất $q^{n/2}$ các giá trị khác nhau trên tất cả $a\trong R_q$, thì phương trình trên đúng với xác suất $\leq \dfrac{1}{q^{n/2}}$.
- Cuối cùng, chúng tôi đưa công đoàn ràng buộc trên tất cả $s,s^\prime,e,e^\prime$ được lấy từ phân phối Gaussian rời rạc để tất cả chúng đều có chuẩn $\leq \beta$ với xác suất áp đảo, thì xác suất chung mà $a(s-s^\prime)=(e^\prime-e)$ Là $\leq \dfrac{(2\beta+1)^{4n}}{q^{n/2}}$, vì số phần tử trong $R_q$ có chuẩn vô cực nhỏ hơn $\beta$ Là $(2\beta+1)^n$ và bằng bất đẳng thức tam giác.
Tôi đã đưa chứng minh này cho giáo sư của mình xem nhưng ông ấy thấy vô nghĩa và nói rằng tôi đang mắc một lỗi ngớ ngẩn, đặc biệt ở bước 3 của chứng minh.
Ngay bây giờ, tôi không hiểu tại sao chứng minh của tôi không chính xác và anh ấy không đề cập đến lý do tại sao chứng minh của tôi sai. Tôi đã cố gắng giải thích cho anh ấy bằng chứng của mình nhưng đã bị tắt vì đối với anh ấy, tôi đã phạm một sai lầm khủng khiếp.
Vì vậy, bất kỳ ai có thể giúp đỡ và làm sáng tỏ vấn đề này đều được đánh giá cao.
