[{"date_created":"2018-12-11T12:02:03Z","date_published":"2005-09-12T00:00:00Z","extern":"1","year":"2005","status":"public","intvolume":"      3621","type":"conference","publist_id":"3468","conference":{"start_date":"2005-08-14","name":"CRYPTO: International Cryptology Conference","end_date":"2005-08-18","location":"Santa Barbara, CA, United States"},"fulldoi":"https://doi.org/10.1007/11535218_4","publication_status":"published","publication":"25th Annual International Cryptology Conference","volume":3621,"OA_type":"gold","author":[{"full_name":"Pietrzak, Krzysztof Z","first_name":"Krzysztof Z","orcid":"0000-0002-9139-1654","last_name":"Pietrzak","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87"}],"day":"12","OA_place":"publisher","page":"55 - 65","das_tickbox":"1","title":"Composition does not imply adaptive security","date_updated":"2026-07-02T07:47:38Z","publisher":"Springer Nature","_id":"3213","acknowledgement":"Supported by the Swiss National Science Foundation, project No. 200020-103847/1.","alternative_title":["LNCS"],"article_processing_charge":"No","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."}],"publication_identifier":{"isbn":["9783540281146"],"eisbn":["9783540318705"]},"citation":{"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>.","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>.","short":"K.Z. Pietrzak, in:, 25th Annual International Cryptology Conference, Springer Nature, 2005, pp. 55–65.","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>","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."},"doi":"10.1007/11535218_4","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","month":"09","language":[{"iso":"eng"}],"oa_version":"None"},{"status":"public","extern":"1","year":"2005","intvolume":"      3621","type":"conference","date_created":"2018-12-11T12:02:03Z","date_published":"2005-09-12T00:00:00Z","fulldoi":"https://doi.org/10.1007/11535218_27","publication_status":"published","publication":"25th Annual International Cryptology Conference","conference":{"location":" Santa Barbara, CA, United States","name":"CRYPTO: International Cryptology Conference","end_date":"2005-08-18","start_date":"2005-08-14"},"publist_id":"3470","OA_type":"closed access","volume":3621,"page":"449 - 466","das_tickbox":"1","author":[{"last_name":"Dodis","full_name":"Dodis, Yevgeniy","first_name":"Yevgeniy"},{"last_name":"Oliveira","first_name":"Roberto","full_name":"Oliveira, Roberto"},{"last_name":"Pietrzak","orcid":"0000-0002-9139-1654","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","full_name":"Pietrzak, Krzysztof Z","first_name":"Krzysztof Z"}],"day":"12","date_updated":"2026-07-02T08:05:18Z","_id":"3212","publisher":"Springer Nature","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","title":"On the generic insecurity of the full domain hash","article_processing_charge":"No","publication_identifier":{"eisbn":["9783540318705"],"isbn":["9783540281146"]},"abstract":[{"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.","lang":"eng"}],"doi":"10.1007/11535218_27","citation":{"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>","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>.","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>","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>.","short":"Y. Dodis, R. Oliveira, K.Z. Pietrzak, in:, 25th Annual International Cryptology Conference, Springer Nature, 2005, 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.","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."},"alternative_title":["LNCS"],"oa_version":"None","month":"09","language":[{"iso":"eng"}],"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345"},{"title":"Improved security analyses for CBC MACs","date_updated":"2026-07-02T07:55:53Z","_id":"3211","publisher":"Springer Nature","acknowledgement":"Pietrzak was supported by the Swiss National Science Foundation, project No. 200020-103847/1.","alternative_title":["LNCS"],"article_processing_charge":"No","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."}],"publication_identifier":{"isbn":["9783540281146"],"eisbn":["9783540318705"]},"doi":"10.1007/11535218_32","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>","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>.","short":"M. Bellare, K.Z. Pietrzak, P. Rogaway, in:, 25th Annual International Cryptology Conference, Springer Nature, 2005, 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.","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.","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>","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>."},"language":[{"iso":"eng"}],"month":"09","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","oa_version":"None","date_created":"2018-12-11T12:02:02Z","date_published":"2005-09-12T00:00:00Z","status":"public","year":"2005","extern":"1","intvolume":"      3621","type":"conference","conference":{"start_date":"2005-08-14","name":"CRYPTO: International Cryptology Conference","end_date":"2005-08-18","location":"Santa Barbara, CA, United States"},"publist_id":"3469","fulldoi":"https://doi.org/10.1007/11535218_32","publication_status":"published","publication":"25th Annual International Cryptology Conference","volume":3621,"OA_type":"gold","author":[{"last_name":"Bellare","full_name":"Bellare, Mihir","first_name":"Mihir"},{"orcid":"0000-0002-9139-1654","last_name":"Pietrzak","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","full_name":"Pietrzak, Krzysztof Z","first_name":"Krzysztof Z"},{"last_name":"Rogaway","full_name":"Rogaway, Phillip","first_name":"Phillip"}],"day":"12","OA_place":"publisher","page":"527 - 545"}]