2026-07-23T21:29:21Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17506 2024-03-06T10:59:46Z ddc:004 open_access

Kolmogorov Complexity Characterizes Statistical Zero Knowledge Allender, Eric Hirahara, Shuichi Tirumala, Harsha Kolmogorov Complexity Interactive Proofs We show that a decidable promise problem has a non-interactive statistical zero-knowledge proof system if and only if it is randomly reducible via an honest polynomial-time reduction to a promise problem for Kolmogorov-random strings, with a superlogarithmic additive approximation term. This extends recent work by Saks and Santhanam (CCC 2022). We build on this to give new characterizations of Statistical Zero Knowledge SZK, as well as the related classes NISZK_L and SZK_L. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Eric Allender and Shuichi Hirahara and Harsha Tirumala 2023 Is Part Of LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2023.3 urn:nbn:de:0030-drops-175063 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.3 eng https://creativecommons.org/licenses/by/4.0/legalcode