Mật mã dựa trên các vấn đề #P-đầy đủ

Có bất kỳ ví dụ nào về sơ đồ mật mã dựa trên (dạng trường hợp trung bình của) vấn đề #P-đầy đủ không?

Chúng tôi không biết làm thế nào để dựa trên mật mã ngay cả trên $\mathbf{NP}$-đầy đủ để một mình $\#\mathbf{P}$-sự đầy đủ. Hơn nữa, có những rào cản được biết đến đối với mật mã dựa trên $\mathbf{NP}$-sự đầy đủ: [AGGM,BT], và cả [Chương 7, B].

Điều đó nói rằng, người ta sẵn sàng đưa ra các giả định bổ sung sau đó $\#\mathbf{P}$-độ cứng có thể hữu ích: ví dụ: trong [CHK+], nó cho thấy rằng trong mô hình tiên tri ngẫu nhiên, độ cứng của $\#SAT$ (đầy đủ cho $\#\mathbf{P}$) có thể tạo ra các bản phân phối cứng của Nash, vấn đề về điện toán trạng thái cân bằng Nash (của trò chơi hai người chơi chẳng hạn).

[AGGM]: Akavia, Goldreich, Goldwasser và Moshkovitz, Dựa trên các chức năng một chiều dựa trên độ cứng NP, STOC 2006

[B]: Brzuszka, Trên nền tảng của trao đổi khóa, Luận án tiến sĩ, 2013

[BT]: Bogdanov và Trevisan, Về các trường hợp giảm từ trường hợp xấu nhất đến trường hợp trung bình đối với các sự cố NP, ĐẶT VẤN ĐỀ 2003

[CHK+]: Choudhuri và cộng sự, Tìm điểm cân bằng Nash không dễ hơn việc phá vỡ Fiat-Shamir, CỔ PHIẾU 2019

Cập nhật: Câu trả lời sau đây không bao gồm câu hỏi ban đầu. Đó là kết quả của sự bối rối p-đầy đủ với #p-đầy đủ.

Thuật toán mã hóa khóa công khai đầu tiên dựa trên bài toán p-đầy đủ. Nó ngày nay được gọi là Câu đố Merkle. Nói một cách đại khái, sự phức tạp của việc trao đổi khóa đối với bên nhận và bên gửi là $\mathcal{O}(n)$ trong khi độ phức tạp của một cuộc tấn công thành công là $\mathcal{O}(n^2)$.

Mặc dù trong mật mã hiện đại, nó không được coi là an toàn nữa, nhưng ý tưởng của Merkle đã thay đổi mọi thứ trong mật mã.