Paper 2025/722

One-Step Schnorr Threshold Identification

Abstract

Threshold zero-knowledge protocols have not been widely adopted, presumably due to the relevant network overhead, complicated certification processes and thus limited interoperability chances. In this work, we propose $\mathsf{OSST}$, a Schnorr-based threshold identification scheme that is both non-interactive and non-reliant on the public shares. Given a $(n, t)$-shared secret $x$, the proposed protocol allows any $t^* \ge t$ (but no less) shareholders to collectively prove that their secret keys combine to $x$ in the sense of interpolation without revealing any information beyond that. On the one side, the provers do not need to engage in multi-party computations, sending their packets to the verifier asynchronously. On the other side, the verification operation involves the combined public key $y \equiv g ^ x$ alone, meaning that the verifier does not need to have validated and registered the individual member identities. The protocol can be cheaply adopted in permissionless and dynamic environments, where no certification processes or infrastructure support are available, and be easily integrated with existing verifiers by means of pure software extension. No publicly trusted setup is required beyond the assumption that $x$ has been distributed by means of Shamir's secret sharing (or equivalent distribution scheme) and that the public counterpart has been advertised correctly; in particular, the protocol is intended to be secure against impersonation attacks in the plain public-key model. We provide evidence that this has good chances to hold true by giving a formal security proof in the random oracle model under the one-more discrete-logarithm hardness ($\mathsf{OMDL}$) assumption.