Name
Title | ||
|---|---|---|
Digital Signatures with Minimal Overhead from Indifferentiable Random Invertible Functions. |
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 vertical bar tau vertical bar - vertical bar m vertical bar. A simple argument shows that for any scheme with "n bits security" vertical bar tau vertical bar - vertical bar m vertical bar >= 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(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. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1007/978-3-642-40041-4_31 | ADVANCES IN CRYPTOLOGY - CRYPTO 2013, PT I |
Keywords | Field | DocType |
digital signatures,indifferentiability,Feistel,Additive combinatorics,Cayley graph | Discrete mathematics,Upper and lower bounds,Cayley graph,Random oracle,Theoretical computer science,Digital signature,Security parameter,Mathematics,Bounded function,Random function,Schnorr signature | Conference |
Volume | ISSN | Citations |
8042 | 0302-9743 | 8 |
PageRank | References | Authors |
0.53 | 23 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Eike Kiltz | 1 | 2872 | 117.46 |
| Krzysztof Pietrzak | 2 | 1513 | 72.60 |
| Mario Szegedy | 3 | 3358 | 325.80 |