---
OA_type: closed access
_id: '3216'
abstract:
- lang: eng
  text: "We prove a new upper bound on the advantage of any adversary for distinguishing
    the encrypted CBC-MAC (EMAC) based on random permutations from a random function.
    Our proof uses techniques recently introduced in [BPR05], which again were inspired
    by [DGH + 04].\r\nThe bound we prove is tight — in the sense that it matches the
    advantage of known attacks up to a constant factor — for a wide range of the parameters:
    let n denote the block-size, q the number of queries the adversary is allowed
    to make and ℓ an upper bound on the length (i.e. number of blocks) of the messages,
    then for ℓ ≤ 2 n/8 and q≥ł2 the advantage is in the order of q 2/2 n (and in particular
    independent of ℓ). This improves on the previous bound of q 2ℓΘ(1/ln ln ℓ)/2 n
    from [BPR05] and matches the trivial attack (which thus is basically optimal)
    where one simply asks random queries until a collision is found."
acknowledgement: Part of this work is supported by the Commission of the European
  Communities through the IST program under contract IST-2002-507932 ECRYPT.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Krzysztof Z
  full_name: Pietrzak, Krzysztof Z
  id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
  last_name: Pietrzak
  orcid: 0000-0002-9139-1654
citation:
  ama: 'Pietrzak KZ. A tight bound for EMAC. In: <i>Proceedings of the 33rd International
    Conference on Automata, Languages and Programming - Volume Part II</i>. Vol 4052.
    Springer Nature; 2006:168-179. doi:<a href="https://doi.org/10.1007/11787006_15">10.1007/11787006_15</a>'
  apa: Pietrzak, K. Z. (2006). A tight bound for EMAC. In <i>Proceedings of the 33rd
    international conference on Automata, Languages and Programming - Volume Part
    II</i> (Vol. 4052, pp. 168–179). Springer Nature. <a href="https://doi.org/10.1007/11787006_15">https://doi.org/10.1007/11787006_15</a>
  chicago: Pietrzak, Krzysztof Z. “A Tight Bound for EMAC.” In <i>Proceedings of the
    33rd International Conference on Automata, Languages and Programming - Volume
    Part II</i>, 4052:168–79. Springer Nature, 2006. <a href="https://doi.org/10.1007/11787006_15">https://doi.org/10.1007/11787006_15</a>.
  ieee: K. Z. Pietrzak, “A tight bound for EMAC,” in <i>Proceedings of the 33rd international
    conference on Automata, Languages and Programming - Volume Part II</i>, 2006,
    vol. 4052, pp. 168–179.
  ista: 'Pietrzak KZ. 2006. A tight bound for EMAC. Proceedings of the 33rd international
    conference on Automata, Languages and Programming - Volume Part II. ICALP: Automata,
    Languages and Programming, LNCS, vol. 4052, 168–179.'
  mla: Pietrzak, Krzysztof Z. “A Tight Bound for EMAC.” <i>Proceedings of the 33rd
    International Conference on Automata, Languages and Programming - Volume Part
    II</i>, vol. 4052, Springer Nature, 2006, pp. 168–79, doi:<a href="https://doi.org/10.1007/11787006_15">10.1007/11787006_15</a>.
  short: K.Z. Pietrzak, in:, Proceedings of the 33rd International Conference on Automata,
    Languages and Programming - Volume Part II, Springer Nature, 2006, pp. 168–179.
conference:
  name: 'ICALP: Automata, Languages and Programming'
date_created: 2018-12-11T12:02:04Z
date_published: 2006-07-28T00:00:00Z
date_updated: 2026-09-02T08:25:36Z
day: '28'
doi: 10.1007/11787006_15
extern: '1'
fulldoi: https://doi.org/10.1007/11787006_15
intvolume: '      4052'
language:
- iso: eng
month: '07'
oa_version: None
page: 168 - 179
publication: Proceedings of the 33rd international conference on Automata, Languages
  and Programming - Volume Part II
publication_identifier:
  eisbn:
  - '9783540359081'
  isbn:
  - '9783540359074'
publication_status: published
publisher: Springer Nature
publist_id: '3463'
status: public
title: A tight bound for EMAC
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 4052
year: '2006'
...