Digital Signatures with Minimal Overhead from Indifferentiable Random Invertible Functions

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 overhead |

τ

| − |

m

|. A simple argument shows that for any scheme with “

n

bits security” |

τ

| − |

m

| ≥ 

n

, i.e., the overhead is lower bounded by the security parameter

n

. 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.