UC San Diego

Digital signature schemes are ubiquitous in real-world applications of cryptography. They are the core cryptographic building block for public-key infrastructures and distributed ledgers. Yet, the exact security of signature and signature-related schemes are often unknown, due to gaps in their security analyses.

A security proof for a cryptographic scheme S rules out attacks on the scheme assuming hardness of some underlying problem P, for example the discrete-logarithm on elliptic curves. Often, there are gaps between the quantitative security evidenced by cryptanalysis and the quantitative security given by security proofs. For many deployed schemes, quantitative security proofs do not give any meaningful security guarantees. The study of concrete security aims to eliminate this gap.

In this work, we study the concrete security of (1) a ``big-key'' identification scheme by Alwen, Dodis, and Wichs, (2) Schnorr identification and signature schemes, and (3) discrete-logarithm-based multi-signature schemes. We identify and tighten the gaps between theoretical guarantees, practical expectations, and best-known cryptanalysis.