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

*Jeremiah Blocki and Seunghoon Lee*

**Abstract: **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 \emph{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 + \log N$ bits. Here, $N$ denotes the number of users and $S$ denotes the size of the hint generated by our preprocessing attacker, e.g., if $S=2^{k/2}$, then we would obtain secure $3.75k$-bit signatures for groups of up to $N \leq 2^{k/4}$ users.

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

**Category / Keywords: **public-key cryptography / Short Schnorr Signatures, Generic Group Model, Random Oracle Model, Multi-User Security, 1-out-of-N Discrete-Log Problem, Preprocessing Attacks

**Date: **received 26 Sep 2019, last revised 4 May 2021

**Contact author: **jblocki at purdue edu, lee2856 at purdue edu

**Available format(s): **PDF | BibTeX Citation

**Version: **20210504:233624 (All versions of this report)

**Short URL: **ia.cr/2019/1105

[ Cryptology ePrint archive ]