tag:blogger.com,1999:blog-3722233.post6817129401606575319..comments2022-12-06T20:23:11.390-06:00Comments on Computational Complexity: PSPACE is contained in Zero Knowledge!! How come nobody seems to care?Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger5125tag:blogger.com,1999:blog-3722233.post-29393160583357716892022-02-07T11:35:59.632-06:002022-02-07T11:35:59.632-06:00You can interpret this result as a generic transfo...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.JTnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-29162741385037644852022-02-07T11:08:46.879-06:002022-02-07T11:08:46.879-06:00IP \subset ZK is really trivial given NP \subset Z...IP \subset ZK is really trivial given NP \subset ZK (the proof could be explained in a sentence), that may be the reason.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-34821685005206237552022-02-07T02:07:29.517-06:002022-02-07T02:07:29.517-06:00I'd guess two reasons:
- NP in ZK is a condit...I'd guess two reasons:<br /><br />- 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.<br /><br />- 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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-70695925661357517362022-02-06T19:37:55.709-06:002022-02-06T19:37:55.709-06:001) Great cartoon!
2) AH- yes, the proof that NP su...1) Great cartoon!<br />2) AH- yes, the proof that NP subseteq ZK can be explained to the <br />layperson on an intuitive level. Having done that, maybe even NP in IP an be explained. But IP=PSPACE.... not so much.gasarchhttps://www.blogger.com/profile/03004932739846901628noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-3782134662534447572022-02-06T18:39:04.651-06:002022-02-06T18:39:04.651-06:00I did a comic about NP in zero knowledge: quackack...I did a comic about NP in zero knowledge: quackack.com/84. 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.<br /><br />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.Anonymoushttps://www.blogger.com/profile/13145307157323355035noreply@blogger.com