International Association
for Cryptologic Research

Resettable statistical zero-knowledge [Garg--Ostrovsky--Visconti--Wadia, TCC 2012] is a strong privacy notion that guarantees statistical zero-knowledge even when the prover uses the same randomness in multiple proofs. In this paper, we show an equivalence of resettable statistical zero-knowledge arguments for NP and witness encryption schemes for NP. - Positive result: For any NP language L, a resettable statistical zero-knowledge argument for L can be constructed from a witness encryption scheme for L under the assumption of the existence of one-way functions. - Negative result: The existence of even resettable statistical witness-indistinguishable arguments for NP imply the existence of witness encryption schemes for NP under the assumption of the existence of one-way functions. The positive result is obtained by naturally extending existing techniques (and is likely to be already well-known among experts). The negative result is our main technical contribution. To explore workarounds for the negative result, we also consider resettable security in a model where the honest party's randomness is only reused with fixed inputs. We show that resettable statistically hiding commitment schemes are impossible even in this model.

In this paper, we give a no-signaling linear probabilistically checkable proof (PCP) system for polynomial-time deterministic computation, i.e., a PCP system for $$\mathcal {P}$$ P such that (1) the honest PCP oracle is a linear function and (2) the soundness holds against any (computational) no-signaling cheating prover, who is allowed to answer each query according to a distribution that depends on the entire query set in a certain way. To the best of our knowledge, our construction is the first PCP system that satisfies these two properties simultaneously. As an application of our PCP system, we obtain a 2-message delegating computation scheme by using a known transformation. Compared with the existing 2-message delegating computation schemes that are based on standard cryptographic assumptions, our scheme requires preprocessing but has a simpler structure and makes use of different (possibly cheaper) standard cryptographic primitives, namely additive/multiplicative homomorphic encryption schemes.

A succinct non-interactive argument (SNARG) is called \emph{holographic} if the verifier runs in time sub-linear in the input length when given oracle access to an encoding of the input. We present holographic SNARGs for P and Batch-NP under the learning with errors (LWE) assumption. Our holographic SNARG for P has a verifier that runs in time $\mathsf{poly}(\lambda, \log T, \log n)$ for $T$-time computations and $n$-bit inputs ($\lambda$ is the security parameter), while our holographic SNARG for Batch-NP has a verifier that runs in time $\mathsf{poly}(\lambda, T, \log k)$ for $k$ instances of $T$-time computations. Before this work, constructions with the same asymptotic efficiency were known in the designated-verifier setting or under the sub-exponential hardness of the LWE assumption. We obtain our holographic SNARGs (in the public-verification setting under the polynomial hardness of the LWE assumption) by constructing holographic SNARGs for certain hash computations and then applying known/trivial transformations. As an application, we use our holographic SNARGs to weaken the assumption needed for a recent public-coin 3-round zero-knowledge (ZK) argument [Kiyoshima, CRYPTO 2022]. Specifically, we use our holographic SNARGs to show that a public-coin 3-round ZK argument exists under the same assumptions as the state-of-the-art private-coin 3-round ZK argument [Bitansky et al., STOC 2018].

We construct a public-coin 3-round zero-knowledge argument for NP assuming (i) the sub-exponential hardness of the learning with errors (LWE) problem and (ii) the existence of keyless multi-collision-resistant hash functions against slightly super-polynomial-time adversaries. These assumptions are almost identical to those that were used recently to obtain a private-coin 3-round zero-knowledge argument [Bitansky et al., STOC 2018]. (The difference is that we assume sub-exponential hardness instead of quasi-polynomial hardness for the LWE problem.)

In this paper, we present a constant-round leakage-resilient zero-knowledge argument system for $$\mathcal {NP}$$ NP under the assumption of the existence of collision-resistant hash function families. That is, using a collision-resistant hash function, we construct a constant-round zero-knowledge argument system that has the following zero-knowledge property: even against any cheating verifier that obtains an arbitrary amount of leakage on the prover’s internal secret state, a simulator can simulate the verifier’s view by obtaining the same amount of leakage on the witness. Previously, leakage-resilient zero-knowledge proofs/arguments for $$\mathcal {NP}$$ NP were constructed only under a relaxed security definition (Garg et al., in: CRYPTO’11, pp 297–315, 2011) or under the DDH assumption (Pandey, in: TCC’14, pp 146–166, 2014). Our leakage-resilient zero-knowledge argument system satisfies an additional property that it is simultaneously leakage-resilient zero-knowledge, meaning that both zero-knowledge and soundness hold in the presence of leakage.

We study the problem of obtaining 2-round interactive arguments for NP with weak zero-knowledge (weak ZK) [Dwork et al., 2003] or with strong witness indistinguishability (strong WI) [Goldreich, 2001] under polynomially hard falsifiable assumptions. We consider both the delayed-input setting [Jain et al., 2017] and the standard non-delayed-input setting, where in the delayed-input setting, (i) prover privacy is only required to hold against delayed-input verifiers (which learn statements in the last round of the protocol) and (ii) soundness is required to hold even against adaptive provers (which choose statements in the last round of the protocol). Concretely, we show the following black-box (BB) impossibility results by relying on standard cryptographic primitives. 1. It is impossible to obtain 2-round delayed-input weak ZK arguments under polynomially hard falsifiable assumptions if BB reductions are used to prove soundness. This result holds even when non-black-box techniques are used to prove weak ZK. 2. It is impossible to obtain 2-round non-delayed-input strong WI arguments and 2-round publicly verifiable delayed-input strong WI arguments under polynomially hard falsifiable assumptions if a natural type of BB reductions, called "oblivious" BB reductions, are used to prove strong WI. 3. It is impossible to obtain 2-round delayed-input strong WI arguments under polynomially hard falsifiable assumptions if BB reductions are used to prove both soundness and strong WI (the BB reductions for strong WI are required to be oblivious as above). Compared with the above result, this result no longer requires public verifiability in the delayed-input setting.

We give a four-round black-box construction of a commit-and-prove protocol with succinct communication. Our construction is WI and has constant soundness error, and it can be upgraded into a one that is ZK and has negligible soundness error by relying on a round-preserving transformation of Khurana et al. (TCC 2018). Our construction is obtained by combining the MPC-in-the-head technique of Ishai et al. (SICOMP 2009) with the two-round succinct argument of Kalai et al. (STOC 2014), and the main technical novelty lies in the analysis of the soundness---we show that, although the succinct argument of Kalai et al. does not necessarily provide soundness for NP statements, it can be used in the MPC-in-the-head technique for proving the consistency of committed MPC views. Our construction is based on sub-exponentially hard collision-resistant hash functions, two-round PIRs, and two-round OTs.

Concurrent non-malleable zero-knowledge ( $$\mathrm {CNMZK}$$ CNMZK ) protocols are zero-knowledge protocols that provides security even when adversaries interact with multiple provers and verifiers simultaneously. It is known that $$\mathrm {CNMZK}$$ CNMZK arguments for $$\mathcal {NP}$$ NP can be constructed in the plain model. Furthermore, it was recently shown that statistical $$\mathrm {CNMZK}$$ CNMZK arguments for $$\mathcal {NP}$$ NP can also be constructed in the plain model. However, although the former requires only the existence of one-way functions, the latter requires the DDH assumption. In this paper, we construct a statistical $$\mathrm {CNMZK}$$ CNMZK argument for $$\mathcal {NP}$$ NP assuming only the existence of one-way functions. The security is proven via black-box simulation, and the round complexity is $$\mathsf {poly}(n)$$ poly ( n ) . Under the existence of collision-resistant hash functions, the round complexity is reduced to $$\omega (\log n)$$ ω ( log n ) , which is essentially optimal for black-box concurrent zero-knowledge protocols.

We give a new proof of the existence of $$O(n^{\epsilon })$$ O ( n ϵ ) -round public-coin concurrent zero-knowledge arguments for $$\mathcal {NP}$$ NP , where $$\epsilon >0$$ ϵ > 0 is an arbitrary constant. The security is proven in the plain model under the assumption that collision-resistant hash functions exist. The existence of such concurrent zero-knowledge arguments was previously proven by Goyal (STOC’13) in the plain model under the same assumption. In the proof, we use a new variant of the non-black-box simulation technique of Barak (FOCS’01). An important property of our simulation technique is that the simulator runs in a “straight-line” manner in the fully concurrent setting. Compared with the simulation technique of Goyal, which also has such a property, the analysis of our simulation technique is (arguably) simpler.

We present a round-efficient black-box construction of a general multi-party computation (MPC) protocol that satisfies composability in the plain model. The security of our protocol is proven in the angel-based UC framework [Prabhakaran and Sahai, STOC’04] under the minimal assumption of the existence of semi-honest oblivious transfer protocols. The round complexity of our protocol is $$\max (\widetilde{O}(\log ^2n), O(R_{{{{\mathsf {O}}}{{\mathsf {T}}}}}))$$ max ( O ~ ( log 2 n ) , O ( R O T ) ) when the round complexity of the underlying oblivious transfer protocol is $$R_{{{{\mathsf {O}}}{{\mathsf {T}}}}}$$ R O T . Since constant-round semi-honest oblivious transfer protocols can be constructed under standard assumptions (such as the existence of enhanced trapdoor permutations), our result gives a $$\widetilde{O}(\log ^2n)$$ O ~ ( log 2 n ) -round protocol under these assumptions. Previously, only an $$O(\max (n^{\epsilon }, R_{{{{\mathsf {O}}}{{\mathsf {T}}}}}))$$ O ( max ( n ϵ , R O T ) ) -round protocol was shown, where $$\epsilon >0$$ ϵ > 0 is an arbitrary constant. We obtain our MPC protocol by constructing a $$\widetilde{O}(\log ^2n)$$ O ~ ( log 2 n ) -round CCA-secure commitment scheme in a black-box way under the assumption of the existence of one-way functions.

In this paper, we give a no-signaling linear probabilistically checkable proof (PCP) system for polynomial-time deterministic computation, i.e., a PCP system for $${\mathcal {P}}$$P such that (1) the PCP oracle is a linear function and (2) the soundness holds against any (computational) no-signaling cheating prover, who is allowed to answer each query according to a distribution that depends on the entire query set in a certain way. To the best of our knowledge, our construction is the first PCP system that satisfies these two properties simultaneously.As an application of our PCP system, we obtain a 2-message scheme for delegating computation by using a known transformation. Compared with existing 2-message delegation schemes based on standard cryptographic assumptions, our scheme requires preprocessing but has a simpler structure and makes use of different (possibly cheaper) standard cryptographic primitives, namely additive/multiplicative homomorphic encryption schemes.