Lior Rotem: Tighter Security for Schnorr Identification and Signatures: A High-Moment Forking Lemma for Sigma- Protocols

Friday, November 5, 2021 - 1:00pm to 2:30pm
email for Zoom Link, 32-370 for hybrid
Lior Rotem


The Schnorr identification and signature schemes have been amongst the most influential cryptographic protocols of the past three decades. Unfortunately, the known approaches for basing their security on the hardness of the discrete logarithm problem encounter a quadratic gap between the best-known attacks via discrete-logarithm computation and the best-known provable security bounds. This gap leads to either degraded efficiency or degraded provable security when setting concrete security parameters (e.g., group size).


This talk will present tighter security guarantees for Schnorr identification and signatures schemes, introducing a novel high-moment generalization of the classic forking lemma. The proof relies on a natural refinement of the standard-model hardness of the DLOG problem, distilling a key aspect of its "generic hardness" by requiring that the success probability of any DLOG algorithm is dominated by the second moment of its running time. I will also discuss generalizations of these results to other identification and signature schemes obtained from Sigma-protocols and to higher moments of the attacker's running time. 


The talk is based on joint work with Gil Segev.