The exact PRF security of truncation: Tight bounds for keyed sponges and truncated CBC

P. Gazi, K.Z. Pietrzak, S. Tessaro, in:, Springer, 2015, pp. 368–387.

Download
OA 592.30 KB

Conference Paper | Published | English
Department
Series Title
LNCS
Abstract
This paper studies the concrete security of PRFs and MACs obtained by keying hash functions based on the sponge paradigm. One such hash function is KECCAK, selected as NIST’s new SHA-3 standard. In contrast to other approaches like HMAC, the exact security of keyed sponges is not well understood. Indeed, recent security analyses delivered concrete security bounds which are far from existing attacks. This paper aims to close this gap. We prove (nearly) exact bounds on the concrete PRF security of keyed sponges using a random permutation. These bounds are tight for the most relevant ranges of parameters, i.e., for messages of length (roughly) l ≤ min{2n/4, 2r} blocks, where n is the state size and r is the desired output length; and for l ≤ q queries (to the construction or the underlying permutation). Moreover, we also improve standard-model bounds. As an intermediate step of independent interest, we prove tight bounds on the PRF security of the truncated CBC-MAC construction, which operates as plain CBC-MAC, but only returns a prefix of the output.
Publishing Year
Date Published
2015-08-01
Volume
9215
Page
368 - 387
Conference
CRYPTO: International Cryptology Conference
Conference Location
Santa Barbara, CA, United States
Conference Date
2015-08-16 – 2015-08-20
IST-REx-ID

Cite this

Gazi P, Pietrzak KZ, Tessaro S. The exact PRF security of truncation: Tight bounds for keyed sponges and truncated CBC. In: Vol 9215. Springer; 2015:368-387. doi:10.1007/978-3-662-47989-6_18
Gazi, P., Pietrzak, K. Z., & Tessaro, S. (2015). The exact PRF security of truncation: Tight bounds for keyed sponges and truncated CBC (Vol. 9215, pp. 368–387). Presented at the CRYPTO: International Cryptology Conference, Santa Barbara, CA, United States: Springer. https://doi.org/10.1007/978-3-662-47989-6_18
Gazi, Peter, Krzysztof Z Pietrzak, and Stefano Tessaro. “The Exact PRF Security of Truncation: Tight Bounds for Keyed Sponges and Truncated CBC,” 9215:368–87. Springer, 2015. https://doi.org/10.1007/978-3-662-47989-6_18.
P. Gazi, K. Z. Pietrzak, and S. Tessaro, “The exact PRF security of truncation: Tight bounds for keyed sponges and truncated CBC,” presented at the CRYPTO: International Cryptology Conference, Santa Barbara, CA, United States, 2015, vol. 9215, pp. 368–387.
Gazi P, Pietrzak KZ, Tessaro S. 2015. The exact PRF security of truncation: Tight bounds for keyed sponges and truncated CBC. CRYPTO: International Cryptology Conference, LNCS, vol. 9215. 368–387.
Gazi, Peter, et al. The Exact PRF Security of Truncation: Tight Bounds for Keyed Sponges and Truncated CBC. Vol. 9215, Springer, 2015, pp. 368–87, doi:10.1007/978-3-662-47989-6_18.
Main File(s)
File Name
Access Level
OA Open Access
Last Uploaded
2018-12-12T10:10:38Z


Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar