Paper 2021/971
Tighter Security for Schnorr Identification and Signatures: A HighMoment Forking Lemma for $\Sigma$Protocols
Lior Rotem and Gil Segev
Abstract
The Schnorr identification and signature schemes have been amongst the most influential cryptographic protocols of the past three decades. Unfortunately, although the bestknown attacks on these two schemes are via discretelogarithm computation, the known approaches for basing their security on the hardness of the discrete logarithm problem encounter the ``squareroot barrier''. In particular, in any group of order $p$ where Shoup's generic hardness result for the discrete logarithm problem is believed to hold (and is thus used for setting concrete security parameters), the bestknown $t$time attacks on the Schnorr identification and signature schemes have success probability $t^2/p$, whereas existing proofs of security only rule out attacks with success probabilities $(t^2/p)^{1/2}$ and $(q_{\mathcal{H}} \cdot t^2/p)^{1/2}$, respectively, where $q_{\mathcal{H}}$ denotes the number of randomoracle queries issued by the attacker. We establish tighter security guarantees for identification and signature schemes which result from $\Sigma$protocols with special soundness based on the hardness of their underlying relation, and in particular for Schnorr's schemes based on the hardness of the discrete logarithm problem. We circumvent the squareroot barrier by introducing a highmoment generalization of the classic forking lemma, relying on the assumption that the underlying relation is ``$d$moment hard'': The success probability of any algorithm in the task of producing a witness for a random instance is dominated by the $d$th moment of the algorithm's running time. In the concrete context of the discrete logarithm problem, already Shoup's original proof shows that the discrete logarithm problem is $2$moment hard in the genericgroup model, and thus our assumption can be viewed as a highlyplausible strengthening of the discrete logarithm assumption in any group where no betterthangeneric algorithms are currently known. Applying our highmoment forking lemma in this context shows that, assuming the $2$moment hardness of the discrete logarithm problem, any $t$time attacker breaks the security of the Schnorr identification and signature schemes with probabilities at most $(t^2/p)^{2/3}$ and $(q_{\mathcal{H}} \cdot t^2/p)^{2/3}$, respectively.
Metadata
 Available format(s)
 Publication info
 A major revision of an IACR publication in CRYPTO 2021
 Keywords
 SignaturesIdentification SchemesSigma ProtocolsForking Lemma
 Contact author(s)

lior rotem @ cs huji ac il
segev @ cs huji ac il  History
 20210722: received
 Short URL
 https://ia.cr/2021/971
 License

CC BY
BibTeX
@misc{cryptoeprint:2021/971, author = {Lior Rotem and Gil Segev}, title = {Tighter Security for Schnorr Identification and Signatures: A HighMoment Forking Lemma for $\Sigma$Protocols}, howpublished = {Cryptology {ePrint} Archive, Paper 2021/971}, year = {2021}, url = {https://eprint.iacr.org/2021/971} }