Currently, the best known constructions in the random oracle model are far from this lower bound requiring an overhead of $n+\log q_h$, where $q_h$ is the number of queries to the random oracle. In this paper we give a construction which basically matches the $n$ bit lower bound. We propose a simple digital signature scheme with $n+o(\log q_h)$ bits overhead, where $q_h$ denotes the number of random oracle queries.
Our construction works in two steps. First, we propose a signature scheme with message recovery having optimal overhead in a new ideal model, the random invertible function model. Second, we show that a four-round Feistel network with random oracles as round functions is tightly "public-indifferentiable'' from a random invertible function. At the core of our indifferentiability proof 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: Digital signatures, indifferentiability, Feistel, Additive combinatorics, Cayley graph. Publication Info: A preliminary version appears in CRYPTO 2013. This is the full version. Date: received 19 Nov 2012, last revised 12 Jun 2013 Contact author: krzpie at gmail com Available format(s): PDF | BibTeX Citation Version: 20130612:195821 (All versions of this report) Short URL: ia.cr/2012/658 Discussion forum: Show discussion | Start new discussion