---
_id: '1671'
abstract:
- lang: eng
  text: 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.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Peter
  full_name: Gazi, Peter
  id: 3E0BFE38-F248-11E8-B48F-1D18A9856A87
  last_name: Gazi
- first_name: Krzysztof Z
  full_name: Pietrzak, Krzysztof Z
  id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
  last_name: Pietrzak
  orcid: 0000-0002-9139-1654
- first_name: Stefano
  full_name: Tessaro, Stefano
  last_name: Tessaro
citation:
  ama: '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>'
  apa: '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>'
  chicago: '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>.'
  ieee: '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.'
  ista: '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.'
  mla: '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>.'
  short: P. Gazi, K.Z. Pietrzak, S. Tessaro, in:, Springer, 2015, pp. 368–387.
conference:
  end_date: 2015-08-20
  location: Santa Barbara, CA, United States
  name: 'CRYPTO: International Cryptology Conference'
  start_date: 2015-08-16
corr_author: '1'
date_created: 2018-12-11T11:53:23Z
date_published: 2015-08-01T00:00:00Z
date_updated: 2025-09-23T13:50:18Z
day: '01'
ddc:
- '004'
- '005'
department:
- _id: KrPi
doi: 10.1007/978-3-662-47989-6_18
ec_funded: 1
external_id:
  isi:
  - '000364183000018'
file:
- access_level: open_access
  checksum: 17d854227b3b753fd34f5d29e5b5a32e
  content_type: application/pdf
  creator: system
  date_created: 2018-12-12T10:10:38Z
  date_updated: 2020-07-14T12:45:11Z
  file_id: '4827'
  file_name: IST-2016-673-v1+1_053.pdf
  file_size: 592296
  relation: main_file
file_date_updated: 2020-07-14T12:45:11Z
has_accepted_license: '1'
intvolume: '      9215'
isi: 1
language:
- iso: eng
month: '08'
oa: 1
oa_version: Submitted Version
page: 368 - 387
project:
- _id: 258C570E-B435-11E9-9278-68D0E5697425
  call_identifier: FP7
  grant_number: '259668'
  name: Provable Security for Physical Cryptography
publication_status: published
publisher: Springer
publist_id: '5478'
pubrep_id: '673'
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'The exact PRF security of truncation: Tight bounds for keyed sponges and truncated
  CBC'
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 9215
year: '2015'
...