Paper 2026/144

Designated-Verifier Dynamic zk-SNARKs with Applications to Dynamic Proofs of Index

Charalampos Papamanthou, Yale University, Lagrange Labs

Shravan Srinivasan, Lagrange Labs

Dimitrios Papadopoulos, Hong Kong University of Science and Technology

Abstract

Recently, the notion of dynamic zk-SNARKs was introduced. A dynamic zk-SNARK augments a standard zk-SNARK with an efficient update algorithm. Given a valid source statement-witness pair $(x,w)$ together with a verifying proof $p$, and a valid target statement-witness pair $(x',w')$, the update algorithm outputs a verifying proof $p'$ for $(x',w')$. Crucially, $p'$ is not recomputed from scratch; instead, the update algorithm takes time roughly proportional to the Hamming distance between $(x,w)$ and $(x',w')$, analogous to how dynamic data structures update the result of a computation after a small change. In this paper, we initiate the study of designated-verifier dynamic zk-SNARKs: dynamic zk-SNARKs in which only a designated verifier, holding secret verification state, can be convinced by a proof. Following recent advances in designated-verifier zk-SNARKs---such as efficient post-quantum designated verifier SNARKs (CCS 2021) and designated verifier SNARKs with very small proofs (CRYPTO 2025)---we construct a designated-verifier dynamic zk-SNARK with $O(\log n)$ update time, constant proof size, and concrete efficiency. Our construction significantly outperforms Dynalog (both asymptotically and concretely), the only publicly verifiable dynamic zk-SNARK with polylogarithmic update time (Wang et al., 2024). The concrete efficiency of our construction enables, for the first time, an efficient implementation of a dynamic proof of index: Given a digest $d$ of an arbitrary set and a digest $d'$ of its sorted index (e.g., binary search tree), we produce a SNARK proof certifying the consistency of $d$ and $d'$. More importantly, this proof can be updated in sublinear time when the underlying set changes---for example, when an element is modified or inserted, potentially altering the sorted order. We demonstrate applications of designated-verifier dynamic proofs of index to verifiable dynamic database outsourcing, where a client outsources a database and later maintains verifiable indices for efficient query answering, even under arbitrary database updates.

@misc{cryptoeprint:2026/144,
      author = {Weijie Wang and Charalampos Papamanthou and Shravan Srinivasan and Dimitrios Papadopoulos},
      title = {Designated-Verifier Dynamic zk-{SNARKs} with Applications to Dynamic Proofs of Index},
      howpublished = {Cryptology {ePrint} Archive, Paper 2026/144},
      year = {2026},
      url = {https://eprint.iacr.org/2026/144}
}