Tại sao các giao thức Zero-Knowledge được sử dụng cho các vấn đề NP nếu IP là loại hệ thống bằng chứng tương tác mà chúng đến từ đâu?

Lý do là về bản chất, lớp ngôn ngữ trong $\mathcal IP$ không có trong $\mathcal NP$ không thể được chứng minh với một chứng minh hiệu quả. Vì chúng ta thường quan tâm đến bối cảnh mật mã với các bộ chứng minh hiệu quả, nên nghiên cứu về ZK thường tập trung vào $\mathcal NP$. (Lưu ý rằng khi nghiên cứu độ phức tạp và thường là trong nền tảng của mật mã, chúng tôi chắc chắn quan tâm đến các chứng minh không hiệu quả.)

Để xem tại sao bên ngoài $\mathcal NP$ người chứng minh không thể hiệu quả, hãy lưu ý rằng bất kỳ bằng chứng tương tác nào với người chứng minh hiệu quả (được cung cấp nhân chứng) đều có thể được mô phỏng bởi một máy nhận nhân chứng và chạy bằng chứng cục bộ, kiểm tra xem kết quả có được chấp nhận hay từ chối. Đây đúng là lớp ngôn ngữ $\mathcal MA$. Theo các giả định phi ngẫu nhiên hóa tiêu chuẩn, $\mathcal MA = NP$. Do đó, theo những giả định này, bất kỳ ngôn ngữ nào không có trong $\mathcal NP$ chỉ có thể được chạy với một câu châm ngôn không hiệu quả (thậm chí đưa ra một số bằng chứng). Như vậy, nó ít được quan tâm hơn khi xây dựng các giao thức và những thứ tương tự.