Paper 2024/1549

Universally Composable SNARKs with Transparent Setup without Programmable Random Oracle

Abstract

Non-interactive zero-knowledge (NIZK) proofs allow a prover to convince a verifier about the validity of an NP-statement by sending a single message and without disclosing any additional information (besides the validity of the statement). Single-message cryptographic proofs are very versatile, which has made them widely used both in theory and in practice. This is particularly true for succinct proofs, where the length of the message is sublinear in the size of the NP relation. This versatility, unfortunately, comes at a price, since any NIZK proof system requires some form of setup, like a common reference string. One way to circumvent the need for a setup is by relying on a Random Oracle. Unfortunately, if the Random Oracle is modeled as a Global resource that the simulator is not allowed to program, then it is impossible to obtain a secure NIZK. This impossibility has been circumvented by allowing the simulator (and the real-world adversary) to program the RO, and allowing the honest parties to check, via a special interface, if the RO outputs have been programmed. In this work, we show that this impossibility can be circumvented by meaningfully weakening the Universal Composability framework following the model proposed by Broadnax et al. (Eurocrypt 2017). In this model, the ideal world functionalities are allowed to interact with oracles that have quasi-polynomial time capabilities. As our main result, we propose the first composable NIZK proof system that relies on a global (non-programmable) random oracle as its only form of setup. The NIZK scheme we propose is witness-succinct (with proofs logarithmic in the size of the witness). Our results break both the barrier of programmability of the random oracle and of polylogarithmic proof size for UC-secure NIZKs with transparent setups. We are able to construct our NIZK using the framework proposed by Ganesh et al. (Eurocrypt 2023), which requires—among other building blocks—a polynomial commitment scheme with special features and a polynomial encoding scheme (a primitive that appropriately masks a witness as a polynomial). As a core technical contribution, we show a polynomial commitment of this type using a basic component of Bulletproofs as a building block, as well as a polynomial encoding based on techniques completely different from the ones from Ganesh et al..