---
OA_place: publisher
OA_type: gold
_id: '3213'
abstract:
- lang: eng
  text: "We study the question whether the sequential or parallel composition of two
    functions, each indistinguishable from a random function by non-adaptive distinguishers
    is secure against adaptive distinguishers. The sequential composition of F and
    G is the function G(F()), the parallel composition is F G where ⋆ is some group
    operation. It has been shown that composition indeed gives adaptive security in
    the information theoretic setting, but unfortunately the proof does not translate
    into the more interesting computational case.\r\nIn this work we show that in
    the computational setting composition does not imply adaptive security: If there
    is a prime order cyclic group where the decisional Diffie-Hellman assumption holds,
    then there are functions F and G which are indistinguishable by non-adaptive polynomially
    time-bounded adversaries, but whose parallel composition can be completely broken
    (i.e. we recover the key) with only three adaptive queries. We give a similar
    result for sequential composition. Interestingly, we need a standard assumption
    from the asymmetric (aka. public-key) world to prove a negative result for symmetric
    (aka. private-key) systems."
acknowledgement: Supported by the Swiss National Science Foundation, project No. 200020-103847/1.
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. Composition does not imply adaptive security. In: <i>25th Annual
    International Cryptology Conference</i>. Vol 3621. Springer Nature; 2005:55-65.
    doi:<a href="https://doi.org/10.1007/11535218_4">10.1007/11535218_4</a>'
  apa: 'Pietrzak, K. Z. (2005). Composition does not imply adaptive security. In <i>25th
    Annual International Cryptology Conference</i> (Vol. 3621, pp. 55–65). Santa Barbara,
    CA, United States: Springer Nature. <a href="https://doi.org/10.1007/11535218_4">https://doi.org/10.1007/11535218_4</a>'
  chicago: Pietrzak, Krzysztof Z. “Composition Does Not Imply Adaptive Security.”
    In <i>25th Annual International Cryptology Conference</i>, 3621:55–65. Springer
    Nature, 2005. <a href="https://doi.org/10.1007/11535218_4">https://doi.org/10.1007/11535218_4</a>.
  ieee: K. Z. Pietrzak, “Composition does not imply adaptive security,” in <i>25th
    Annual International Cryptology Conference</i>, Santa Barbara, CA, United States,
    2005, vol. 3621, pp. 55–65.
  ista: 'Pietrzak KZ. 2005. Composition does not imply adaptive security. 25th Annual
    International Cryptology Conference. CRYPTO: International Cryptology Conference,
    LNCS, vol. 3621, 55–65.'
  mla: Pietrzak, Krzysztof Z. “Composition Does Not Imply Adaptive Security.” <i>25th
    Annual International Cryptology Conference</i>, vol. 3621, Springer Nature, 2005,
    pp. 55–65, doi:<a href="https://doi.org/10.1007/11535218_4">10.1007/11535218_4</a>.
  short: K.Z. Pietrzak, in:, 25th Annual International Cryptology Conference, Springer
    Nature, 2005, pp. 55–65.
conference:
  end_date: 2005-08-18
  location: Santa Barbara, CA, United States
  name: 'CRYPTO: International Cryptology Conference'
  start_date: 2005-08-14
das_tickbox: '1'
date_created: 2018-12-11T12:02:03Z
date_published: 2005-09-12T00:00:00Z
date_updated: 2026-07-02T07:47:38Z
day: '12'
doi: 10.1007/11535218_4
extern: '1'
fulldoi: https://doi.org/10.1007/11535218_4
intvolume: '      3621'
language:
- iso: eng
month: '09'
oa_version: None
page: 55 - 65
publication: 25th Annual International Cryptology Conference
publication_identifier:
  eisbn:
  - '9783540318705'
  isbn:
  - '9783540281146'
publication_status: published
publisher: Springer Nature
publist_id: '3468'
status: public
title: Composition does not imply adaptive security
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 3621
year: '2005'
...
---
OA_type: closed access
_id: '3212'
abstract:
- lang: eng
  text: "The Full-Domain Hash (FDH) signature scheme [3] forms one the most basic
    usages of random oracles. It works with a family F of trapdoor permutations (TDP),
    where the signature of m is computed as f−1(h(m)) (here f ∈R F and h is modelled
    as a random oracle). It is known to be existentially unforgeable for any TDP family
    F [3], although a much tighter security reduction is known for a restrictive class
    of TDP’s [10,14] — namely, those induced by a family of claw-free permutations
    (CFP) pairs. The latter result was shown [11] to match the best possible “black-box”
    security reduction in the random oracle model, irrespective of the TDP family
    F (e.g., RSA) one might use.\r\nIn this work we investigate the question if it
    is possible to instantiate the random oracle h with a “real” family of hash functions
    H such that the corresponding schemes can be proven secure in the standard model,
    under some natural assumption on the family F. Our main result rules out the existence
    of such instantiations for any assumption on F which (1) is satisfied by a family
    of random permutations; and (2) does not allow the attacker to invert f ∈R F on
    an a-priori unbounded number of points. Moreover, this holds even if the choice
    of H can arbitrarily depend on f. As an immediate corollary, we rule out instantiating
    FDH based on general claw-free permutations, which shows that in order to prove
    the security of FDH in the standard model one must utilize significantly more
    structure on F than what is sufficient for the best proof of security in the random
    oracle model."
acknowledgement: Supported by NSF CAREER Award CCR-0133806 and TC Grant No.CCR-0311095.
  Supported by the Swiss National Science Foundation, project No. 200020-103847/1
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Yevgeniy
  full_name: Dodis, Yevgeniy
  last_name: Dodis
- first_name: Roberto
  full_name: Oliveira, Roberto
  last_name: Oliveira
- 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: 'Dodis Y, Oliveira R, Pietrzak KZ. On the generic insecurity of the full domain
    hash. In: <i>25th Annual International Cryptology Conference</i>. Vol 3621. Springer
    Nature; 2005:449-466. doi:<a href="https://doi.org/10.1007/11535218_27">10.1007/11535218_27</a>'
  apa: 'Dodis, Y., Oliveira, R., &#38; Pietrzak, K. Z. (2005). On the generic insecurity
    of the full domain hash. In <i>25th Annual International Cryptology Conference</i>
    (Vol. 3621, pp. 449–466).  Santa Barbara, CA, United States: Springer Nature.
    <a href="https://doi.org/10.1007/11535218_27">https://doi.org/10.1007/11535218_27</a>'
  chicago: Dodis, Yevgeniy, Roberto Oliveira, and Krzysztof Z Pietrzak. “On the Generic
    Insecurity of the Full Domain Hash.” In <i>25th Annual International Cryptology
    Conference</i>, 3621:449–66. Springer Nature, 2005. <a href="https://doi.org/10.1007/11535218_27">https://doi.org/10.1007/11535218_27</a>.
  ieee: Y. Dodis, R. Oliveira, and K. Z. Pietrzak, “On the generic insecurity of the
    full domain hash,” in <i>25th Annual International Cryptology Conference</i>,  Santa
    Barbara, CA, United States, 2005, vol. 3621, pp. 449–466.
  ista: 'Dodis Y, Oliveira R, Pietrzak KZ. 2005. On the generic insecurity of the
    full domain hash. 25th Annual International Cryptology Conference. CRYPTO: International
    Cryptology Conference, LNCS, vol. 3621, 449–466.'
  mla: Dodis, Yevgeniy, et al. “On the Generic Insecurity of the Full Domain Hash.”
    <i>25th Annual International Cryptology Conference</i>, vol. 3621, Springer Nature,
    2005, pp. 449–66, doi:<a href="https://doi.org/10.1007/11535218_27">10.1007/11535218_27</a>.
  short: Y. Dodis, R. Oliveira, K.Z. Pietrzak, in:, 25th Annual International Cryptology
    Conference, Springer Nature, 2005, pp. 449–466.
conference:
  end_date: 2005-08-18
  location: ' Santa Barbara, CA, United States'
  name: 'CRYPTO: International Cryptology Conference'
  start_date: 2005-08-14
das_tickbox: '1'
date_created: 2018-12-11T12:02:03Z
date_published: 2005-09-12T00:00:00Z
date_updated: 2026-07-02T08:05:18Z
day: '12'
doi: 10.1007/11535218_27
extern: '1'
fulldoi: https://doi.org/10.1007/11535218_27
intvolume: '      3621'
language:
- iso: eng
month: '09'
oa_version: None
page: 449 - 466
publication: 25th Annual International Cryptology Conference
publication_identifier:
  eisbn:
  - '9783540318705'
  isbn:
  - '9783540281146'
publication_status: published
publisher: Springer Nature
publist_id: '3470'
status: public
title: On the generic insecurity of the full domain hash
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 3621
year: '2005'
...
---
OA_place: publisher
OA_type: gold
_id: '3211'
abstract:
- lang: eng
  text: We present an improved bound on the advantage of any q-query adversary at
    distinguishing between the CBC MAC over a random n-bit permutation and a random
    function outputting n bits. The result assumes that no message queried is a prefix
    of any other, as is the case when all messages to be MACed have the same length.
    We go on to give an improved analysis of the encrypted CBC MAC, where there is
    no restriction on queried messages. Letting m be the block length of the longest
    query, our bounds are about mq2/2n for the basic CBC MAC and mo(1)q2/2n for the
    encrypted CBC MAC, improving prior bounds of m2q2/2n. The new bounds translate
    into improved guarantees on the probability of forging these MACs.
acknowledgement: Pietrzak was supported by the Swiss National Science Foundation,
  project No. 200020-103847/1.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Mihir
  full_name: Bellare, Mihir
  last_name: Bellare
- 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: Phillip
  full_name: Rogaway, Phillip
  last_name: Rogaway
citation:
  ama: 'Bellare M, Pietrzak KZ, Rogaway P. Improved security analyses for CBC MACs.
    In: <i>25th Annual International Cryptology Conference</i>. Vol 3621. Springer
    Nature; 2005:527-545. doi:<a href="https://doi.org/10.1007/11535218_32">10.1007/11535218_32</a>'
  apa: 'Bellare, M., Pietrzak, K. Z., &#38; Rogaway, P. (2005). Improved security
    analyses for CBC MACs. In <i>25th Annual International Cryptology Conference</i>
    (Vol. 3621, pp. 527–545). Santa Barbara, CA, United States: Springer Nature. <a
    href="https://doi.org/10.1007/11535218_32">https://doi.org/10.1007/11535218_32</a>'
  chicago: Bellare, Mihir, Krzysztof Z Pietrzak, and Phillip Rogaway. “Improved Security
    Analyses for CBC MACs.” In <i>25th Annual International Cryptology Conference</i>,
    3621:527–45. Springer Nature, 2005. <a href="https://doi.org/10.1007/11535218_32">https://doi.org/10.1007/11535218_32</a>.
  ieee: M. Bellare, K. Z. Pietrzak, and P. Rogaway, “Improved security analyses for
    CBC MACs,” in <i>25th Annual International Cryptology Conference</i>, Santa Barbara,
    CA, United States, 2005, vol. 3621, pp. 527–545.
  ista: 'Bellare M, Pietrzak KZ, Rogaway P. 2005. Improved security analyses for CBC
    MACs. 25th Annual International Cryptology Conference. CRYPTO: International Cryptology
    Conference, LNCS, vol. 3621, 527–545.'
  mla: Bellare, Mihir, et al. “Improved Security Analyses for CBC MACs.” <i>25th Annual
    International Cryptology Conference</i>, vol. 3621, Springer Nature, 2005, pp.
    527–45, doi:<a href="https://doi.org/10.1007/11535218_32">10.1007/11535218_32</a>.
  short: M. Bellare, K.Z. Pietrzak, P. Rogaway, in:, 25th Annual International Cryptology
    Conference, Springer Nature, 2005, pp. 527–545.
conference:
  end_date: 2005-08-18
  location: Santa Barbara, CA, United States
  name: 'CRYPTO: International Cryptology Conference'
  start_date: 2005-08-14
date_created: 2018-12-11T12:02:02Z
date_published: 2005-09-12T00:00:00Z
date_updated: 2026-07-02T07:55:53Z
day: '12'
doi: 10.1007/11535218_32
extern: '1'
fulldoi: https://doi.org/10.1007/11535218_32
intvolume: '      3621'
language:
- iso: eng
month: '09'
oa_version: None
page: 527 - 545
publication: 25th Annual International Cryptology Conference
publication_identifier:
  eisbn:
  - '9783540318705'
  isbn:
  - '9783540281146'
publication_status: published
publisher: Springer Nature
publist_id: '3469'
status: public
title: Improved security analyses for CBC MACs
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 3621
year: '2005'
...