Tại sao RLWE nhẹ hơn LWE và tại sao chúng ta có thể chọn $a_i$ làm hoán vị của $a_1$ trong RLWE mà không phải LWE?

Trong LWE, chúng tôi có

$$<a_1,s> + e + \mu_1\in \mathbb{Z}_q$$

cho một khóa bí mật $s\in \{0,1\}^n$ và $a_1\in \mathbb{Z}_q^n$

Đây là một mã hóa của một số $\mu_1$. Nếu chúng ta muốn mã hóa $n$ khác biệt $\mu_i$, chúng tôi cần $n$ khác biệt $a_i$. Với $n$ giá trị $a_{11}, ..., a_{1n}$ chúng tôi đã có thể mã hóa một $\mu_1$.

Đối với RLWE, chúng tôi có

$$a*s +e + m \in \mathbb{Z}_q[X]^n$$

vì $a\in \mathbb{Z}_q[X]^n, e\in \mathbb{Z}_q[X]^n, m \in \mathbb{Z}_q[X]^n$, và $*$ là modulo nhân đa thức $x^n+1$. Đây là một mã hóa của một đa thức $m$ và do đó mã hóa của $n$ con số $m_1,...,m_n$. Với $n$ giá trị $a_1, ..., a_n$ chúng tôi đã có thể mã hóa $n$ con số.

Tôi nghĩ đây là ý nghĩa của câu trả lời này để giải thích: https://crypto.stackexchange.com/a/47602. Để mã hóa $n$ các giá trị trong LWE, chúng tôi cần bội số kích thước khóa của $n^2$ vì $a$'S. Đối với RLWE, chúng ta chỉ cần $n$. Tuy nhiên, vẫn còn đối với RLWE, trên trang 5 của PDF anh ấy đã liên kết, anh ấy nói rằng nếu chúng ta muốn mã hóa $n$ vectơ, chúng ta chỉ cần chọn $a_1\in \mathbb{Z}_q[X]^n$ và những cái khác $a_i$ như chức năng của $a_1$ như thế này: $$\vec{a_i} = (a_i, ..., a_n, -a_1, ..., -a_{i-1}).$$ Trước hết, tại sao điều này có thể được thực hiện cho RLWE mà không phải LWE? Đối với LWE, chúng ta có một loại hệ phương trình tuyến tính:

$$a_{i1}s_1 + a_{i2}s_2 + ... + a_{in}s_n + e_i = bi \mbox{ mod q}$$

điều đó được cho là khó giải quyết. Nếu chúng ta làm cho nó như vậy $a_{i}$ là một hoán vị của $a_1$ thì tôi nghĩ vấn đề không còn khó nữa. Tôi có đúng không? Nhưng tại sao nó vẫn khó trên RLWE? Có phải chỉ vì trên RLWE chúng ta không có hệ phương trình? Chúng ta có

$$a_i*s +e_i + m_i = b_i \mbox{ mod $x^n$ + 1}$$

có lẽ $a_i$ là một hoán vị của $a_1$ ở đây vẫn còn vấn đề khó khăn, tôi đoán vậy.

Đầu tiên, Regev đang mô tả rằng RLWE có thể được xem như một thể hiện "có cấu trúc" nhất định của LWE. Điều này là do

1. bạn có thể mô tả đa thức dưới dạng vectơ trong $\mathbb{Z}_q^n$,
2. bạn có thể mô tả phép cộng của đa thức theo phép cộng của vectơ trong $\mathbb{Z}_q^n$, và
3. bạn có thể mô tả phép nhân của đa thức $\bmod (x^n+1)$ về "tích vô hướng ngộ nghĩnh" của các vectơ trong $\mathbb{Z}_q^n$.

Bước cuối cùng là bước duy nhất thực sự không tầm thường. Tôi sẽ không rút ra tất cả ở đây, nhưng người ta có thể chỉ ra rằng $i$hệ số của tích đa thức $a(x)b(x)\bmod (q, x^n+1)$ có dạng $\langle \vec b, \mathsf{negacyclic}^{\circ i}(\vec a)\rangle$, ở đâu $\mathsf{negacyclic}^{\circ i}(\vec a)$ là $i$-gấp ứng dụng của phép toán dịch chuyển tròn $\vec a$ (sang trái hoặc phải, tôi luôn quên) và nhân các hệ số với $-1$ khi chúng "quấn lấy nhau". Một cách cụ thể, đó là $i$- lần lặp lại của hoạt động

$$(a_0,\dots,a_{n-1})\mapsto (-a_{n-1},a_0,\dots,a_{n-2}).$$

Điều này có nghĩa là người ta có thể chính xác mô tả một trường hợp RLWE $(a(x), a(x)s(x) + e(x))$ bằng cách viết lại mọi thứ dưới dạng các vectơ số nguyên. Đặc biệt, nếu bạn đặt $A$ là ma trận sau (trong đó $[a,b,c]$ là một ma trận với cột $a,b,c$)

$$A = [\mathsf{negacyclic}^{\circ 0}(\vec a),\mathsf{negacyclic}^{\circ 1}(\vec a),\dots, \mathsf{negacyclic}^{\ circ (n-1)}(\vec a)],$$

thì ví dụ RLWE đã nói ở trên chính xác tương ứng với ví dụ LWE $(A, Như + e)$. Như Regev đã đề cập, điều này $A$ không còn ngẫu nhiên thống nhất trên $\mathbb{Z}_q^{n\times n}$, như nó là toàn bộ theo quy định của $O(n)$ phần tử.

Trước hết, tại sao điều này có thể được thực hiện cho RLWE mà không phải LWE?

Để làm rõ, những gì đang được thực hiện là xem RLWE như một dạng có cấu trúc của LWE. Một sự đánh đổi một số giả định về cấu trúc trong $A$ cho một số tiết kiệm trong hiệu quả. Vì LWE là phiên bản "không có cấu trúc", người ta không thể giả định cấu trúc trong một đối tượng "không có cấu trúc".

Nếu chúng ta làm cho nó như vậy $\vec a_i$ là một hoán vị của $\vec a_1$ thì tôi nghĩ vấn đề không còn khó nữa.

Vì chúng tôi chỉ đơn giản là viết lại phiên bản RLWE của mình bằng một ngôn ngữ khác, phiên bản "LWE có cấu trúc" khó nếu phiên bản RLWE khó. Vì vậy, RLWE có thể được coi là nói rằng (đối với các hoán vị thích hợp) rằng vấn đề là vẫn cứng.

Lưu ý rằng không phải tất cả các hoán vị đều hoạt động. Điều này nhanh chóng trở thành kỹ thuật, nhưng $\mathbb{Z}_q[x]/(x^n-1)$ ban đầu được xem xét (bởi Micciancio, cho một biến thể Ring của vấn đề SIS). Đa thức này không phải là bất khả quy (nó có nghiệm tại $x = 1$). Khi đó tồn tại một phép đồng cấu (tương ứng với đánh giá đa thức tại 1) ánh xạ $a(x) \in\mathbb{Z}_q[x]/(x^n-1)\to \mathbb{Z}_q$, dẫn đến các cuộc tấn công. Dù sao, điều này có liên quan vì phép nhân trên $\mathbb{Z}_q[x]/(x^n-1)$ tương ứng với tuần hoàn hoán vị của $\vec a$ (chứ không phải là vòng âm những điều được mô tả ở trên).

Tất cả điều này có nghĩa là tập hợp tất cả các phiên bản RLWE có thể được xem như một tập hợp con của tập hợp tất cả các phiên bản LWE. Từ quan điểm này, RLWE có thể không khó hơn LWE --- bất kỳ thuật toán nào phá vỡ LWE đều phá vỡ RLWE. Người ta có thể tự hỏi "tập hợp con RLWE" dễ dàng hơn như thế nào --- có một số vấn đề về mạng đã biết khi mọi thứ trở nên nhiều dễ dàng hơn khi bạn giả định cấu trúc (tôi tin rằng SIVP là ví dụ chính). Đối với vấn đề RLWE, có thêm các ví dụ trong đó nếu tham số sai mọi thứ trở nên dễ dàng hơn, ví dụ như khi bạn sử dụng $x^n-1$ một đa thức bất khả quy. Ngoài ra còn có một số cuộc tấn công lượng tử không tầm thường vào một biến thể gần giống của vấn đề SVP đối với các phiên bản RLWE (tôi tin rằng đó là vấn đề về trình tạo nguyên tắc ngắn).

Không có điều nào ở trên ngụ ý (đối với đa thức như $x^{2^k}+1$, thường được sử dụng) các cuộc tấn công chống lại RLWE tốt hơn so với tồn tại đối với LWE. Có một số tác giả (cụ thể là Bernstein) tin rằng cấu trúc bổ sung sẽ hữu ích [1], nhưng vẫn chưa có gì được chỉ ra cụ thể.

[1] Ông tin rằng có điều gì đó sắc thái hơn liên quan đến kích thước của các nhóm Galois của đa thức đã chọn $f(x)$ được sử dụng trong RLWE. đa thức $x^{2^k}+1$ có một nhóm Galois nhỏ, có kích thước $O(\deg f)$. Kích thước của nhóm galois cực đại là $O((\deg f)!)$, lớn hơn nhiều. Các nhóm galois lớn hơn xuất hiện đối với các đa thức ngẫu nhiên w.h.p., và do đó "ít cấu trúc hơn". Không có cuộc tấn công được biết đến sử dụng nhóm Galois nhỏ của $x^{2^k}+1$.

"chúng ta có thể đơn giản chọn $a_i \in \mathbb{Z}_q[X]^n$" => Tôi nghĩ nó chỉ nên $\mathbb{Z}_q^n$.

Những gì bạn phải hiểu về đoạn này là thực tế là mã hóa

$\mu_0, \dots, \mu_{n-1}$ xem như một đa thức $\mu = \sum \mu_i X^i$ với RLWE và đa thức $\sum a_i X^i$, tương đương với việc mã hóa từng tọa độ $\mu_j$ với LWE và vectơ $\vec{a_j}=(a_{j}, a_{j+1}, \dots, a_{n-1}, -a_{1}, \dots, -a_{j-1})$.

Tại sao nó đúng? Bởi vì nếu chúng ta nhìn vào hệ số của $X^j$ Trong $a*s +e + \mu \in \mathbb{Z}_q[X]^n$, chúng tôi thu được chính xác

$<a_j,s> + e_j + \mu_j$ (với $e_j$ hệ số của $X^j$ cho đa thức $e$).

Về độ cứng của các giả định: RLWE là một giả định khác biệt (và dễ dàng hơn) so với LWE. Bảo mật của nó đã được nghiên cứu độc lập. Về giả định bạn đề xuất, nhưng tôi chỉ nhận xét:

• Bạn không chụp được RLWE (vì $-$).

• Đối với một số hoán vị, vấn đề trở nên dễ dàng hơn nhiều:

Ví dụ, nếu $\sigma = (1,2)(3,4)\dots(n-1, n).$ (với ký hiệu của bạn đó là $i_j = i_j + 1$ nếu $i_j$ là số lẻ, và $i_j -1$ nếu không).

Sau đó chúng tôi có $c_1= <a,s> + e_1 + \mu_1$, và $c_2 = \sum^{n/2}_{j=1} (a_{2j}s_{2j-1} + a_{2j-1}s_{2j}) + e_2 + \mu_2.$

sau đó $c_1 + c_2 = \sum^{n/2}_{j=1} (a_{2j}s_{2j-1} + a_{2j-1}s_{2j} + a_{2j}s_{2j} + a_{2j-1}s_{2j-1}) + e_1+ e_2 + \mu_1+ \mu_2.$

$=\sum^{n/2}_{j=1} (a_{2j} + a_{2j-1})(s_{2j-1} + s_{2j-1}) + e_1+ e_2 + (\ mu_1+ \mu_2).$

Sau đó, chúng tôi đã giảm kích thước của một yếu tố $2$.

Tôi sẽ muốn khái quát hóa, và nói với một hoán vị thứ tự $k$, bạn có thể giảm kích thước của một yếu tố $k$ (thì có lẽ nó không an toàn).