May 16, 2021

Dedicated Forum to help removing adware, malware, spyware, ransomware, trojans, viruses and more!

On the Multi-User Security of Short Schnorr Signatures with Preprocessing, by Jeremiah Blocki and Seunghoon Lee

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 $papprox 2^{2k}$ consists of a tuple $(s,e)$, where $e in {0,1}^{2k}$ is a hash output and $sin 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