Digital signatures with minimal overhead from indifferentiable random invertible functions

Kiltz, Eike and Pietrzak, Krzysztof and Szegedy, Mario (2013) Digital signatures with minimal overhead from indifferentiable random invertible functions. In: CRYPTO: International Cryptology Conference, August 18-22, 2013, Santa Barbara, CA, USA.

[img] Text
658.pdf - Submitted Version
Available under License Creative Commons Attribution.
[IST-2016-685-v1+1]
Download (481Kb)
Official URL: http://dx.doi.org/10.1007/978-3-642-40041-4_31

Abstract

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 + logq 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(logq 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.

Item Type: Conference or Workshop Item (Paper)
Subjects: 000 Computer science, knowledge & general works > 000 Computer science, knowledge & systems
000 Computer science, knowledge & general works > 000 Computer science, knowledge & systems > 004 Data processing & computer science
Research Group: Pietrzak Group
SWORD Depositor: Sword Import User
Depositing User: Sword Import User
Date Deposited: 02 Dec 2016 08:42
Last Modified: 05 Sep 2017 14:26
URI: https://repository.ist.ac.at/id/eprint/685

Actions (login required)

View Item View Item