Paper 2026/1097

Schnorr-like Signatures in the Non-Observable Random Oracle Model

Abstract

Schnorr's signature scheme and many of its variants are among the most efficient group-based digital signature schemes. Schnorr's scheme has very compact signatures (consisting of only two exponents in its most compact form). However, its security reduction is notoriously non-tight and requires a strong (“programmable”) version of the random oracle model. Variants with a tight(er) security proof in a more realistic model exist, but are less compact and efficient. In this work, we investigate whether these disadvantages are inherent to Schnorr's signatures and its variants. In particular, we define a family of “Schnorr-like” signature schemes, which contains group-based signature schemes with verification similar to Schnorr's scheme. To explore the necessity of (heavy) random oracle abstractions for such schemes, we allow only for a very weak (“non-programmable, non-observable”) version of a random oracle in the security proof. Our main result is that there is no tight reduction of the security of any such “Schnorr-like” scheme to any group-based assumption that holds generically. We also show that this result itself is tight, in the sense that non-tightly secure schemes exist. Similarly, already for a slightly generalized definition of “extended Schnorr-like” schemes, tightly secure schemes exist. Our main result employs a meta-reduction with a new “filtering” technique that may be of independent interest.