Cryptology ePrint Archive: Report 2019/1105

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 ]