Paper 2025/2146

Zero-Knowledge Protocols with PVC Security: Striking the Balance between Security and Efficiency

Abstract

Zero-knowledge protocols allow a prover to prove possession of a witness for an NP-statement without revealing any information about the witness itself. This kind of protocol has found extensive applications in various fields, including secure computation and blockchain. However, in certain scenarios (e.g. when the statements are complicated), existing zero-knowledge protocols may not be well-suited due to their limited applicability or high computational overhead. We address these limitations by incorporating the notion of publicly verifiable covert (PVC) security into zero-knowledge protocols. PVC security, recently emerging from secure computation, effectively balances security and efficiency in practical scenarios. With PVC security, while a malicious party may attempt to cheat, such cheating will be detected and become publicly verifiable with a significant probability (called deterrence factor, e.g. ${>}90\%$). This notion is well-suited for practical scenarios involving reputation-conscious parties (e.g. companies) and offers substantial efficiency improvements. In this paper, we present the first definition of zero-knowledge protocols with PVC security. We then propose a generic transformation to convert Sigma protocols with $1$-bit challenge, a kind of protocol widely used for zero-knowledge, into efficient zero-knowledge protocols with PVC security. By applying our transformation, we can substantially improve the efficiency of existing protocols for reputation-sensitive parties. For instance, applying the transformation to achieve a deterrence factor of $93.75\%$ incurs a cost of only around $20\%$ compared to the original protocol. Therefore, our results contribute to significant advancements in practical zero-knowledge protocols.