Paper 2012/014

Reset Indifferentiability from Weakened Random Oracle Salvages One-pass Hash Functions

Yusuke Naito, Kazuki Yoneyama, and Kazuo Ohta


Ristenpart et al. showed that the limitation of the indifferentiability theorem of Maurer et al. which does not cover all multi stage security notions but covers only single stage security notions, defined a new concept (reset indifferentiability), and proved the reset indifferentiability theorem, which is an analogy of the indifferentiability theorem covers all security notions S: if H^U is reset indifferentiable from RO, for any security notion, a cryptosystem C is at least as secure in the U model as in the RO model. Unfortunately, they also proved the impossibility of H^U being reset indifferentiable from a RO where H is a one-pass hash function such as ChopMD and Sponge constructions. In this paper, we will propose a new proof of molular approach instead of the RO methodology, Reset Indifferentiability from Weakened Random Oracle, called as the WRO methodology, in order to ensure the security of C with H^U, salvaging ChopMD and Sponge. The concrete proof procedure of the WRO methodology is as follows: 1. Define a new concept of WRO instead of RO, 2. Prove that H^U is reset indifferentiable from a WRO, (here an example of H is ChopMD and Sponge), and 3. Prove that C is secure in the WRO model. As a result we can prove that C with H^U is secure by combining the results of Steps 2, 3, and the theorem of Ristenpart et al. Moreover, for public-key encryption (as cryptosystem C) and chosen-distribution attack we will prove that C(WRO) is secure, which implies the appropriateness of the new concept of the WRO model.

Available format(s)
Publication info
Published elsewhere. Major revision. ACNS2014
indifferentiabilityreset indifferentiabilitymulti-stage security game
Contact author(s)
Naito Yusuke @ ce mitsubishielectric co jp
2014-06-04: last of 26 revisions
2012-01-14: received
See all versions
Short URL
Creative Commons Attribution


      author = {Yusuke Naito and Kazuki Yoneyama and Kazuo Ohta},
      title = {Reset Indifferentiability from Weakened Random Oracle Salvages One-pass Hash Functions},
      howpublished = {Cryptology ePrint Archive, Paper 2012/014},
      year = {2012},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.