Can Statistical Zero Knowledge be made Non-interactive? or On the Relationship of SZK and NISZK
We extend the study of non-interactive statistical zero-knowledge proofs. Our main focus is to compare the class NISZK of problems possessing such non-interactive proofs to the class SZK of problems possessing interactive statistical zero-knowledge proofs. Along these lines, we first show that if st...
| Main Authors: | , , |
|---|---|
| Published: |
2023
|
| Online Access: | https://hdl.handle.net/1721.1/149287 |
| _version_ | 1826206303544934400 |
|---|---|
| author | Goldreich, Oded Sahai, Amit Vadhan, Salil |
| author_facet | Goldreich, Oded Sahai, Amit Vadhan, Salil |
| author_sort | Goldreich, Oded |
| collection | MIT |
| description | We extend the study of non-interactive statistical zero-knowledge proofs. Our main focus is to compare the class NISZK of problems possessing such non-interactive proofs to the class SZK of problems possessing interactive statistical zero-knowledge proofs. Along these lines, we first show that if statistical zero knowledge is non-trivial then so is non-interactive statistical zero knowledge, where by non-trivial we mean that the class includes problems which are not solvable in probabilistic polynommial-time. (The hypothesis holds under various assumptions, such as the intractability of the Discrete Logarithm Problem.) Furthermore, we show that if NISZK is closed under complement, then in fact SZK = NISZk, i.e. all statistical zero-knowledge proofs can be made non-interactive. The main tools in our analysis are two promise problems that are natural restrictions of promise problems known to be complete for SZK. We show that these restricted problems are in fact completer for NISZK and use this relationship to derive our results comparing the two classes. The two problems refer to the statistical difference, and difference in entropy, respectively, of a given distribution from the uniform one. We also consider a weak form of NISZK, in which only requires that for every inverse polynomial 1/p(n), there exists a simulator which achieves simulator deviation 1/p(n), and show that this weak form of NISZK actually equals NISZK. |
| first_indexed | 2024-09-23T13:27:20Z |
| id | mit-1721.1/149287 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T13:27:20Z |
| publishDate | 2023 |
| record_format | dspace |
| spelling | mit-1721.1/1492872023-03-30T03:38:05Z Can Statistical Zero Knowledge be made Non-interactive? or On the Relationship of SZK and NISZK Goldreich, Oded Sahai, Amit Vadhan, Salil We extend the study of non-interactive statistical zero-knowledge proofs. Our main focus is to compare the class NISZK of problems possessing such non-interactive proofs to the class SZK of problems possessing interactive statistical zero-knowledge proofs. Along these lines, we first show that if statistical zero knowledge is non-trivial then so is non-interactive statistical zero knowledge, where by non-trivial we mean that the class includes problems which are not solvable in probabilistic polynommial-time. (The hypothesis holds under various assumptions, such as the intractability of the Discrete Logarithm Problem.) Furthermore, we show that if NISZK is closed under complement, then in fact SZK = NISZk, i.e. all statistical zero-knowledge proofs can be made non-interactive. The main tools in our analysis are two promise problems that are natural restrictions of promise problems known to be complete for SZK. We show that these restricted problems are in fact completer for NISZK and use this relationship to derive our results comparing the two classes. The two problems refer to the statistical difference, and difference in entropy, respectively, of a given distribution from the uniform one. We also consider a weak form of NISZK, in which only requires that for every inverse polynomial 1/p(n), there exists a simulator which achieves simulator deviation 1/p(n), and show that this weak form of NISZK actually equals NISZK. 2023-03-29T14:41:21Z 2023-03-29T14:41:21Z 1999-09 https://hdl.handle.net/1721.1/149287 MIT-LCS-TM-594 application/pdf |
| spellingShingle | Goldreich, Oded Sahai, Amit Vadhan, Salil Can Statistical Zero Knowledge be made Non-interactive? or On the Relationship of SZK and NISZK |
| title | Can Statistical Zero Knowledge be made Non-interactive? or On the Relationship of SZK and NISZK |
| title_full | Can Statistical Zero Knowledge be made Non-interactive? or On the Relationship of SZK and NISZK |
| title_fullStr | Can Statistical Zero Knowledge be made Non-interactive? or On the Relationship of SZK and NISZK |
| title_full_unstemmed | Can Statistical Zero Knowledge be made Non-interactive? or On the Relationship of SZK and NISZK |
| title_short | Can Statistical Zero Knowledge be made Non-interactive? or On the Relationship of SZK and NISZK |
| title_sort | can statistical zero knowledge be made non interactive or on the relationship of szk and niszk |
| url | https://hdl.handle.net/1721.1/149287 |
| work_keys_str_mv | AT goldreichoded canstatisticalzeroknowledgebemadenoninteractiveorontherelationshipofszkandniszk AT sahaiamit canstatisticalzeroknowledgebemadenoninteractiveorontherelationshipofszkandniszk AT vadhansalil canstatisticalzeroknowledgebemadenoninteractiveorontherelationshipofszkandniszk |