Designated-Verifier SNARGs with One Group Element
摘要
We revisit the question of minimizing the proof length of designated-verifier succinct non-interactive arguments (dv-SNARGs) in the generic group model. Barta et al. (Crypto 2020) constructed such dv-SNARGs with inverse-polynomial soundness in which the proof consists of only two group elements. For negligible soundness, all previous constructions required a super-constant number of group elements. We show that one group element suffices for negligible soundness. Concretely, we obtain dv-SNARGs (in fact, dv-SNARKs) with \(2^{-\tau }\) soundness where proofs consist of one element of a generic group \(\mathbb G\) and \(O(\tau )\) additional bits. In particular, the proof length in group elements is constant even with \(1/|\mathbb G|\) soundness error. In more concrete terms, compared to the best known SNARGs using bilinear groups, we get dv-SNARGs with roughly 2x shorter proofs (with \(2^{-80}\) soundness at a 128-bit security level). We are not aware of any practically feasible proof systems that achieve similar succinctness, even fully interactive or heuristic ones. Our technical approach is based on a novel combination of techniques for trapdoor hash functions and group-based homomorphic secret sharing with linear multi-prover interactive proofs.