Điểm:3

Độ chính xác giải mã của Mã hóa dựa trên RLWE

lá cờ br
zbo

Tôi gặp khó khăn trong việc chứng minh tính chính xác của quá trình giải mã trong Hệ thống mật mã dựa trên RLWE. Để nói rõ tôi đang ở đâu, trước tiên hãy để tôi trình bày sơ đồ đầy đủ. Hình ảnh từ chương 3.2 của tờ giấy này. nhập mô tả hình ảnh ở đây

Và bằng chứng giải mã đúng đắn của kế hoạch sau nhập mô tả hình ảnh ở đây

Trong bằng chứng này, tôi có thể nhận được phương trình cuối cùng thứ hai trong quy trình giải mã, tức là $$\mathbf{m} + (t/q)(\mathbf{v}-\epsilon \cdot \mathbf{m}) + t\cdot \mathbf{r} $$

Nhưng đối với phương trình cuối cùng tôi không biết tại sao. $$(t/q)||\mathbf{v}-\epsilon \cdot \mathbf{m}|| \lt 1/2 $$

Tôi có một số manh mối. chúng tôi đã có $||\mathbf{v}|| \le 2\cdot \delta_R \cdot B^2 + B$, Sau đó $2\cdot \delta_R \cdot B^2 + B \lt \Delta / 2$, chúng ta có $||\mathbf{v}|| \lt \frac{q}{2t}$ từ $\Delta = \lfloor q/t \rfloor \le q/t$. Vì thế $(t/q)||\mathbf{v}|| \lt \frac{1}{2}$. Điều này rất giống với những gì chúng tôi muốn, tức là $(t/q)||\mathbf{v}-\epsilon \cdot \mathbf{m}|| \lt 1/2 $.
Tôi đoán có một mối quan hệ giữa $||\mathbf{v}||$$||\mathbf{v}-\epsilon \cdot \mathbf{m}||$ , nhưng tôi không biết cách xây dựng mối quan hệ giữa chúng. Bằng chứng trong bài báo có một lời giải thích ngắn gọn "Vì $\mathbf{m} \in R_t$" , nhưng tôi không thể hiểu được. Bất kỳ ai cũng có thể đưa ra một số gợi ý hữu ích.

Thêm vào đó, định mức trong bài báo này ở định mức vô cực.

Chỉnh sửa20220601:
Thêm một số giải thích ở trên.

  1. $\delta_R $ được gọi là hệ số giãn nở của vành $R$. Và $\delta_R = \max{\frac{||a\cdot b||}{||a||\cdot ||b||}},a\in R, b\in R$.
  2. Ở trên, chúng ta có $\mathbf{v} = \mathbf{e}\cdot \mathbf{u}+ \mathbf{e}_1 +\mathbf{e}_2\cdot \mathbf{s}$, từ $\mathbf{e},\mathbf{u},\mathbf{e}_2,\mathbf{s} \in \chi$, nên chuẩn vô cực của chúng đều có giới hạn $B$, sau đó $||\mathbf{e}\cdot \mathbf{u}||= \frac{||\mathbf{e}\cdot \mathbf{u}||}{||\mathbf{e}||\cdot ||\mathbf{u}||}\cdot ||\mathbf{e}||\cdot ||\mathbf{u}|| \le \delta_R \cdot B^2$, tương tự, $||\mathbf{e}_2 \cdot \mathbf{s}|| \le \delta_R \cdot B^2$, vì vậy chúng tôi có $||\mathbf{v}|| \le 2\cdot \delta_R \cdot B^2 + B$
kelalaka avatar
lá cờ in
[Đăng chéo không phải là một đạo đức tốt trong SO](https://meta.stackexchange.com/questions/64068/is-cross-posting-a-question-on-multiple-stack-exchange-sites-permit-if -the-qu). Bạn có thể xóa bản sao toán học?
zbo avatar
lá cờ br
zbo
@kelalaka Xin lỗi, đã không nhận ra điều đó. Sẽ xóa nó ngay bây giờ.
Mark avatar
lá cờ ng
Có mối quan hệ giả định nào giữa $t$ và $q$ không? Rất đơn giản để có được giới hạn $(t/q)\lVert \epsilon\vec m\rVert_\infty \leq t^2/2q$. Với một giả định đủ mạnh về $t, q$, điều này đủ để gần như đạt được giới hạn của bạn (bạn sẽ mất một số yếu tố không đổi có thể bỏ qua trong cài đặt này).
zbo avatar
lá cờ br
zbo
Không có cuộc nói chuyện nào về mối quan hệ giữa $t$ và $q$ trong phần sơ bộ của bài báo . Nhưng trong một thư viện đồng hình như SEAL, về cơ bản chúng ta có các tham số như $t$ là $4096$ và $q$ là một số bit có kích thước $109$. $(t/q)||\mathbf{v} -\epsilon \cdot \mathbf{m}|| \le (t/q)(||\mathbf{v}||+\epsilon||\mathbf{m}|| ) \le (t/q)(\Delta/2)+ (t/q)( \epsilon \cdot (t/2)) \le (t/q)\cdot (q/2t)+(t/q)(\epsilon \cdot (t/2) ) = 1/2 + \frac{\ epsilon \cdot t^2}{2q}$
zbo avatar
lá cờ br
zbo
@Mark Trong cài đặt tham số, $\frac{\epsilon \cdot t^2}{2q}$ nhỏ, có thể không đáng kể, nhưng tôi vẫn không thể đặt nó nhỏ hơn $\frac{1}{2}$
Mark avatar
lá cờ ng
Bây giờ tôi không có thời gian để xem qua bài báo, nhưng có lẽ điều đáng nói là nếu $t\mid q$, thật dễ dàng để chỉ ra rằng $\epsilon =0$, và toàn bộ vấn đề này sẽ biến mất. Đây là cài đặt phổ biến nhất (cả thực tế và lý thuyết), mặc dù nó không giải quyết đầy đủ câu hỏi của bạn.
zbo avatar
lá cờ br
zbo
@Mark Cảm ơn, tôi bị mắc kẹt trong phần chứng minh này và không đọc tiếp bài báo sau, có vẻ như các thông số làm cho mọi thứ khác đi rất nhiều.

Đăng câu trả lời

Hầu hết mọi người không hiểu rằng việc đặt nhiều câu hỏi sẽ mở ra cơ hội học hỏi và cải thiện mối quan hệ giữa các cá nhân. Ví dụ, trong các nghiên cứu của Alison, mặc dù mọi người có thể nhớ chính xác có bao nhiêu câu hỏi đã được đặt ra trong các cuộc trò chuyện của họ, nhưng họ không trực giác nhận ra mối liên hệ giữa câu hỏi và sự yêu thích. Qua bốn nghiên cứu, trong đó những người tham gia tự tham gia vào các cuộc trò chuyện hoặc đọc bản ghi lại các cuộc trò chuyện của người khác, mọi người có xu hướng không nhận ra rằng việc đặt câu hỏi sẽ ảnh hưởng—hoặc đã ảnh hưởng—mức độ thân thiện giữa những người đối thoại.