conference paper published yes Peter Gazi author 3E0BFE38-F248-11E8-B48F-1D18A9856A87 Krzysztof Z Pietrzak author 3E04A7AA-F248-11E8-B48F-1D18A9856A870000-0002-9139-1654 Stefano Tessaro author KrPi department CRYPTO: International Cryptology Conference Provable Security for Physical Cryptography project 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. https://research-explorer.ista.ac.at/download/1671/4827/IST-2016-673-v1+1_053.pdf application/pdfno Springer2015Santa Barbara, CA, United States eng 00036418300001810.1007/978-3-662-47989-6_18 9215368 - 387 P. Gazi, K.Z. Pietrzak, S. Tessaro, in:, Springer, 2015, pp. 368–387. Gazi, Peter, et al. <i>The Exact PRF Security of Truncation: Tight Bounds for Keyed Sponges and Truncated CBC</i>. Vol. 9215, Springer, 2015, pp. 368–87, doi:<a href="https://doi.org/10.1007/978-3-662-47989-6_18">10.1007/978-3-662-47989-6_18</a>. 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. <a href="https://doi.org/10.1007/978-3-662-47989-6_18">https://doi.org/10.1007/978-3-662-47989-6_18</a>. 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, P., Pietrzak, K. Z., &#38; 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. <a href="https://doi.org/10.1007/978-3-662-47989-6_18">https://doi.org/10.1007/978-3-662-47989-6_18</a> 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:<a href="https://doi.org/10.1007/978-3-662-47989-6_18">10.1007/978-3-662-47989-6_18</a> 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. 16712018-12-11T11:53:23Z2025-09-23T13:50:18Z