Cryptology ePrint Archive: Report 2009/040

How to Prove the Security of Practical Cryptosystems with Merkle-Damg{\aa}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{\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}$.

Category / Keywords:

Date: received 21 Jan 2009

Contact author: tolucky tigers at gmail com

Available formats: PDF | BibTeX Citation

Version: 20090125:052826 (All versions of this report)

Discussion forum: Show discussion | Start new discussion