An Efficiency-Preserving Transformation from Honest-Verifier Statistical Zero-Knowledge to Statistical Zero-Knowledge

by Pavel Hubacek and Alon Rosen and Margarita Vald

Oded's comments

I was quite surprised that one can get an efficiently-preserving transformation of the type this paper provides. The key observation seems to be that weaker form of zero-knowledge (i.e., HVSZK) implies the existence of instance-based commitment schemes in which the strategies of the parties depend only on the strategy of the original verifier (in the HVSZK for SD). These instance-based commitment schemes are then used to construct instance-based zero-knowledge proofs, which is indeed an appealing notion of independent interest, which are then used to prove that the verifier behaves properly (and so the ZK feature of proper behavior is preserved in the general case). This may explain how once can possibly preserve the complexity of the prover while perfoming such transformations.

The original abstract

We present an unconditional transformation from any honest-verifier statistical zero-knowledge (HVSZK) protocol to standard SZK that preserves round complexity and efficiency of both the verifier and the prover. This improves over currently known transformations, which either rely on some computational assumptions or introduce significant computational overhead. Our main conceptual contribution is the introduction of instance-dependent SZK proofs for NP, which serve as a building block in our transformation. Instance-dependent SZK for NP can be constructed unconditionally based on instance-dependent commitment schemes of Ong and Vadhan (TCC'08).

As an additional contribution, we give a simple constant-round SZK protocol for Statistical-Difference resembling the textbook HVSZK proof of Sahai and Vadhan (J.ACM'03). This yields a conceptually simple constant-round protocol for all of SZK.

See Crypto ePrint TR18-164.


Back to list of Oded's choices.