Sunday, February 06, 2022

PSPACE is contained in Zero Knowledge!! How come nobody seems to care?

(This post was inspired by Lance's post on Zero Knowledge, here, which was inspired by a video he has in the post which was inspired by... (I think this ordering is well founded.))

 ZK= Zero Knowledge.

When it was shown that NP \subseteq ZK this was a big deal. This was by Goldreich-Micali-Wigderson  (see here (FOCS-1986, JACM-1991). In the JACM paper they have the following passage:

Our result that all languages in NP have zero-knowledge proof systems, has been extended to IP, assuming the same assumptions. (The result was first proved by Impagliazzo and Yung, but since their paper [53] contains only a claim of the result, the interested reader is directed to [11] where a (different proof) appears.) In other words, whatever can be efficiently proven can be efficiently proven in a zero-knowledge manner. This may be viewed as the best result possible, since only languages having interactive proof systems can have zero-knowledge interactive proof systems.

11. BEN-OR, M., GOLDREICH, O., GOLDWASSER, S., HASTAD, J., KILLIAN, J., MICALI, S,,  AND ROGAWAY, P. Everything provable is provable in zero-knowledge. In Proceedings of Advances in Cryptology— Crypto88. Lecture Notes in Computer Science, vol. 403. Springer-Verlag, New York, 1990, pp. 37-56.

53.IMPAGLIAZZO. R., AND YUNG, M. Direct minimum-knowledge computations. In C. Pomerance, ed., Proceedings of Advances in Cryptology— Crypto87. Lecture Notes in Computer Science, vol. 293. Springer-Verlag, New York, 1987, pp. 40-51.
Later the papers of Lund-Fortnow-Karloff-Nisan and Shamir showed IP=PSPACE. Hence

PSPACE \subseteq ZK

When I realized this I thought OH, that's interesting! I then looked around the web and could not find any mention of it. I asked Lance and some people in crypto and yeah, they all knew it was true, but nobody seemed to care.

Why the apathy? Speculation:

1) ZK is a notion people actually want to use in real crypto (and there has been some progress on that lately). The prover for ZK in PSPACE has to be way to powerful to be practical. I don't really like this explanation since we are talking about theorists. Even in crypto, which has more of a connection to the real works then, say, Ramsey Theory, there are still plenty of non-useful results. 

2) IP=PSPACE was the big news and  had interesting proof with nice ideas. Nothing crypto-ish about it. So the corollary that PSPACE \subseteq ZK is an afterthought. 

3) SAT in ZK was big news. IP in ZK is nice, but uses mostly the same ideas.

4) I am WRONG- it is a celebrated result and I somehow missed the celebration.

5) The proof that ZK is in PSPACE USES two interesting results, but adds NOTHING to the mix. In short, the proof is to easy.

Any other ideas?


  1. I did a comic about NP in zero knowledge: When I made it, I found it surprising how easily it could be extended to PSPACE and would have liked to do a follow up.

    But it sort of falls into the same issue that making a comic about IP=PSPACE does. The IP=PSPACE protocol is just difficult to explain quickly in an easy and intuitive way. And I don't feel comfortable assuming that readers know it.

    1. 1) Great cartoon!
      2) AH- yes, the proof that NP subseteq ZK can be explained to the
      layperson on an intuitive level. Having done that, maybe even NP in IP an be explained. But IP=PSPACE.... not so much.

  2. I'd guess two reasons:

    - NP in ZK is a conditional result (albeit with a condition that we tend to believe in secure encryption) unlike IP=PSPACE. The result will not apply to SZK unless we get a surprising complexity collapse.

    - ZK is mostly interesting in a practical cryptographic context where many rounds of interaction is a problem. Bounded round ZK or NIZK is where the main interest lies from that point of view. Again, without a stunning complexity collapse, PSPACE doesn't seem likely to be in bounded-round ZK since the IP=PSPACE proof critically relies on unbounded rounds of interaction.

  3. IP \subset ZK is really trivial given NP \subset ZK (the proof could be explained in a sentence), that may be the reason.

  4. You can interpret this result as a generic transformation of any (non-zero-knowledge) protocol into a zero-knowledge one (PSPACE in zero-knowledge then just follows form IP=PSPACE). People do care about such non-zk-to-zk transformations, even in practice. E.g., most zk-SNARKs today are designed by first giving a non-zero-knowledge SNARK and then finding a way to "add" zero-knowledge to it without much overhead. Of course, far more practical transformations are now known than the one given in [11]. And there can be concrete benefits to tailoring the transformation to the non-zk protocol at hand, rather than using a totally generic transformation.