Welcome to the resource topic for 2012/658
Title:
Digital Signatures with Minimal Overhead from Indifferentiable Random Invertible Functions
Authors: Eike Kiltz, Krzysztof Pietrzak, 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 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.
ePrint: https://eprint.iacr.org/2012/658
Talk: https://www.youtube.com/watch?v=xzcRlrSriyw
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .