Zero-Knowledge Proofs with Enhanced Deniability

Abstract

In cryptography, deniability is a crucial concept that allows a participant to plausibly deny taking part in executing a scheme or protocol. Non-interactive zero-knowledge (NIZK) proofs enable a party (the prover) to convince another party (the verifier) of the validity of a statement without revealing any information beyond the truth of the statement, and without requiring any interaction between the parties. Although there has been limited research on incorporating deniability into proof systems, a recent development known as short-lived proofs introduces deniability in these systems. Short-lived proofs (SLP) are non-interactive proofs of knowledge with the novel property that after a specified period of time, the proof loses its soundness thus rendering it invalid. SLPs yield short-lived signatures, and these primitives are useful in providing cryptographic deniability in applications like e-voting, deniable messaging and email.

A beacon stream outputs values which are uniformly distributed and unpredictable randomness as of time T_i. A SLP uses a beacon value b in the statement as an indicator to the amount of time that has passed in order to determine whether a proof has lost its soundness. The central idea in constructing SLP is to allow forgery of the proof by any party performing a sequential computation. A useful property called 1-reusable forgeability that a short-lived proof(or signature) can have, captures the desired property that a single slow computation enables efficient proof forgery for any statement. An even stronger notion of deniability called k-reusable forgeability allows forging proofs for any statement using one of k beacon values after just one slow computation providing faster and more efficient forgeries. In this work, we study SLPs with k-reusable forgeability and make the following contributions.

(i) We contruct a SLP with k-reusable forgeability based on Sigma protocols and a zero-knowledge verifiable delay function (zkVDF) representing the first such construction in the literature. Towards our construction, we present a novel proof of knowledge of eth root of a discrete logarithm with a commit-and-prove flavor that could be of independent interest.

(ii) We construct a commit-and-prove Incrementally Verifiable Computation (IVC) scheme using the Nova proof system, that allows a prover to recursively prove correct execution of incremental computations of the form y=F^n(x) given commitments to x and y. Using this as a building block together with CP-SNARKs, we construct an SLP that offers k-reusable forgeability for relations proved using zkSNARKs.

Both of our protocols provide improved prover efficiency compared to previous constructions, with minimal additional cost in terms of verifier efficiency and proof size.