<abstract xmlns="http://www.w3.org/1999/xhtml"><p> Many cryptographic systems which involve hash functions have proof of their security in a so called random oracle model. Behavior of hash functions used in such cryptographic systems should be as close as possible to the behavior of a random function. There are several properties of hash functions dealing with a random behavior. A hash function is pseudo-random oracle if it is indifferentiable from a random oracle. However, it is well known that hash functions based on the popular Merkle-Damg˚ard domain extension transform do not satisfy the pseudo-random oracle property. On the other hand no attack is known for many concrete applications utilizing Merkle-Damg˚ard hash functions. Hence, a weakened notion called public-use pseudo random oracle was introduced. The property can be met by the Merkle-Damg˚ard construction and is sufficient for several important applications. A hash function is public use pseudo-random oracle if it is indifferentiable from a random oracle with public messages (i.e., all messages hashed so far are available to all parties). This is the case of most hash based signature schemes.</p><p>In this paper we analyze relationship between the property pseudo-random oracle and its variant public image pseudo-random oracle. Roughly, a hash function is public image pseudo-random oracle if it is indifferentiable from a random oracle with public images (i.e., all images of messages hashed so far are available to all parties, messages are kept secret). We prove that the properties are equivalent.</p></abstract>

Many cryptographic systems which involve hash functions have proof of their security in a so called random oracle model. Behavior of hash functions used in such cryptographic systems should be as close as possible to the behavior of a random function. There are several properties of hash functions dealing with a random behavior. A hash function is pseudo-random oracle if it is indifferentiable from a random oracle. However, it is well known that hash functions based on the popular Merkle-Damg˚ard domain extension transform do not satisfy the pseudo-random oracle property. On the other hand no attack is known for many concrete applications utilizing Merkle-Damg˚ard hash functions. Hence, a weakened notion called public-use pseudo random oracle was introduced. The property can be met by the Merkle-Damg˚ard construction and is sufficient for several important applications. A hash function is public use pseudo-random oracle if it is indifferentiable from a random oracle with public messages (i.e., all messages hashed so far are available to all parties). This is the case of most hash based signature schemes.In this paper we analyze relationship between the property pseudo-random oracle and its variant public image pseudo-random oracle. Roughly, a hash function is public image pseudo-random oracle if it is indifferentiable from a random oracle with public images (i.e., all images of messages hashed so far are available to all parties, messages are kept secret). We prove that the properties are equivalent.

On Pseudo-Random Oracles

Department of Computer Science, Faculty of Mathematics, Physics and Informatics, Comenius University, Mlynsk´a dolina, SK–842-48 Bratislava, SLOVAKI

Tatra Mountains Mathematical Publications

{"article-title":"On Pseudo-Random Oracles"}

Many cryptographic systems which involve hash functions have proof of their security in a so called random oracle model. Behavior of hash functions used in...

On Pseudo-Random Oracles

Published Online: Feb 01, 2013

Page range: 155 - 187

DOI: https://doi.org/10.2478/v10127-012-0045-5

Keywords
random oracle, cryptographic hash function, pseudo-random oracle

This content is open access.

On Pseudo-Random Oracles

Published Online: Feb 01, 2013

Page range: 155 - 187

DOI: https://doi.org/10.2478/v10127-012-0045-5

Keywordsrandom oracle, cryptographic hash function, pseudo-random oracle

This content is open access.

Keywords
random oracle, cryptographic hash function, pseudo-random oracle