Đầu tiên tôi muốn định nghĩa chính xác hơn về "cùng $x$" tấn công.
giải thích đầu tiên
Alice và Bob biết họ $x$ giống nhau. Điều đó không hợp lý, bởi vì trong trường hợp này, họ đã chia sẻ thông tin bí mật (họ đã có thể tính khóa công khai chung $g^x$ không có bất kỳ giao tiếp nào).
giải thích thứ hai
Bây giờ, giả sử, đối thủ có thể ép buộc (chúng ta không biết bằng cách nào) $x$ bằng với $y$ (Nhưng Alice và Bob không biết điều đó rồi giao tiếp $g^x$). Sau đó, mục tiêu của đối thủ là tính toán $g^{x^2}$ bằng cách biết $g^x$. Vấn đề này được biết là khó trong mô hình chung (bạn có thể xem ví dụ cái này), và sau đó có lẽ cũng khó đối với nhóm cụ thể được chọn tốt.
giải thích thứ ba
Alice và Bob tôn trọng giao thức, nhưng họ không may chọn giống nhau $x$, điều đáng chú ý là đối thủ có thể dễ dàng phát hiện ra trường hợp này. Nhưng điện toán $g^{x^2}$ khó như trong trường hợp thứ hai.
Giới thiệu về LWE
tôi sẽ xem xét phiên bản này của trao đổi khóa DH:
Về cách giải thích đầu tiên, nó không có ý nghĩa đối với DH.
Một nhận xét quan trọng là trên thực tế, ngay cả Alice và Bob cũng có cùng $x$, các khóa một phần được gửi không giống nhau (trái ngược với khóa trong DH). Đầu tiên bởi vì họ tính toán $x^\perp A$ và $Ax$, và cũng bởi vì không có lý do gì mà chúng lại có tiếng ồn giống nhau.
Vì lý do này, việc phát hiện đẳng thức trong trường hợp thứ ba là không tầm thường, (ít nhất là không tầm thường như trong trường hợp DH).
Về thực tế để tính toán bí mật $x$ trong trường hợp thứ hai. Nó có vẻ khó, nhưng theo như tôi biết thì không có kết quả nào về độ khó của vấn đề cụ thể này.
Chúng ta có thể định dạng lại cả hai vấn đề. Cho một ma trận vuông $A$, có khó không
phân biệt $(Ax+ 2e, x^\perp A+ 2e')$ và $(Ax+ 2e, y^\perp A+ 2e')$?
Và đưa ra $(Ax+ 2e, x^\perp A+ 2e')$ có khó đoán chút ít quan trọng nhất của $x^\perp Ax$.
Tôi muốn nghĩ rằng cả hai vấn đề đều khó khăn. Nhưng theo như tôi biết, nó không thể giảm xuống bất kỳ vấn đề khó khăn nào đã biết.
