International Association
for Cryptologic Research

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.