The search functionality is under construction.

The search functionality is under construction.

Since the Merkle-Damgård hash function (denoted by MDFH) that uses a fixed input length random oracle as a compression function is not indifferentiable from a random oracle (denoted by RO) due to the extension attack, there is no guarantee for the security of cryptosystems, which are secure in the RO model, when RO is instantiated with MDHF. This fact motivates us to establish a criteria methodology for confirming cryptosystems security when RO is instantiated with MDHF. In this paper, we confirm cryptosystems security by using the following approach: 1.Find a weakened random oracle (denoted by WRO) which leaks values needed to realize the extension attack. 2.Prove that MDHF is indifferentiable from WRO. 3.Prove cryptosystems security in the WRO model. The indifferentiability framework of Maurer, Renner and Holenstein guarantees that we can securely use the cryptosystem when WRO is instantiated with MDHF. Thus we concentrate on such finding WRO. We propose Traceable Random Oracle (denoted by TRO) which leaks values enough to permit the extension attack. By using TRO, we can *easily* confirm the security of OAEP encryption scheme and variants of OAEP encryption scheme. However, there are several practical cryptosystems whose security cannot be confirmed by TRO (e.g. RSA-KEM). This is because TRO leaks values that are irrelevant to the extension attack. Therefore, we propose another WRO, Extension Attack Simulatable Random Oracle (denoted by ERO), which leaks *just* the value needed for the extension attack. Fortunately, ERO is *necessary and sufficient* to confirm the security of cryptosystems under MDHF. This means that the security of *any* cryptosystem under MDHF is *equivalent* to that under the ERO model. We prove that RSA-KEM is secure in the ERO model.

- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E94-A No.1 pp.57-70

- Publication Date
- 2011/01/01

- Publicized

- Online ISSN
- 1745-1337

- DOI
- 10.1587/transfun.E94.A.57

- Type of Manuscript
- Special Section PAPER (Special Section on Cryptography and Information Security)

- Category
- Public Key Cryptography

The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.

Copy

Yusuke NAITO, Kazuki YONEYAMA, Lei WANG, Kazuo OHTA, "Security of Cryptosystems Using Merkle-Damgård in the Random Oracle Model" in IEICE TRANSACTIONS on Fundamentals,
vol. E94-A, no. 1, pp. 57-70, January 2011, doi: 10.1587/transfun.E94.A.57.

Abstract: Since the Merkle-Damgård hash function (denoted by MDFH) that uses a fixed input length random oracle as a compression function is not indifferentiable from a random oracle (denoted by RO) due to the extension attack, there is no guarantee for the security of cryptosystems, which are secure in the RO model, when RO is instantiated with MDHF. This fact motivates us to establish a criteria methodology for confirming cryptosystems security when RO is instantiated with MDHF. In this paper, we confirm cryptosystems security by using the following approach: 1.Find a weakened random oracle (denoted by WRO) which leaks values needed to realize the extension attack. 2.Prove that MDHF is indifferentiable from WRO. 3.Prove cryptosystems security in the WRO model. The indifferentiability framework of Maurer, Renner and Holenstein guarantees that we can securely use the cryptosystem when WRO is instantiated with MDHF. Thus we concentrate on such finding WRO. We propose Traceable Random Oracle (denoted by TRO) which leaks values enough to permit the extension attack. By using TRO, we can *easily* confirm the security of OAEP encryption scheme and variants of OAEP encryption scheme. However, there are several practical cryptosystems whose security cannot be confirmed by TRO (e.g. RSA-KEM). This is because TRO leaks values that are irrelevant to the extension attack. Therefore, we propose another WRO, Extension Attack Simulatable Random Oracle (denoted by ERO), which leaks *just* the value needed for the extension attack. Fortunately, ERO is *necessary and sufficient* to confirm the security of cryptosystems under MDHF. This means that the security of *any* cryptosystem under MDHF is *equivalent* to that under the ERO model. We prove that RSA-KEM is secure in the ERO model.

URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E94.A.57/_p

Copy

@ARTICLE{e94-a_1_57,

author={Yusuke NAITO, Kazuki YONEYAMA, Lei WANG, Kazuo OHTA, },

journal={IEICE TRANSACTIONS on Fundamentals},

title={Security of Cryptosystems Using Merkle-Damgård in the Random Oracle Model},

year={2011},

volume={E94-A},

number={1},

pages={57-70},

abstract={Since the Merkle-Damgård hash function (denoted by MDFH) that uses a fixed input length random oracle as a compression function is not indifferentiable from a random oracle (denoted by RO) due to the extension attack, there is no guarantee for the security of cryptosystems, which are secure in the RO model, when RO is instantiated with MDHF. This fact motivates us to establish a criteria methodology for confirming cryptosystems security when RO is instantiated with MDHF. In this paper, we confirm cryptosystems security by using the following approach: 1.Find a weakened random oracle (denoted by WRO) which leaks values needed to realize the extension attack. 2.Prove that MDHF is indifferentiable from WRO. 3.Prove cryptosystems security in the WRO model. The indifferentiability framework of Maurer, Renner and Holenstein guarantees that we can securely use the cryptosystem when WRO is instantiated with MDHF. Thus we concentrate on such finding WRO. We propose Traceable Random Oracle (denoted by TRO) which leaks values enough to permit the extension attack. By using TRO, we can *easily* confirm the security of OAEP encryption scheme and variants of OAEP encryption scheme. However, there are several practical cryptosystems whose security cannot be confirmed by TRO (e.g. RSA-KEM). This is because TRO leaks values that are irrelevant to the extension attack. Therefore, we propose another WRO, Extension Attack Simulatable Random Oracle (denoted by ERO), which leaks *just* the value needed for the extension attack. Fortunately, ERO is *necessary and sufficient* to confirm the security of cryptosystems under MDHF. This means that the security of *any* cryptosystem under MDHF is *equivalent* to that under the ERO model. We prove that RSA-KEM is secure in the ERO model.},

keywords={},

doi={10.1587/transfun.E94.A.57},

ISSN={1745-1337},

month={January},}

Copy

TY - JOUR

TI - Security of Cryptosystems Using Merkle-Damgård in the Random Oracle Model

T2 - IEICE TRANSACTIONS on Fundamentals

SP - 57

EP - 70

AU - Yusuke NAITO

AU - Kazuki YONEYAMA

AU - Lei WANG

AU - Kazuo OHTA

PY - 2011

DO - 10.1587/transfun.E94.A.57

JO - IEICE TRANSACTIONS on Fundamentals

SN - 1745-1337

VL - E94-A

IS - 1

JA - IEICE TRANSACTIONS on Fundamentals

Y1 - January 2011

AB - Since the Merkle-Damgård hash function (denoted by MDFH) that uses a fixed input length random oracle as a compression function is not indifferentiable from a random oracle (denoted by RO) due to the extension attack, there is no guarantee for the security of cryptosystems, which are secure in the RO model, when RO is instantiated with MDHF. This fact motivates us to establish a criteria methodology for confirming cryptosystems security when RO is instantiated with MDHF. In this paper, we confirm cryptosystems security by using the following approach: 1.Find a weakened random oracle (denoted by WRO) which leaks values needed to realize the extension attack. 2.Prove that MDHF is indifferentiable from WRO. 3.Prove cryptosystems security in the WRO model. The indifferentiability framework of Maurer, Renner and Holenstein guarantees that we can securely use the cryptosystem when WRO is instantiated with MDHF. Thus we concentrate on such finding WRO. We propose Traceable Random Oracle (denoted by TRO) which leaks values enough to permit the extension attack. By using TRO, we can *easily* confirm the security of OAEP encryption scheme and variants of OAEP encryption scheme. However, there are several practical cryptosystems whose security cannot be confirmed by TRO (e.g. RSA-KEM). This is because TRO leaks values that are irrelevant to the extension attack. Therefore, we propose another WRO, Extension Attack Simulatable Random Oracle (denoted by ERO), which leaks *just* the value needed for the extension attack. Fortunately, ERO is *necessary and sufficient* to confirm the security of cryptosystems under MDHF. This means that the security of *any* cryptosystem under MDHF is *equivalent* to that under the ERO model. We prove that RSA-KEM is secure in the ERO model.

ER -