Welcome to the resource topic for 2019/1105
Title:
On the Multi-User Security of Short Schnorr Signatures with Preprocessing
Authors: Jeremiah Blocki, 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 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.
ePrint: https://eprint.iacr.org/2019/1105
Talk: https://www.youtube.com/watch?v=qo9as48W8mI
Slides: https://iacr.org/submit/files/slides/2022/eurocrypt/eurocrypt2022/47/slides.pptx
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .