We design and implement a simple zero-knowledge argument protocol for NP whose communication complexity is proportional to the square-root of the verification circuit size. The protocol can be based on any collision-resistant hash function. Alternatively, it can be made non-interactive in the random oracle model, yielding concretely efficient zk-SNARKs that do not require a trusted setup or public-key cryptography.
No takes yet. Share an insight, caveat, or question.
Ames et al. (2017) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: