International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Paper: How to Prove the Security of Practical Cryptosystems with Merkle-Damg{\aa}rd Hashing by Adopting Indifferentiability

Authors:
Yusuke Naito
Kazuki Yoneyama
Lei Wang
Kazuo Ohta
Download:
URL: http://eprint.iacr.org/2009/040
Search ePrint
Search Google
Abstract: In this paper, we show that major cryptosystems such as FDH, OAEP, and RSA-KEM are secure under a hash function $MD^h$ with Merkle-Damg{\aa}rd (MD) construction that uses a random oracle compression function $h$. First, we propose two new ideal primitives called Traceable Random Oracle ($\mathcal{TRO}$) and Extension Attack Simulatable Random Oracle ($\mathcal{ERO}$) which are weaker than a random oracle ($\mathcal{RO}$). Second, we show that $MD^h$ is indifferentiable from $\mathcal{LRO}$, $\mathcal{TRO}$ and $\mathcal{ERO}$, where $\mathcal{LRO}$ is Leaky Random Oracle proposed by Yoneyama et al. This result means that if a cryptosystem is secure in these models, then the cryptosystem is secure under $MD^h$ following the indifferentiability theory proposed by Maurer et al. Finally, we prove that OAEP is secure in the $\mathcal{TRO}$ model and RSA-KEM is secure in the $\mathcal{ERO}$ model. Since it is also known that FDH is secure in the $\mathcal{LRO}$ model, as a result, major cryptosystems, FDH, OAEP and RSA-KEM, are secure under $MD^h$, though $MD^h$ is not indifferentiable from $\mathcal{RO}$.
BibTeX
@misc{eprint-2009-18188,
  title={How to Prove the Security of Practical Cryptosystems with Merkle-Damg{\aa}rd Hashing by Adopting Indifferentiability},
  booktitle={IACR Eprint archive},
  keywords={},
  url={http://eprint.iacr.org/2009/040},
  note={ tolucky.tigers@gmail.com 14265 received 21 Jan 2009},
  author={Yusuke Naito and Kazuki Yoneyama and Lei Wang and Kazuo Ohta},
  year=2009
}