Paper 2009/040

How to Prove the Security of Practical Cryptosystems with Merkle-Damgård Hashing by Adopting Indifferentiability

Yusuke Naito, Kazuki Yoneyama, Lei Wang, and Kazuo Ohta

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å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}$.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Unknown where it was published
Contact author(s)
tolucky tigers @ gmail com
History
2009-01-25: received
Short URL
https://ia.cr/2009/040
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2009/040,
      author = {Yusuke Naito and Kazuki Yoneyama and Lei Wang and Kazuo Ohta},
      title = {How to Prove the Security of Practical Cryptosystems with Merkle-Damgård Hashing by Adopting Indifferentiability},
      howpublished = {Cryptology {ePrint} Archive, Paper 2009/040},
      year = {2009},
      url = {https://eprint.iacr.org/2009/040}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.