International Association
for Cryptologic Research

Non-malleable zero-knowledge (NMZK), originally introduced in the seminal work of Dolev, Dwork, and Naor (STOC 91), is a fundamental concept for modeling the security of proof systems against man-in-the-middle attacks. After 30 years of active research, Kim, Liang, and Pandey (CRYPTO 2022) presented the first efficient constant-round NMZK argument system based solely on symmetric-key cryptography. Their construction relies on a non-black-box use of the involved cryptographic primitives and on multiple executions of Ligero (CCS 2017) that affect both the round complexity and the computational efficiency of their protocol. Their work left open the natural important challenge of achieving NMZK using the underlying primitives only in a black-box fashion (regardless of the number of rounds and actual efficiency). In this paper, we solve the aforementioned open problem by presenting the first NMZK argument system based on the black-box use of cryptographic primitives. Our work is optimal in the use of primitives since we only need one-way functions, and asymptotically optimal in the number of rounds since we only require a constant number of rounds. Our argument system is non-malleable with respect to the strong ``simulation-extractability'' flavor of non-malleability. Furthermore, we also show that our construction can be efficiently instantiated in Minicrypt, significantly improving upon the work of Kim et al., both in terms of round complexity and computational efficiency.

Threshold ring signatures are digital signatures that allow $t$ parties to sign a message while hiding their identity in a larger set of $n$ users called ``ring''. Recently, Aranha et al. [PKC 2022] introduced the notion of \emph{extendable} threshold ring signatures ($\etrs$). $\etrs$ allow one to update, in a non-interactive manner, a threshold ring signature on a certain message so that the updated signature has a greater threshold, and/or an augmented set of potential signers. An application of this primitive is anonymous count me in. A first signer creates a ring signature with a sufficiently large ring announcing a proposition in the signed message. After such cause becomes \emph{public}, other parties can anonymously decide to support that proposal by producing an updated signature. Crucially, such applications rely on partial signatures being posted on a \emph{publicly accessible} bulletin board since users may not know/trust each other. In this paper, we first point out that even if anonymous count me in was suggested as an application of $\etrs$, the anonymity notion proposed in the previous work is insufficient in many application scenarios. Indeed, the existing notion guarantees anonymity only against adversaries who just see the last signature, and are not allowed to access the ``full evolution" of an $\etrs$. This is in stark contrast with applications where partial signatures are posted in a public bulletin board. We therefore propose stronger anonymity definitions and construct a new $\etrs$ that satisfies such definitions. Interestingly, while satisfying stronger anonymity properties, our $\etrs$ asymptotically improves on the two $\etrs$ presented in prior work [PKC 2022] in terms of both time complexity and signature size. Our $\etrs$ relies on extendable non-interactive witness-indistinguishable proof of knowledge ($\ps$ PoK), a novel technical tool that we formalize and construct, and that may be of independent interest. We build our constructions from pairing groups under the SXDH assumption.