International Association
for Cryptologic Research

Polynomial commitment schemes allow a prover to commit to a polynomial and later reveal the evaluation of the polynomial on an arbitrary point along with proof of validity. This object is central in the design of many cryptographic schemes such as zero-knowledge proofs and verifiable secret sharing. In the standard definition, the polynomial is known to the prover whereas the evaluation points are not private. In this paper, we put forward the notion of \emph{private polynomial commitments} that capture additional privacy guarantees, where the evaluation points are hidden from the verifier while the polynomial is hidden from both. We provide concretely efficient constructions that allow simultaneously batch the verification of many evaluations with a small additive overhead. As an application, we design a new concretely efficient multi-party private set-intersection with malicious security and improved asymptotic communication and space complexities. We demonstrate the concrete efficiency of our construction via an implementation. Our scheme can prove $2^{10}$ evaluations of a private polynomial of degree $2^{10}$ in 157s. The proof size is only 169KB and the verification time is 11.8s. Moreover, we also implemented the multi-party private set intersection protocol and scale it to 1000 parties (which has not been shown before). The total running time for $2^{14}$ elements per party is 2,410 seconds. While existing protocols offer better computational complexity, our scheme offers significantly smaller communication and better scalability (in the number of parties) owing to better memory usage.

We obtain the first two-round two-party computation protocol, in the plain model, that is secure against passive adversaries who can adaptively corrupt all parties where the communication complexity is proportional to the square of the RAM complexity of the function up to polylogarithmic factors assuming the existence of non-committing encryption.

The question of minimizing the {\em computational overhead} of cryptography was put forward by the work of Ishai, Kushilevitz, Ostrovsky and Sahai (STOC 2008). The main conclusion was that, under plausible assumptions, most cryptographic primitives can be realized with {\em constant} computational overhead. However, this ignores an additive term that may depend polynomially on the (concrete) computational security parameter $\lambda$. In this work, we study the question of obtaining optimal efficiency, up to polylogarithmic factors, for {\em all} choices of $n$ and $\lambda$, where $n$ is the size of the given task. In particular, when $n=\lambda$, we would like the computational cost to be only $\tilde O(\lambda)$. We refer to this goal as {\em asymptotically quasi-optimal} (AQO) cryptography. We start by realizing the first AQO semi-honest batch oblivious linear evaluation (BOLE) protocol. Our protocol applies to OLE over small fields and relies on the near-exponential security of the ring learning with errors (RLWE) assumption. Building on the above and on known constructions of AQO PCPs, we design the first AQO zero-knowledge (ZK) argument system for Boolean circuit satisfiability. Our construction combines a new AQO ZK-PCP construction that respects the AQO property of the underlying PCP along with a technique for converting statistical secrecy into soundness via OLE reversal. Finally, combining the above results, we get AQO secure computation protocols for Boolean circuits with security against malicious parties under RLWE.

Zero-knowledge proofs allow a prover to convince a verifier of a statement without revealing anything besides its validity. A major bottleneck in scaling sub-linear zero-knowledge proofs is the high space requirement of the prover, even for NP relations that can be verified in a small space. In this work, we ask whether there exist complexity-preserving (i.e. overhead w.r.t time and space are minimal) succinct zero-knowledge arguments of knowledge with minimal assumptions while making only black-box access to the underlying primitives. We essentially resolve this question up to polylogarithmic factors. Namely, for every NP relation that can be verified in time T and space S, we construct a public-coin zero-knowledge argument system that is black-box based on collision-resistant hash-functions (CRH) where the prover runs in time $\O(T)$ and space $\O(S)$, the verifier runs in time $\O(T/S+S)$ and space $\O(\kappa)$ and the communication is $\O(T/S)$, where $\kappa$ is the statistical security parameter. Using the Fiat-Shamir heuristic, our construction yields the first complexity-preserving ZK-SNARK based on CRH (via a black-box construction). Furthermore, we give evidence that reducing the proof length below $\O(T/S)$ will be hard using existing techniques by arguing the space-complexity of constant-distance error correcting codes.

Zero-Knowledge PCPs (ZK-PCPs; Kilian, Petrank, and Tardos, STOC ‘97) are PCPs with the additional zero-knowledge guarantee that the view of any (possibly malicious) verifier making a bounded number of queries to the proof can be efficiently simulated up to a small statistical distance. Similarly, ZK-PCPs of Proximity (ZK-PCPPs; Ishai and Weiss, TCC ‘14) are PCPPs in which the view of an adversarial verifier can be efficiently simulated with few queries to the input. Previous ZK-PCP constructions obtained an exponential gap between the query complexity q of the honest verifier, and the bound $$q^*$$ q ∗ on the queries of a malicious verifier (i.e., $$q={\mathsf {poly}}\log \left( q^*\right) $$ q = poly log q ∗ ), but required either exponential-time simulation, or adaptive honest verification. This should be contrasted with standard PCPs, that can be verified non-adaptively (i.e., with a single round of queries to the proof). The problem of constructing such ZK-PCPs, even when $$q^*=q$$ q ∗ = q , has remained open since they were first introduced more than 2 decades ago. This question is also open for ZK-PCPPs, for which no construction with non-adaptive honest verification is known (not even with exponential-time simulation). We resolve this question by constructing the first ZK-PCPs and ZK-PCPPs which simultaneously achieve efficient zero-knowledge simulation and non-adaptive honest verification. Our schemes have a square-root query gap, namely $$q^*/q=O\left( \sqrt{n}\right) $$ q ∗ / q = O n , where n is the input length. Our constructions combine the “MPC-in-the-head” technique (Ishai et al., STOC ‘07) with leakage-resilient secret sharing. Specifically, we use the MPC-in-the-head technique to construct a ZK-PCP variant over a large alphabet, then employ leakage-resilient secret sharing to design a new alphabet reduction for ZK-PCPs which preserves zero-knowledge.

Secure multi-party computation (MPC) is a central cryptographic task that allows a set of mutually distrustful parties to jointly compute some function of their private inputs where security should hold in the presence of an active (i.e. malicious) adversary that can corrupt any number of parties. Despite extensive research, the precise round complexity of this “standard-bearer” cryptographic primitive, under polynomial-time hardness assumptions, is unknown. Recently, Garg, Mukherjee, Pandey and Polychroniadou, in Eurocrypt 2016 demonstrated that the round complexity of any MPC protocol relying on black-box proofs of security in the plain model must be at least four. Following this work, independently Ananth, Choudhuri and Jain, CRYPTO 2017 and Brakerski, Halevi, and Polychroniadou, TCC 2017 made progress towards solving this question and constructed four-round protocols based on the DDH and LWE assumptions, respectively, albeit with super-polynomial hardness. More recently, Ciampi, Ostrovsky, Siniscalchi and Visconti in TCC 2017 closed the gap for two-party protocols by constructing a four-round protocol from polynomial-time assumptions, concretely, trapdoor permutations. In another work, Ciampi, Ostrovsky, Siniscalchi and Visconti TCC 2017 showed how to design a four-round multi-party protocol for the specific case of multi-party coin-tossing based on one-way functions. In this work, we resolve this question by designing a four-round actively secure multi-party (two or more parties) protocol for general functionalities under standard polynomial-time hardness assumptions with a black-box proof of security, specifically, under the assumptions LWE, DDH, QR and DCR.

Ishai, Kushilevitz, Ostrovsky and Sahai (STOC 2007 ; SIAM J Comput 39(3):1121–1152, 2009 ) introduced the powerful “MPC-in-the-head” technique that provided a general transformation of information-theoretic MPC protocols secure against passive adversaries to a ZK proof in a “black-box” way. In this work, we extend this technique and provide a generic transformation of any semi-honest secure two-party computation (2PC) protocol (with mild adaptive security guarantees) in the so-called oblivious-transfer hybrid model to an adaptive ZK proof for any $$\textsf {NP}$$ NP language, in a “black-box” way assuming only one-way functions. Our basic construction based on Goldreich–Micali–Wigderson’s 2PC protocol yields an adaptive ZK proof with communication complexity proportional to quadratic in the size of the circuit implementing the $$\textsf {NP}$$ NP relation. Previously such proofs relied on an expensive Karp reduction of the $$\textsf {NP}$$ NP language to Graph Hamiltonicity [Lindell and Zarosim (TCC 2009 ; J Cryptol 24(4):761–799, 2011 )]. As an application of our techniques, we show how to obtain a ZK proof with an “input-delayed” property for any $$\textsf {NP}$$ NP language without relying on expensive Karp reductions that is black box in the underlying one-way function. Namely, the input-delayed property allows the honest prover’s algorithm to receive the actual statement to be proved only in the final round. We further generalize this to obtain a “commit-and-prove” protocol with the same property where the prover commits to a witness w in the second message and proves a statement x regarding the witness w in zero-knowledge where the statement is determined only in the last round. This improves a previous construction of Lapidot and Shamir (Crypto 1990 ) that was designed specifically for the Graph Hamiltonicity problem and relied on the underlying primitives in a non-black-box way. Additionally, we provide a general transformation to construct a randomized encoding of a function f from any 2PC protocol that securely computes a related functionality (in a black-box way) from one-way functions. We show that if the 2PC protocol has mild adaptive security guarantees (which are satisfied by both the Yao’s and GMW’s protocol), then the resulting randomized encoding can be decomposed to an offline/online encoding.

We prove that if a language $\cL$ has a 4-round fully black-box zero-knowledge argument with negligible soundness based on one-way functions, then $\overline{\cL} \in \MA$. Since $\coNP \subseteq \MA$ implies that the polynomial hierarchy collapses, our result implies that $\NP$-complete languages are unlikely to have 4-round fully black-box zero-knowledge arguments based on one-way functions. In TCC 2018, Hazay and Venkitasubramaniam, and Khurana, Ostrovsky, and Srinivasan demonstrated 4-round fully black-box zero-knowledge arguments for all languages in $\NP$ based on injective one-way functions. Their results also imply a 5-round protocol based on one-way functions. In essence, our result resolves the round complexity of fully black-box zero-knowledge arguments based on one-way functions.

We construct the first actively-secure Multi-Party Computation (MPC) protocols with an \emph{arbitrary} number of parties in the dishonest majority setting, for an \emph{arbitrary} field $\FF$ with \emph{constant communication overhead} over the ``passive-GMW'' protocol (Goldreich, Micali and Wigderson, STOC `87). Our protocols rely on passive implementations of Oblivious Transfer (OT) in the boolean setting and Oblivious Linear function Evaluation (OLE) in the arithmetic setting. Previously, such protocols were only known over sufficiently large fields (Genkin et al. STOC `14) or a constant number of parties (Ishai et al. CRYPTO `08). Conceptually, our protocols are obtained via a new compiler from a passively-secure protocol for a distributed multiplication functionality $\cF_\mult$, to an actively-secure protocol for general functionalities. Roughly, $\cF_\mult$ is parameterized by a linear-secret sharing scheme $\cS$, where it takes $\cS$-shares of two secrets and returns $\cS$-shares of their product. We show that our compilation is concretely efficient for sufficiently large fields, resulting in an overhead of 2 when securely computing natural circuits. Our compiler has two additional benefits: (1) it can rely on \emph{any} passive implementation of $\cF_\mult$, which, besides the standard implementation based on OT (for boolean) and OLE (for arithmetic) allows us to rely on implementations based on threshold cryptosystems (Cramer et al. Eurocrypt `01); and (2) it can rely on weaker-than-passive (i.e., imperfect/leaky) implementations, which in some parameter regimes yield actively-secure protocols with overhead less than 2. Instantiating this compiler with an ``honest-majority'' implementations of $\cF_\mult$, we obtain the first honest-majority protocol with optimal corruption threshold for boolean circuits with constant communication overhead over the best passive protocol (Damg{\aa}rd and Nielsen, CRYPTO `07).

The dual execution paradigm of Mohassel and Franklin (PKC’06) and Huang, Katz and Evans (IEEE ’12) shows how to achieve the notion of 1-bit leakage security at roughly twice the cost of semi-honest security for the special case of two-party secure computation . To date, there are no multi-party computation (MPC) protocols that offer such a strong trade-off between security and semi-honest performance. Our main result is to address this shortcoming by designing 1-bit leakage protocols for the multi-party setting, albeit for a special class of functions. We say that function f ( x ,  y ) is efficiently verifiable by g if the running time of g is always smaller than f and $$g(x,y,z)=1$$ if and only if $$f(x,y)=z$$ . In the two-party setting, we first improve dual execution by observing that the “second execution” can be an evaluation of g instead of f , and that by definition, the evaluation of g is asymptotically more efficient. Our main MPC result is to construct a 1-bit leakage protocol for such functions from any passive protocol for f that is secure up to additive errors and any active protocol for g . An important result by Genkin et al. (STOC ’14) shows how the classic protocols by Goldreich et al. (STOC ’87) and Ben-Or et al. (STOC ’88) naturally support this property, which allows to instantiate our compiler with two-party and multi-party protocols. A key technical result we prove is that the passive protocol for distributed garbling due to Beaver et al. (STOC ’90) is in fact secure up to additive errors against malicious adversaries, thereby, yielding another powerful instantiation of our paradigm in the constant-round multi-party setting. As another concrete example of instantiating our approach, we present a novel protocol for computing perfect matching that is secure in the 1-bit leakage model and whose communication complexity is less than the honest-but-curious implementations of textbook algorithms for perfect matching.

In this work, we study the intrinsic complexity of black-box Universally Composable (UC) secure computation based on general assumptions. We present a thorough study in various corruption modelings while focusing on achieving security in the common reference string (CRS) model. Our results involve the following:Static UC secure computation. Designing the first static UC oblivious transfer protocol based on public-key encryption and stand-alone semi-honest oblivious transfer. As a corollary, we obtain the first black-box constructions of UC secure computation assuming only two-round semi-honest oblivious transfer.One-sided UC secure computation. Designing adaptive UC two-party computation with single corruptions assuming public-key encryption with oblivious ciphertext generation.Adaptive UC secure computation. Designing adaptively secure UC commitment scheme assuming only public-key encryption with oblivious ciphertext generation. As a corollary, we obtain the first black-box constructions of adaptive UC secure computation assuming only (trapdoor) simulatable public-key encryption (as well as a variety of concrete assumptions).We remark that such a result was not known even under non-black-box constructions.

Katz and Ostrovsky (Crypto 2004) proved that five rounds are necessary for stand-alone general black-box constructions of secure two-party protocols and at least four rounds are necessary if only one party needs to receive the output. Recently, Ostrovsky, Richelson and Scafuro (Crypto 2015) proved optimality of this result by showing how to realize stand-alone, secure two-party computation under general assumptions (with black-box proof of security) in four rounds where only one party receives the output, and an extension to five rounds where both parties receive the output. In this paper, we study the question of what security is achievable for stand-alone two-party protocols within four rounds and show the following results: 1. A 4-round two-party protocol for coin-tossing that achieves 1 /  p - security (i.e., simulation fails with probability at most $$1/p+{\mathsf {negl}}$$ 1 / p + negl ), in the presence of malicious corruptions. 2. A 4-round two-party protocol for general functionalities where both parties receive the output, that achieves 1 /  p -security and privacy in the presence of malicious adversaries corrupting one of the parties, and full security in the presence of non-aborting malicious adversaries corrupting the other party. 3. A 3-round oblivious-transfer protocol that achieves 1 /  p -security against arbitrary malicious senders, while simultaneously guaranteeing a meaningful notion of privacy against malicious corruptions of either party. 4. Finally, we show that the simulation-based security guarantees for our 3-round protocols are optimal by proving that 1 /  p -simulation security is impossible to achieve against both parties in three rounds or less when requiring some minimal guarantees on the privacy of their inputs.

Secure multi-party computation (MPC) is a central cryptographic task that allows a set of mutually distrustful parties to jointly compute some function of their private inputs where security should hold in the presence of a malicious adversary that can corrupt any number of parties. Despite extensive research, the precise round complexity of this “standard-bearer” cryptographic primitive is unknown. Recently, Garg, Mukherjee, Pandey and Polychroniadou, in EUROCRYPT 2016 demonstrated that the round complexity of any MPC protocol relying on black-box proofs of security in the plain model must be at least four. Following this work, independently Ananth, Choudhuri and Jain, CRYPTO 2017 and Brakerski, Halevi, and Polychroniadou, TCC 2017 made progress towards solving this question and constructed four-round protocols based on non-polynomial time assumptions. More recently, Ciampi, Ostrovsky, Siniscalchi and Visconti in TCC 2017 closed the gap for two-party protocols by constructing a four-round protocol from polynomial-time assumptions. In another work, Ciampi, Ostrovsky, Siniscalchi and Visconti TCC 2017 showed how to design a four-round multi-party protocol for the specific case of multi-party coin-tossing.In this work, we resolve this question by designing a four-round actively secure multi-party (two or more parties) protocol for general functionalities under standard polynomial-time hardness assumptions with a black-box proof of security.

In this paper, we revisit the round complexity of designing zero-knowledge (ZK) arguments via a black-box construction from minimal assumptions. Our main result implements a 4-round ZK argument for any language in $$\textsf {NP}$$ NP, based on injective one-way functions, that makes black-box use of the underlying function. As a corollary, we also obtain the first 4-round perfect zero-knowledge argument for $$\textsf {NP}$$ NP based on claw-free permutations via a black-box construction and 4-round input-delayed commit-and-prove zero-knowledge argument based on injective one-way functions.

We present the first two-round multiparty computation (MPC) protocols secure against malicious adaptive corruption in the common reference string (CRS) model, based on DDH, LWE, or QR. Prior two-round adaptively secure protocols were known only in the two-party setting against semi-honest adversaries, or in the general multiparty setting assuming the existence of indistinguishability obfuscation (iO).Our protocols are constructed in two steps. First, we construct two-round oblivious transfer (OT) protocols secure against malicious adaptive corruption in the CRS model based on DDH, LWE, or QR. We achieve this by generically transforming any two-round OT that is only secure against static corruption but has certain oblivious sampleability properties, into a two-round adaptively secure OT. Prior constructions were only secure against semi-honest adversaries or based on iO.Second, building upon recent constructions of two-round MPC from two-round OT in the weaker static corruption setting [Garg and Srinivasan, Benhamouda and Lin, Eurocrypt’18] and using equivocal garbled circuits from [Canetti, Poburinnaya and Venkitasubramaniam, STOC’17], we show how to construct two-round adaptively secure MPC from two-round adaptively secure OT and constant-round adaptively secure MPC, with respect to both malicious and semi-honest adversaries. As a corollary, we also obtain the first 2-round MPC secure against semi-honest adaptive corruption in the plain model based on augmented non-committing encryption (NCE), which can be based on a variety of assumptions, CDH, RSA, DDH, LWE, or factoring Blum integers. Finally, we mention that our OT and MPC protocols in the CRS model are, in fact, adaptively secure in the Universal Composability framework.