International Association
for Cryptologic Research

We consider the problem of verifying the computations of a RAM program on a committed database $x\in\{0,1\}^n$. A recent work by Ishai, Ostrovsky, and Shah (Crypto 2023) obtained a {\em doubly efficient} solution, in which the communication and verifier’s work are polylogarithmic in $n$ and the prover’s work is comparable to the (possibly sublinear) running time of the RAM program. This only makes a {\em black-box} use of a collision-resistant hash function, or alternatively can be implemented unconditionally and non-interactively in the random oracle model. In the current work, we extend this prior work by providing an additional {\em zero-knowledge} guarantee and by supporting {\em database updates}. This gives the first doubly efficient zero-knowledge implementation of RAM programs that makes a black-box use of symmetric cryptography. While the extra zero knowledge and updatable database features of our solution are orthogonal in scope, our means for achieving them are technically related: to verify with zero knowledge many computations on the same database, we rely on a database refreshing procedure that we also use to accommodate updates.

The most fundamental performance metrics of secure multi-party computation (MPC) protocols are related to the number of messages the parties exchange (i.e., round complexity), the size of these messages (i.e., communication complexity), and the overall computational resources required to execute the protocol (i.e., computational complexity). Another quality metric of MPC protocols is related to the black-box or non-black-box use of the underlying cryptographic primitives. Indeed, the design of black-box MPC protocols, other than being of theoretical interest, usually can lead to protocols that have better computational complexity. In this work, we aim to optimize the round and communication complexity of black-box secure multi-party computation in the plain model, by designing a constant-round two-party computation protocol in the malicious setting, whose communication complexity is only polylogarithmic in the size of the function being evaluated. We successfully design such a protocol, having only black-box access to fully homomorphic encryption, trapdoor permutations, and hash functions. To the best of our knowledge, our protocol is the first to make black-box use of standard cryptographic primitives while achieving almost asymptotically optimal communication and round complexity.

Probabilistic proof systems such as PCPs and their zero-knowledge variants (ZK-PCPs) are central building blocks in cryptographic applications. In this work, we study {\em query-reusable} proof systems where the verifier can sample its queries once and use them to verify any polynomial number of proofs. In this reusable setting, soundness should still hold even if the prover can learn the verifier's decision (accept or reject) on many badly formed proofs. Our study is motivated by attractive features of designated-verifier NIZK systems that combine a query-reusable (honest-verifier) ZK-PCP with symmetric encryption. The reusability of ZK-PCP was studied by Chase et al. (Crypto 2019), who obtained a limited negative result for ZK-PCP with a special simulator. This left the question open for unrestricted ZK-PCP. We essentially settle this question by showing a negative result for statistical ZK-PCP (alternatively, PCP with sublinear query complexity) under standard complexity theoretic assumptions. We complement this with a positive result, showing that if {\em either} soundness or ZK are computational, query-reusable ZK-PCPs that {\em do not} meet the special simulation requirement of Chase et al. follow from standard cryptographic assumptions. Finally, we study the relaxed notion of {\em bounded} query reusability, where the prover is allowed to interact with the verifier over a bounded number of epochs by issuing a batch of polynomially many proofs in each epoch and learning the verifier's decisions. We obtain a nearly tight characterization of the number of queries required for r-epoch reusability.

State-of-the-art protocols that achieve constant-round secure multiparty computation currently present a trade-off: either consume an amount of communication that scales quadratically in the number of parties, or achieve better asymptotics at the cost of high constant factors (e.g. schemes based on LPN or DDH). We construct a constant-round MPC protocol where communication scales *linearly* in the number of parties `n'. Our construction relies only on OT and RO, and it leverages packed secret sharing. Due to building on simple primitives, our protocol offers concrete improvement over asymptotically-efficient LPN-based schemes. We consider security in the presence of a dishonest majority where the malicious (with abort) adversary corrupts an arbitrary constant fraction of parties. Our scheme is proved secure in the OT hybrid/random oracle model. By leveraging *tri-state circuits* (Heath et al. Crypto 2023), we extend our protocol to the RAM model of computation. For a RAM program that halts within T steps, our maliciously-secure protocol communicates O(n . T . log^3 T . log log T . \kappa) total bits, where \kappa is a security parameter.

Motivated by the goal of proving statements that involve small subsets of a big database, we introduce and study the notion of projection codes. A standard error-correcting code allows one to encode a message x into a codeword X, such that even if a constant fraction of X is corrupted, the message x can still be recovered. A projection code extends this guarantee to any subset of the bits of x. Concretely, for every projection of x to a subset s of its coordinates, there is a subset S of comparable size such that the projected encoding X|_S forms a robust encoding of the projected message x|_s. Our first main result is a construction of projection codes with a near-optimal increase in the length of x and size of s. We then apply this to obtain our second main result: succinct arguments for the computation of a RAM program on a (big) committed database, where the communication and the run-time of both the prover and the verifier are close to optimal even when the RAM program run-time is much smaller than the database size. Our solution makes only a black-box use of a collision-resistant hash function, providing the first black-box alternative to previous non-black-box constructions with similar asymptotic efficiency.