Limitations of the Meta Reduction Technique: The Case of Schnorr Signatures


Our results are twofold. On the one hand, we use the meta-reduction technique to show that the security of Schnorr signatures cannot be proven equivalent to the discrete logarithm problem without programming the random oracle. This result holds under the one-more discrete logarithm assumption and for a large natural class of reductions, we call simple reductions. This class in particular subsumes those used in previous proofs of security in the (programmable) random oracle model.

On the other hand, we show that a stronger result, i.e., an unconditional one, where the meta-reduction also solves the discrete logarithm problem, is most likely not achievable. In fact, we prove that for any randomized signature scheme, finding a meta-reduction that solves a hard non-interactive problem is equivalent to finding an adversary against the strong existential unforgeability of the signature scheme.

Master Thesis, Technische Universit├Ąt Darmstadt