Kiltz, Eike; Pietrzak, Krzysztof ZIST Austria; Szegedy, Mario
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.
571 - 588
CRYPTO: International Cryptology Conference
Santa Barbara, CA, United States
2013-08-18 – 2013-08-22
Kiltz E, Pietrzak KZ, Szegedy M. Digital signatures with minimal overhead from indifferentiable random invertible functions. 2013;8042:571-588. doi:10.1007/978-3-642-40041-4_31
Kiltz, E., Pietrzak, K. Z., & Szegedy, M. (2013). Digital signatures with minimal overhead from indifferentiable random invertible functions. Presented at the CRYPTO: International Cryptology Conference, Santa Barbara, CA, United States: Springer. https://doi.org/10.1007/978-3-642-40041-4_31
Kiltz, Eike, Krzysztof Z Pietrzak, and Mario Szegedy. “Digital Signatures with Minimal Overhead from Indifferentiable Random Invertible Functions.” Lecture Notes in Computer Science. Springer, 2013. https://doi.org/10.1007/978-3-642-40041-4_31.
E. Kiltz, K. Z. Pietrzak, and M. Szegedy, “Digital signatures with minimal overhead from indifferentiable random invertible functions,” vol. 8042. Springer, pp. 571–588, 2013.
Kiltz E, Pietrzak KZ, Szegedy M. 2013. Digital signatures with minimal overhead from indifferentiable random invertible functions. 8042, 571–588.
Kiltz, Eike, et al. Digital Signatures with Minimal Overhead from Indifferentiable Random Invertible Functions. Vol. 8042, Springer, 2013, pp. 571–88, doi:10.1007/978-3-642-40041-4_31.