International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Davies-Meyer Merkle-Damg{\aa}rd Revisited:\\Variants of Indifferentiability and Random Oracles

Authors:
Yusuke Naito
Kazuki Yoneyama
Lei Wang
Kazuo Ohta
Download:
URL: http://eprint.iacr.org/2009/075
Search ePrint
Search Google
Abstract: In this paper, we succeed in analyzing practical cryptosystems that employ the Davies-Meyer Merkle-Damg{\aa}rd hash function $\mddm^E$ with ideal cipher $E$ by using two approaches: {\it indifferentiability from variants of random oracles} and {\it indifferentiability from a random oracle $\ro$ with conditions}. We show that RSA-KEM with $\mddm^E$ is secure by using the former approach and that OAEP with $\mddm^E$ is secure by using the latter approach. The public-use random oracle ($\pubro$) model is a variant of random oracle (proposed by Dodis et al. and Yoneyama et al.). We also show that cryptosystems secure under $\pubro$ model, such as FDH, Fiat-Shamir, PSS and so on, are also secure under $\mddm^E$ by using the former approach. Note that Dodis et al. failed in the paper of EUROCRYPT 2009 in analyzing the security of cryptosystems with $\mddm^E$, because they started by analyzing the underlying compression function, while our first approach starts by analyzing the hash function.
BibTeX
@misc{eprint-2009-18207,
  title={Davies-Meyer Merkle-Damg{\aa}rd Revisited:\\Variants of Indifferentiability and Random Oracles},
  booktitle={IACR Eprint archive},
  keywords={Merkle-Damg{\aa}rd construction, Davis-Mayer mode, indifferentiability, random oracles, secure cryptosystems in the random oracle model.},
  url={http://eprint.iacr.org/2009/075},
  note={ tolucky.tigers@gmail.com 14288 received 13 Feb 2009, last revised 13 Feb 2009},
  author={Yusuke Naito and Kazuki Yoneyama and Lei Wang and Kazuo Ohta},
  year=2009
}