Cryptology ePrint Archive: Report 2012/658

Digital Signatures with Minimal Overhead

Eike Kiltz and Krzysztof Pietrzak and Mario Szegedy

Abstract: In a digital signature scheme with message recovery, rather than transmitting the message $m$ and its signature $\sigma$, a single enhanced signature $\tau$ is transmitted. The verifier is able to recover $m$ from $\tau$ and at the same time verify its authenticity. The two most important parameters of such a scheme are its security and the overhead $|\tau|-|m|$. A simple argument shows that for any scheme with ``$n$ bits security" $|\tau|-|m|\ge 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 $\approx 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.

Category / Keywords: public-key cryptography / digital signatures, cayley graphs

Date: received 19 Nov 2012, last revised 22 Nov 2012

Contact author: krzpie at gmail com

Available formats: PDF | BibTeX Citation

Version: 20121126:012822 (All versions of this report)

Discussion forum: Show discussion | Start new discussion