You are looking at a specific version 20090125:052826 of this paper. See the latest version.

Paper 2009/040

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

Yusuke Naito and Kazuki Yoneyama and 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
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.