NP là tập các bài toán quyết định có thể kiểm chứng hiệu quả. Đưa ra một ví dụ $x$ của vấn đề quyết định, có một "chứng minh" ngắn $w$ rằng, đưa ra cặp $(x, w)$, người ta có thể xác minh một cách hiệu quả rằng $x$ là đúng.
coNP là tập các bài toán quyết định bác bỏ một cách hiệu quả. Đưa ra một ví dụ $x$ của vấn đề quyết định, có một "bằng chứng" ngắn $w$ rằng, đưa ra cặp $(x, w)$, người ta có thể xác minh một cách hiệu quả rằng $x$ là sai.
Về cơ bản, đối với tất cả các lược đồ mã hóa khóa công khai đã biết, các khóa công khai tạo thành một bộ NP.
Điều đó có nghĩa là gì?
Đưa ra một số khóa công khai $pk$, có một số thông tin bổ sung $sk$ (khóa bí mật) sao cho người ta có thể xác minh một cách hiệu quả rằng $pk$ là khóa công khai đối với khóa bí mật $sk$.
Ví dụ
cho RSA, $N = pq$. đưa ra một số $N'$ có thể có hoặc không có hình thức này, chúng tôi có thể xác minh một cách hiệu quả thông qua nhân chứng $(p, q)$.
đối với các giả định loại DLOG, đưa ra một số $(g, g^s)$, chúng ta có thể xác minh một cách hiệu quả tương tự rằng $g^s$ lấy mẫu đơn này thông qua nhân chứng $s$
đối với các sơ đồ mạng/dựa trên mã, được cung cấp một số $(A, Như + e)$, chúng tôi có thể xác minh một cách hiệu quả rằng $(As + e)$ lấy mẫu đơn này thông qua nhân chứng $(s, e)$.
Tất cả điều này để nói rằng, với khóa bí mật của một số PKE, thông thường khá dễ dàng để xác minh khóa chung được cấu trúc chính xác (và không chỉ đơn giản là một số yếu tố ngẫu nhiên).
Bây giờ, khóa công khai sẽ nằm trong bộ coNP nếu, được cung cấp một số "$pk$" đó là không phải một khóa công khai (và thay vào đó chỉ đơn giản là một số "yếu tố ngẫu nhiên"), người ta có thể xác minh điều này một cách hiệu quả.
Ví dụ: đối với RSA, nếu ai đó đưa cho bạn một số $N$ điều đó không thể được viết như $N = pq$, bạn có thể xác minh điều này một cách hiệu quả thông qua một hệ số hoàn chỉnh của $N = \prod_i p_i^{e_i}$. $((p_1, e_1),\dots,(p_k,e_k))$ do đó đóng vai trò là nhân chứng cho $N$ không phải là khóa công khai RSA và theo nghĩa này, khóa công khai RSA vừa là tập hợp NP vừa là tập hợp coNP.
Yêu cầu của phần đó của bài báo là điều kiện tiên quyết
mã hóa là xác định và bộ khóa công khai tạo thành bộ coNP.
là hạn chế. Cá nhân tôi xem phần đầu tiên của điều này là hạn chế hơn phần thứ hai.
Ví dụ, đối với tôi, có vẻ như trong cả ba ví dụ tôi đã đề cập ở trên, các khóa công khai tạo thành một bộ coNP.
Trong hai ví dụ đầu tiên, điều đó là hiển nhiên và trong ví dụ thứ ba, tôi nghĩ rằng việc giảm cơ sở đủ mạnh có thể/nên hoạt động như một nhân chứng, đặc biệt nếu $B$ là một cơ sở đủ ngắn cho đối ngẫu của $\mathcal{L}(A)$, sau đó $(BA + Be)$ sẽ là một vectơ ngắn bất thường đối với mẫu "LWE thực", nhưng sẽ là ngẫu nhiên thống nhất đối với một mẫu ngẫu nhiên, ví dụ: sẽ là một nhân chứng coNP.
