A proof complexity perspective on effectively zero-knowledge proofs
arXiv:2607.13540
The paper reformulates effectively zero-knowledge proofs in logical terms, provides simple proofs of their existence and indistinguishability, and shows how proof‑complexity generators can convert them into genuine zero‑knowledge proofs under a hardness conjecture.
Abstract
Ilango (FOCS 2025) invented effectively zero-knowledge proofs, a new variant of zero-knowledge. We reformulate it in the language of logic and give simple proofs (under the same assumptions as Ilango (FOCS 2025)) of its existence and of the key property defined in Ilango (FOCS 2025) that it is "indistinguishable from true" (that property is in Ilango (FOCS 2025) a part of the definition of the prover, not its consequence). Using the theory of proof complexity generators we show that the concept can be turned it into a genuinely zero-knowledge proofs, assuming a conjecture from the theory about the existence of a hard generator and allowing the parties to share a common random string.
preliminary version