Tìm kiếm LWE để giảm SVP

Vì vậy, đối với luận án tốt nghiệp của tôi, tôi đang viết về hệ thống mật mã LWE của Regev từ bài báo gốc năm 2005 của anh ấy. Tôi đã hoàn thành với tính chính xác và bảo mật (chỉ giảm từ tìm kiếm LWE thông qua giảm từ trung bình đến kém nhất và giảm theo quyết định tìm kiếm, tuy nhiên, điểm chính của bài báo đó - giảm GapSVP sang tìm kiếm LWE nằm ngoài phạm vi của tôi work) nhưng bây giờ tôi muốn chứng minh một cuộc tấn công vào hệ thống mật mã đó bằng một cuộc tấn công vào khóa công khai. Tôi muốn làm điều đó bằng cách giảm tìm kiếm LWE thành SVP (hoặc CVP hoặc một cái gì đó tương tự) và sau đó sử dụng một số thuật toán để giải SVP, tốt nhất là một cái gì đó cổ điển như LLL (mặc dù tôi thậm chí không chắc liệu LLL có đúng không sự lựa chọn) vì tôi sẽ tìm hiểu rõ ràng và phong phú về tài liệu để nghiên cứu từ một số cải tiến cận biên (về lý thuyết) về hiệu quả của cuộc tấn công. Bất kỳ ai trong số các Bạn có thể chỉ cho tôi các bài báo phù hợp để giảm LWE thành SVP này hoặc điều gì đó mà Bạn có thể nghĩ là có liên quan và phù hợp với mức độ trưởng thành và kinh nghiệm (trong) của tôi trong lĩnh vực này. Cảm ơn trước.

Bạn đã vô tình vấp phải một chủ đề đặc biệt hóc búa/phân cực trong mật mã dựa trên mạng, cụ thể là cái được gọi là độ kín giảm từ tìm kiếm đến quyết định.

Tóm lại, một tuyên bố có dạng

Bất kỳ thuật toán nào $A$ chống lại vấn đề $A$ mà chạy trong thời gian $T_A$ với lợi thế $\epsilon_A$ ngụ ý một thuật toán $B$ chống lại vấn đề $B$ mà chạy trong thời gian $T_B$ lợi thế $\epsilon_B$.

là một cách đơn giản để tóm tắt quá trình giảm mật mã. Lý tưởng nhất là giảm chặt, nghĩa là cả hai:

1. $T_A\khoảng T_B$ (tốt nhất là khi $T_B = T_A$ cộng với một số chi phí nhỏ để chạy giảm), và
2. $\epsilon_A\approx \epsilon_B$.

Có (đại khái) hai khái niệm về độ kín, tiệm cận (nói đâu $T_B= O(T_A)$, và bê tông. Lưu ý rằng giảm với thời gian chạy $T_A = 2^{512}T_B$ là chặt chẽ tiệm cận, nhưng không chặt chẽ cụ thể.

Mức giảm của Regev rõ ràng là "không chặt chẽ". Về mặt kỹ thuật, việc xác định chính xác điều này có nghĩa là gì là phức tạp, vì vậy tôi sẽ chỉ liên kết với các tài liệu tương đối.

1. Một cái nhìn khác về sự chặt chẽ 2, lúc đầu đưa ra vấn đề về độ chặt của giảm (em nghĩ ở mục 6 hay 7 gì đó nhưng không nhớ).

2. Một Luận án thạc sĩ tuyên bố sẽ giảm bớt chặt chẽ hơn (và trực tiếp tham số hóa hệ thống mật mã dựa trên SVP, như bạn đang thảo luận), nhưng

3. (Một tập hợp con của) các tác giả của bài báo đầu tiên đưa ra một bài báo khác trong tháng này, cho rằng các tính toán của luận án là sai và việc rút gọn còn chưa chặt chẽ. Cũng có những tuyên bố thú vị khác ở đây --- Giảm Regev là một thuật toán BQP. Họ nhận thấy rằng nó không tầm thường, đặc biệt là thuật toán của Shor (cụ thể) dễ thực hiện hơn nhiều, điều này có lẽ không tuyệt vời.

cũng đã có một số cuộc thảo luận về nhóm google NIST-PQC có thể được quan tâm. Đại khái, Dan Bernstein nhận thấy khoảng cách chặt chẽ có vấn đề. Chris Peikert đã phác họa sự khác biệt giữa "sự chặt chẽ về lợi thế" ($\epsilon_A\approx \epsilon_B$) và "độ kín thời gian chạy" ($T_A\khoảng T_B$). Mặc dù có vẻ như người ta có thể cố gắng chính thức hóa sự khác biệt này, nhưng tôi không biết có bất kỳ bài viết nào về vấn đề này ngoài chuỗi email được liên kết.

Đây là tất cả để nói rằng nhiều tác giả đã gợi ý rằng ý nghĩa cụ thể giảm trường hợp xấu nhất đến trường hợp trung bình thành SVP không dẫn đến các khái niệm bảo mật có ý nghĩa, trừ khi người ta chọn vô cùng tham số lớn, không được sử dụng trong thực tế. "Các tham số nhỏ nhất" mà mọi người đã đạt được với chiến lược này vẫn còn lớn (xem luận văn thạc sĩ), và gần đây một số tác giả đã tuyên bố rằng các tham số "lớn, nhưng chỉ bằng hệ số 2x - 3x" này là không chính xác.

Mặc dù tất cả các tác phẩm này đều chứa các mô tả về việc giảm LWE thành SVP, nhưng tôi không chắc liệu có bất kỳ tác phẩm nào trong số đó sẽ đặc biệt hữu ích từ góc độ giải thích hay không. Tuy nhiên, đề xuất của bạn có ý nghĩa nhất với giả định rằng mức giảm rất chặt chẽ --- thật không may, đây không phải là trường hợp (giả sử tính chính xác của bài báo thứ nhất và thứ ba ở trên, mà tôi chưa đọc kỹ), vì vậy đề xuất của bạn có thể hơn khó khăn hơn bạn nghĩ.

Lưu ý rằng sự tồn tại của một khoảng cách chặt chẽ không không phải có nghĩa là LWE không an toàn, chỉ là (cụ thể) dựa trên tính bảo mật của LWE trên SVP là không thể. Do đó, hầu hết những người ủng hộ mật mã dựa trên lưới đã tiến hành như sau:

1. sử dụng sự tồn tại của trường hợp xấu nhất để giảm trường hợp trung bình để tranh luận định tính rằng "bản phân phối LWE" không phải là "thiếu sót về mặt cấu trúc". Là một ví dụ về phân phối "có sai sót về mặt cấu trúc" cho một vấn đề, RSA được biết là dễ dàng nếu $N = pq$ là như vậy $|p-q|$ nhỏ (thông qua Thuật toán bao thanh toán của Fermat). Điều này sẽ không bao giờ thực sự xảy ra nếu mọi thứ được tạo đúng cách, nhưng liên kết trước đã tìm thấy một số khóa được tạo không đúng cách.

2. đặt cụ thể các tham số dựa trên phân tích mật mã trực tiếp của LWE, giả sử sử dụng công cụ ước tính LWE.

Nếu mục tiêu chính của bạn chỉ là tấn công một phiên bản LWE, tôi khuyên bạn nên đọc công cụ ước tính LWE. Đại khái, nó được sử dụng để tham số hóa các phiên bản LWE. Nó thực hiện điều này bằng cách ước tính chi phí (cụ thể) của các cuộc tấn công đã biết khác nhau chống lại LWE. Có lẽ điều hợp lý nhất là bạn nên xem xét các cuộc tấn công đã biết này. Có nhiều tài nguyên tốt về các cuộc tấn công đã biết chống lại LWE, tuy nhiên tài liệu về công cụ ước tính LWE có lẽ là tài liệu cập nhật nhất.