3 ms·
The main type of zero-knowledge proofs are a subset (potentially proper subset) of interactive proofs. All problems that have an interactive proof form a comple
by Kranar 5y ago
The main type of zero-knowledge proofs are a subset (potentially proper subset) of interactive proofs. All problems that have an interactive proof form a complexity class called IP, and IP is currently believed to be a subset of PSPACE.
So no, not all provable statements are zero-knowledge provable if by zero-knowledge proof you mean an interactive proof where no information is transferred.
Of course it's possible that in the future, other types of zero knowledge proofs will be formulated that are not interactive proofs. For example there are zk-SNARKs that are non-interactive and zero knowledge, but they form a subset of IP and in fact are a subset of NP problems.
- tooltower 5y ago> IP is currently believed to be a subset of PSPACE. IP is _known_ to be _equal_ to PSPACE
- Kranar 5y agoWell there you go, Wikipedia confirms that IP = PSPACE, and furthermore that if some assumptions hold about one-way functions, then zero knowledge IP = IP = PSPACE. Thanks for your correction. https://en.wikipedia.org/wiki/IP_(complexity) https://en.wikipedia.org/wiki/IP_(complexity)