IACR News item: 25 November 2012
Eike Kiltz, Krzysztof Pietrzak, Mario Szegedy
ePrint Reportverify 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.
Additional news items may be found on the IACR news page.