Paper 2011/339

Careful with Composition: Limitations of Indifferentiability and Universal Composability

Thomas Ristenpart, Hovav Shacham, and Thomas Shrimpton


We exhibit a hash-based storage auditing scheme which is provably secure in the random-oracle model (ROM), but easily broken when one instead uses typical indifferentiable hash constructions. This contradicts the widely accepted belief that the indifferentiability composition theorem applies to any cryptosystem. We characterize the uncovered limitation of the indifferentiability framework by show- ing that the formalizations used thus far implicitly exclude security notions captured by experiments that have multiple, disjoint adversarial stages. Examples include deterministic public-key encryption (PKE), password-based cryptography, hash function nonmalleability, key-dependent message security, and more. We formalize a stronger notion, reset indifferentiability, that enables an indifferentiability- style composition theorem covering such multi-stage security notions, but then show that practical hash constructions cannot be reset indifferentiable. We discuss how these limitations also affect the universal composability framework. We finish by showing the chosen-distribution attack security (which requires a multi-stage game) of some important public-key encryption schemes built using a hash construction paradigm introduced by Dodis, Ristenpart, and Shrimpton.

Available format(s)
Publication info
Published elsewhere. A preliminary version of this paper was published under the title "Careful with Composition: Limitations of the Indifferentiability Framework" at Eurocrypt 2011
Contact author(s)
rist @ cs wisc edu
2011-06-26: received
Short URL
Creative Commons Attribution


      author = {Thomas Ristenpart and Hovav Shacham and Thomas Shrimpton},
      title = {Careful with Composition: Limitations of Indifferentiability and Universal Composability},
      howpublished = {Cryptology ePrint Archive, Paper 2011/339},
      year = {2011},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.