Portland Sea Dogs
The authors 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 in-differentiable hash constructions. This contradicts the widely accepted belief that the in-differentiability composition theorem applies to any cryptosystem. They characterize the uncovered limitation of the in-differentiability framework by showing 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 non-malleability, key-dependent message security, and more.