Tight Bounds on Uniform-Challenge Reductions from Sigma Protocols

Sigma protocols are fundamental cryptographic tools, serving as the foundation of many practical schemes—most notably, the Schnorr identification and signature schemes. To prove the security of Sigma protocols, one typically reduces breaking a Sigma protocol to solving a presumed hard problem (e.g., computing the discrete logarithm in a certain group). In many settings, however, these reductions are not tight: given an adversary that breaks a Sigma protocol with probability $\varepsilon$, the reduction only yields an adversary for the underlying problem with probability $\varepsilon^2$. This quadratic loss affects efficiency, as it forces choosing larger security parameters to reach a target security level.

In this work, we show that this quadratic loss is inherent for two natural classes of reductions. For interactive protocols, we prove it for uniform-challenge, black-box reductions, which query the adversary using uniformly sampled challenges. For non-interactive protocols (i.e., in the random-oracle model), we prove it for weakly programmable, black-box reductions, which answer the adversary’s oracle queries with uniformly sampled outputs. Applying our bounds to the reductions from Schnorr identification and signatures to discrete logarithm yields lower bounds that match known positive results—namely, the classical worst-case reduction of Pointcheval and Stern (Journal of Cryptology, 2000) and the higher-moment reduction of Rotem and Segev (Journal of Cryptology, 2024).

Our approach reduces the analysis of such reductions to the values of simple hitting games—combinatorial games that we introduce. Bounding these games is our main technical contribution, and we believe these bounds can enable more modular proofs of related results.