Digital Signatures with Minimal Overhead.
Eike Kiltz, Krzysztof Pietrzak, Márió Szegedy · 2012
In a digital signature scheme with message recovery, rather than transmitting the message m and its signature σ, a single enhanced signature τ is transmitted. The verifier is able to recover m from τ and at the same time verify its authenticity. The two most important parameters of such a scheme are its security and the overhead |τ | − |m|. A simple argument shows that for any scheme with “n bits security ” |τ | − |m | ≥ n, i.e., the overhead is at least the security. The best previous constructions required an overhead of 2n. In this paper we show that the n bit lower bound can basically be matched. Concretely, we propose a new simple RSA-based digital signature scheme that, for n = 80 bits security in the random oracle model, has an overhead of ≈ 90 bits. At the core of our security analysis is an almost tight upper bound for the expected number of edges of the densest “small ” subgraph of a random Cayley graph, which may be of independent interest.