Paper 2012/658

Digital Signatures with Minimal Overhead from Indifferentiable Random Invertible Functions

Eike Kiltz, Krzysztof Pietrzak, and Mario Szegedy


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 overhead $|\tau|-|m|$. A simple argument shows that for any scheme with ``$n$ bits security" $|\tau|-|m|\ge 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.

Available format(s)
Publication info
Published elsewhere. A preliminary version appears in CRYPTO 2013. This is the full version.
Digital signaturesindifferentiabilityFeistelAdditive combinatoricsCayley graph.
Contact author(s)
krzpie @ gmail com
2013-06-12: revised
2012-11-26: received
See all versions
Short URL
Creative Commons Attribution


      author = {Eike Kiltz and Krzysztof Pietrzak and Mario Szegedy},
      title = {Digital Signatures with Minimal Overhead from Indifferentiable Random Invertible Functions},
      howpublished = {Cryptology ePrint Archive, Paper 2012/658},
      year = {2012},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.