Cuộc tấn công được tuyên bố không "phá vỡ" mật mã dựa trên mạng, chỉ cải thiện hơn nữa các cuộc tấn công đã biết.
Tôi sẽ cố gắng mô tả ngắn gọn tình hình.
tiệm cận:
Về mặt tiệm cận, dấu hiệu tốt nhất của chúng tôi là LWE cần có thời gian $2^{cn}$ để giải quyết một số hằng số $c$.
Điều này trái ngược với RSA $2^{(\log N)^{1/3}}$ (điều này rất không chính xác và nên sử dụng đúng cách ký hiệu L) và DLog đường cong elip $2^{\frac{1}{2}\log_2|\mathbb{G}|}$.
Điều này có nghĩa là, ngay cả với những cải tiến đối với các cuộc tấn công chống lại các biến thể LWE, chúng tôi tin rằng nó có "quy mô tốt hơn" so với các giả định như RSA (mà bạn đề cập cụ thể), mặc dù tương tự như ECDlog.
ước tính hiện tại của $c$ có thể khác nhau, nhưng nó là $< 1/2$ (Tôi tin có lẽ $\xấp xỉ 0,28$ là hiện tại, nhưng chưa được kiểm tra), vì vậy ECDlog là tốt nhất trên số liệu này, sau đó là LWE và sau đó (ở xa) RSA/trường hữu hạn DH.
Cũng không rõ khái niệm này hữu ích như thế nào trên thực tế --- nó nói rằng một số bộ thông số có thể an toàn, nhưng không giúp chọn cái nào.
cụ thể:
Ngay cả khi LWE làm cầm lấy $2^{cn}$ thời gian để giải quyết, điều này không giúp ích gì cho chúng tôi nếu chúng tôi không biết $c$.
Các cuộc tấn công được cải thiện (về mặt lý thuyết) đã được cải thiện $c$ tăng ca.
Điều này có thể dẫn đến các bộ tham số khác nhau bị "hỏng" (mặc dù không phải theo nghĩa là chúng ta có thể thực hiện các cuộc tấn công thực tế chống lại chúng --- theo nghĩa là chúng không đáp ứng các tiêu chuẩn tối thiểu của NIST để ở một "mức bảo mật" nhất định).
Tình trạng này được cho là tốt hơn hơn tình huống bao thanh toán đã trải qua với sự phát triển của các kỹ thuật "tính toán chỉ số".
Đối với ECDlog, các cuộc tấn công tốt nhất vẫn là (các biến thể của) thuật toán Pollard Rho, và nó đã xảy ra theo cách này đối với một Dài thời gian.
Đây là tất cả để nói rằng ECDlog cụ thể có bảo mật được hiểu rõ nhất, mặc dù tôi muốn nói rằng LWE vẫn đánh bại RSA/những thứ khác dễ bị tổn thương bởi các kỹ thuật tính toán chỉ số.
Mặc dù NFS đã được tạo ra ~ 30 năm trước, nhưng vẫn có thể tin rằng nó đã được cải thiện.
Ví dụ: con đường của DLog trường hữu hạn (đặc trưng nhỏ) là từ độ phức tạp gần giống như RSA, đến (đại khái) $2^{(\log p^n)^{1/4}}$, và sau đó đến thời gian gần như đa thức (xem Nadia Heninger, thông qua Matthew Green).
Điều này không có nghĩa là điều gì đó tương tự sẽ xảy ra với bao thanh toán (nó đã không xảy ra trong khoảng 30 năm qua), nhưng có lẽ đó vẫn là một khả năng không thoải mái.
Thực tế:
Cách cuối cùng để hiểu tính bảo mật của một giả định về độ cứng là giải các trường hợp thực sự lớn của nó.
Điều này dẫn đến câu hỏi
- bộ tham số lớn nhất đã bị phá vỡ trong một tính toán thực là gì?
- bao nhiêu thời gian đã được đầu tư vào tính toán này?
Đối với RSA, những thứ như RSA-240 (bán nguyên tố 768 bit) đã bị phá vỡ trong 1000 năm lõi (hoặc 6 tháng iirc).
Theo nghĩa này, RSA (và DH trường hữu hạn cho đặc tính không nhỏ) là giả định độ cứng được thử nghiệm tốt nhất (và có lẽ được hiểu rõ nhất) của chúng tôi.
Các đường cong elip cũng đã có những tính toán dài.
Các trang hồ sơ liệt kê một số điểm ngắt trong phạm vi nhóm kích thước $2^{110}$ đến $2^{120}$, và thời gian của đồng hồ treo tường lại lên đến 6 tháng đối với loại cao cấp.
Về số liệu này, LWE thực sự bị tụt lại phía sau.
Có một số "thử thách mạng tinh thể" nổi tiếng (la la những thách thức RSA), ví dụ như TU Darmstadt thách thức.
Đây là dành cho LWE đơn giản (Peikert đã làm một số cho RLWE, nhưng tôi không thấy bảng xếp hạng công khai dành cho họ).
Dù sao đi nữa, đối với các thử thách LWE đơn giản, kích thước cao nhất mà bất kỳ ai từng giải quyết là 85, trong khi kích thước 500+ (mặc dù 700+ phổ biến hơn) được sử dụng trong các sơ đồ thực tế.
Tất cả các bản ghi tôi đã xem được sử dụng chưa đến 200 giờ đồng hồ treo tường (thường là trên một số ít bộ xử lý), vì vậy các phép tính thực sự nhiều quy mô nhỏ hơn so với tính toán RSA/ECDlog.
Điều này có nghĩa là "các cuộc tấn công lớn" chống lại LWE ít nhất là nhỏ hơn một bậc so với các cuộc tấn công tương tự chống lại RSA/ECDlog, mặc dù điều này có thể làm giảm giá trị ồ ạt quy mô của các cuộc tấn công học thuật hiện đại chống lại RSA.
Vì vậy, cả phiên bản lớn nhất của LWE đã bị phá vỡ đều nhỏ (đây là một dấu hiệu bảo mật tốt) và nó chưa có "cuộc tấn công thực sự lớn" nào chống lại nó (đây là một cuộc tấn công tồi).
Ở trên bỏ qua nhiều điều tinh tế về các giả định về độ cứng, chẳng hạn như
- khả năng phục hồi rò rỉ,
- dễ thực hiện,
- dễ dàng giảm thiểu kênh phụ.
LWE thực sự hoạt động khá tốt trên tất cả các số liệu này (miễn là bạn không thực hiện chữ ký), chắc chắn tốt hơn RSA, mặc dù cá nhân tôi không biết về ECDlog.
Như đã nói, cá nhân tôi xem LWE là
- một to lớn cải tiến trên RSA/(trường hữu hạn)DLog, và
- có lẽ tệ hơn ECDlog.
Chắc chắn nếu máy tính lượng tử không phải là rủi ro, sẽ không có lý do gì để rời xa ECDlog (ngoại trừ các ứng dụng đặc biệt như FHE).
Nhưng họ là, vì vậy chúng ta phải.
Từ quan điểm này, không nên so sánh giữa LWE và RSA/ECDlog, vì thật không may, thế giới có ý nghĩa của chúng đang nhanh chóng rời bỏ chúng ta.
Thay vào đó, nên so sánh với các giả định hậu lượng tử khác.
Nhưng trong số các giả định hậu lượng tử, LWE thực sự đang dẫn đầu.
Có những giả định có độ bảo mật tốt hơn (chẳng hạn như McEliece), nhưng hiệu quả của chúng quá tệ nên không thể sử dụng được trừ những trường hợp đặc biệt.
Các giả định khả thi chính khác là
- NTRU, cũng dựa trên mạng và do đó không thực sự "độc lập" với các cuộc tấn công vào LWE, và
- SIDH.
Bản thân SIDH vẫn chậm hơn một bậc so với cấu trúc dựa trên lưới iirc (mặc dù nó nhỏ gọn hơn).
Có một số lý do để tranh luận rằng tính bảo mật của nó đã "đứng vững trước thử thách của thời gian" so với các giả định dựa trên mạng (cf Trường hợp cho SIKE), nhưng cũng là iirc mới chỉ có ~10 năm tuổi, do đó, bản thân nó vẫn là một giả định mới (và thậm chí còn hơn thế nữa vào năm 2016, khi NIST bắt đầu quá trình lựa chọn của mình).
Nó cũng khá phức tạp về mặt toán học, điều này có thể gây khó khăn cho việc triển khai (nhưng tôi chưa thử).
Điều này hơi dài (và bỏ qua nhiều chủ đề kỹ thuật, chẳng hạn như độ cứng của LWR "mô-đun nhỏ" hoặc tuyên bố về tác động của kích thước nhóm galois đối với độ cứng RLWE, những vấn đề chưa được giải quyết trong nhiều năm.
Đây là những chủ đề dường như có khả năng xảy ra "đột phá lớn" nhất, nhưng vẫn chưa có gì xảy ra), nhưng tôi hy vọng ít nhất cũng bắt đầu trả lời câu hỏi của bạn.
