Paper 2019/1105

On the Multi-User Security of Short Schnorr Signatures with Preprocessing

Jeremiah Blocki, Purdue University West Lafayette
Seunghoon Lee, Purdue University West Lafayette

The Schnorr signature scheme is an efficient digital signature scheme with short signature lengths, i.e., $4k$-bit signatures for $k$ bits of security. A Schnorr signature $\sigma$ over a group of size $p\approx 2^{2k}$ consists of a tuple $(s,e)$, where $e \in \{0,1\}^{2k}$ is a hash output and $s\in \mathbb{Z}_p$ must be computed using the secret key. While the hash output $e$ requires $2k$ bits to encode, Schnorr proposed that it might be possible to truncate the hash value without adversely impacting security. In this paper, we prove that short Schnorr signatures of length $3k$ bits provide $k$ bits of multi-user security in the (Shoup's) generic group model and the programmable random oracle model. We further analyze the multi-user security of key-prefixed short Schnorr signatures against preprocessing attacks, showing that it is possible to obtain secure signatures of length $3k + \log S$ bits. Here, $S$ denotes the size of the hint generated by our preprocessing attacker, e.g., if $S=2^{k/2}$, then we would obtain $3.5k$-bit signatures. Our techniques easily generalize to several other Fiat-Shamir-based signature schemes, allowing us to establish analogous results for Chaum-Pedersen signatures and Katz-Wang signatures. As a building block, we also analyze the $1$-out-of-$N$ discrete-log problem in the generic group model, with and without preprocessing.

Note: This is the full version of the paper with the same title which appeared at EUROCRYPT 2022. Note: Improved multi-user security bounds to eliminate unnecessary dependences on N (updated on 02/2023).

Available format(s)
Public-key cryptography
Publication info
A minor revision of an IACR publication in EUROCRYPT 2022
Short Schnorr SignaturesGeneric Group ModelRandom Oracle ModelMulti-User Security1-out-of-N Discrete-Log ProblemPreprocessing Attacks
Contact author(s)
jblocki @ purdue edu
lee2856 @ purdue edu
2023-02-08: last of 4 revisions
2019-09-29: received
See all versions
Short URL
Creative Commons Attribution


      author = {Jeremiah Blocki and Seunghoon Lee},
      title = {On the Multi-User Security of Short Schnorr Signatures with Preprocessing},
      howpublished = {Cryptology ePrint Archive, Paper 2019/1105},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.