Trước tiên, tôi sẽ trả lời câu hỏi của bạn (có một câu trả lời khá đơn giản mà bạn có thể thất vọng), trước khi thảo luận về phần mở rộng nhẹ của vấn đề mà chúng tôi cho rằng máy tính lượng tử không thể giải quyết, mà bạn có thể quan tâm.
Là một lưu ý phụ nhanh chóng về nhận xét
Ít nhất là trong trường hợp bao thanh toán nếu $\log_2(p)=\log_2(q)=\log_2(k)$ thì việc giải phương trình là không thể về mặt lý thuyết thông tin vì về cơ bản nó chỉ là một miếng đệm một lần.
Nói chung, cách xử lý vấn đề này là nói rằng đối thủ sẽ thắng nếu họ phục hồi không tí nào giải pháp cho $x^2+y^2\bmod k$, chứ không phải là một số giải pháp cụ thể.
Điều này có thể được nhìn thấy trong những thứ như
- trò chơi khôi phục khóa nhất quán (chứ không phải trò chơi khôi phục khóa mục tiêu) và
- làm thế nào các chức năng một chiều cần khôi phục bất kỳ hình ảnh trước nào của $y$, ví dụ. không tí nào $x$ như vậy mà $f(x) = y$, thay vì một số "chính xác" $x'$ được chọn nội bộ trong trò chơi.
Tôi sẽ mô tả mọi thứ theo những thuật ngữ này, vì nó là tiêu chuẩn.
Nếu điều này không phù hợp với ứng dụng của bạn, có lẽ bạn nên cố gắng mô tả ứng dụng của mình nhiều hơn.
Câu hỏi này rất đơn giản: Thuật toán của Shor có thể giải các phương trình này trong thời gian đa thức khi chúng được thực hiện với số học hữu hạn thay vì trên các số nguyên không?
Tôi hiểu rằng thuật toán của Shor đang được mô tả trên $\mathbb{Z}$ còn hơn là $\mathbb{Z}_n$ không phải là một vấn đề nghiêm trọng với việc triển khai "thế giới thực" của nó. Đặc biệt, mặc dù người ta cần phải cẩn thận để các biểu diễn có độ chính xác hữu hạn mà người ta làm việc không quá "mất mát", nhưng tôi hiểu rằng những chi tiết này dễ xử lý hơn nhiều so với những thứ như xây dựng một máy tính lượng tử.
Với điều kiện sự hiểu biết này là chính xác, câu trả lời cho cả hai câu hỏi này gần như tầm thường --- giải các phương trình khác nhau trên $\mathbb{Z}$, và sau đó giảm các câu trả lời $\bmod k$ để có được giải pháp trên $\mathbb{Z}_k$. Như poncho chỉ ra trong các bình luận, vấn đề giải quyết $n = xy\bmod k$ vì $x, y$ là thậm chí cổ điển dễ dàng, vì vậy đạo đức của câu chuyện là việc áp đặt các ràng buộc mô-đun có thể làm cho vấn đề (có lẽ) dễ dàng hơn đáng kể, nhưng đối với những vấn đề này, chúng không làm cho vấn đề trở nên khó khăn hơn.
Có một phần mở rộng nhẹ của vấn đề giải quyết cho $n = xy \bmod k$ được cho là cứng lượng tử.
Việc giải quyết sự đồng dạng này có thể được coi là giải phương trình tuyến tính một biến (chính xác).
Có hai cách tự nhiên để khái quát hóa điều này
- nhiều hơn một biến, và
- nhiều hơn một phương trình.
Ví dụ: thay đổi vấn đề thành nơi một vấn đề được đưa ra $\vec b = A\vec s\bmod k$ ở đâu $\vec b\in\mathbb{Z}_k^n, A\in\mathbb{Z}_k^{n\times n}, \vec s\in\mathbb{Z}_k^n$.
Tuy nhiên, đây vẫn là chuyện nhỏ để "giải quyết" --- nếu bạn chọn $A$ là ma trận đơn vị, sau đó $\vec s = \vec b$ làm.
Tổng quát hơn, nếu bạn chọn $A$ không thể đảo ngược $\mathbb{Z}_k$, sau đó $\vec s = \vec A^{-1}\vec b$ làm.
Thậm chí nếu $\vec A$ không thể đảo ngược (giả sử nó không bình phương), có những điều bạn có thể làm bằng cách sử dụng các kỹ thuật đại số tuyến tính tổng quát.
Tất cả điều này đều hiệu quả và cổ điển, ví dụ: Shor vẫn còn quá mức cần thiết.
Nói chung, làm thế nào để ngăn chặn các cuộc tấn công trên là gấp đôi
chỉ định một số ma trận $A$ người ta phải sử dụng (vì vậy người ta không thể đặt $A$ là danh tính hoặc ma trận khả nghịch ngẫu nhiên) và
tiêm một số tiếng ồn vào vấn đề.
Lưu ý rằng chỉ điểm đầu tiên thôi là đủ (đòn tấn công của Poncho vẫn hoạt động), vì vậy điểm thứ hai nên được coi là cơ bản.
Cụ thể vấn đề như sau
Học Với Sai Lầm: Để cho $A\in\mathbb{Z}_k^{n\times n}$ là ngẫu nhiên thống nhất, và để cho $\vec s\in\mathbb{Z}_k^n$ là một vectơ "bí mật".
Đối với phân phối cố định $\chi$ hỗ trợ trên $\mathbb{Z}_k$, chúng tôi nói tìm kiếm học tập với lỗi vấn đề là phục hồi $\vec s$, được cho $(A, A\vec s + \vec e)$, ở đâu $\vec e \gets \chi^n$.
Tùy thuộc vào tham số hóa, vấn đề LWE là một trong những ứng cử viên hàng đầu cho giả định về độ cứng an toàn trước các máy tính lượng tử.
Điều này có nghĩa là, để khái quát hóa phù hợp việc giải quyết $n \equiv xy\bmod k$, người ta cho rằng thuật toán Shor không thể giải quyết vấn đề.
Tuy nhiên, như đã thấy ở trên, quá trình khái quát hóa được loại bỏ nhiều bước khỏi vấn đề ban đầu của bạn.
Có những cách khái quát hóa tương tự khác theo hướng này (Bài toán Tương đương học tập với tiếng ồn hoặc bài toán GCD gần đúng) --- điểm giống nhau cơ bản với tất cả chúng là bạn có một số biến thể "ồn ào" của một bài toán tuyến tính.
Ngoài ra còn có sự tổng quát hóa của $x^2+y^2\bmod k$ vấn đề được cho là an toàn lượng tử, nhưng tôi không biết nhiều chi tiết, vì vậy sẽ viết ít hơn.
Đại khái, người ta thay thế đa thức bậc hai $f(x, y) = x^2+y^2\bmod k$ với một Bất kỳ đa thức bậc hai (hoặc tập hợp các đa thức) trong $n$ biến.
Sau đó, vấn đề phục hồi $(x_1,\dots, x_n)$ đó là (đồng thời) các số 0 của đa thức bậc hai nhiều biến $p_0, \dots,p_m$ (đại khái) liên quan đến việc phá vỡ "Hệ thống mật mã đa biến".
Lưu ý rằng sự khăng khăng rằng người ta khôi phục các số 0 của đa thức (chứ không phải $p(x_0,\dots,x_n) = N$, như bạn yêu cầu) không làm mất tính tổng quát, vì người ta có thể khôi phục điều này bằng cách nhìn vào số 0 của $p(x_0,\dots,x_n) - N$.
Đây là tất cả để nói rằng
- Shor's được cho là sẽ phá vỡ cả hai vấn đề của bạn, nhưng
- có những khái quát về cả hai vấn đề của bạn được cho là an toàn lượng tử. Trên thực tế, nhiều giả thuyết an toàn lượng tử "hàng đầu" (mọi thứ tôi biết ngoại trừ những thứ mã hóa isogeny-stuff và thứ hạng) có thể được coi là sự khái quát hóa các vấn đề của bạn.
