What a lovely hat

Paper 2025/722

One-Step Schnorr Threshold Identification

Abstract

Threshold cryptographic primitives have not been widely adopted in real-world distributed systems (i.e., beyond the closed-committee model), presumably due to synchronization overhead and complex certification processes for the shareholders. These are both aspects of their extended reliance on infrastructure, an assumption that is usually glossed over in their design.In this work, we propose $\textsf{OSST}$, a Schnorr-based real-time threshold identification protocol that is non-interactive and does not rely on public shares. Given a Shamir $(n, t)$-shared secret $x$, the proposed protocol allows any $t^* \ge t$ (but no less) shareholders to dynamically prove over designated communication channels that their secret keys interpolate to $x$ without revealing any information beyond that. Provers do not engage in distributed computations, sending their packets to the verifier asynchronously; conversely, verifiers need only know the combined public key $y \equiv g ^ x$, without need to pre-validate and register the individual member identities. The protocol is intended for use in permissionless and unmanaged meshes that lack overlay networks and trust infrastructure, a use case space that has been tacitly neglected as "niche" by threshold cryptography. No auditable or certified multi-key setup is required beyond distributing $x$ according to Shamir's secret sharing (or equivalent distributed key generation scheme) and correctly advertising its public counterpart; in particular, the protocol is intended to be secure against impersonation attacks without relying on the consistency of any advertised shares. 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 ($\textsf{OMDL}$) hardness assumption.