Paper 2009/550

How to Construct Cryptosystems and Hash Functions in Weakened Random Oracle Models

Yusuke Naito, Lei Wang, and Kazuo Ohta

Abstract

In this paper, we discuss how to construct secure cryptosystems and secure hash functions in weakened random oracle models. ~~~~The weakened random oracle model ($\wrom$), which was introduced by Numayama et al. at PKC 2008, is a random oracle with several weaknesses. Though the security of cryptosystems in the random oracle model, $\rom$, has been discussed sufficiently, the same is not true for $\wrom$. A few cryptosystems have been proven secure in $\wrom$. In this paper, we will propose a new conversion that can convert \emph{any} cryptosystem secure in $\rom$ to a new cryptosystem that is secure in the first preimage tractable random oracle model $\fptrom$ \emph{without re-proof}. $\fptrom$ is $\rom$ without preimage resistance and so is the weakest of the $\wrom$ models. Since there are many secure cryptosystems in $\rom$, our conversion can yield many cryptosystems secure in $\fptrom$. ~~~~The fixed input length weakened random oracle model, $\filwrom$, introduced by Liskov at SAC 2006, reflects the known weakness of compression functions. We will propose new hash functions that are indifferentiable from $\ro$ when the underlying compression function is modeled by a two-way partially-specified preimage-tractable fixed input length random oracle model ($\wfilrom$). $\wfilrom$ is $\filrom$ without two types of preimage resistance and is the weakest of the $\filwrom$ models. The proposed hash functions are more efficient than the existing hash functions which are indifferentiable from $\ro$ when the underlying compression function is modeled by $\wfilrom$.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Unknown where it was published
Keywords
Random oracle modelhash functionsindifferentiability
Contact author(s)
tolucky tigers @ gmail com
History
2009-11-16: received
Short URL
https://ia.cr/2009/550
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2009/550,
      author = {Yusuke Naito and Lei Wang and Kazuo Ohta},
      title = {How to Construct Cryptosystems and Hash Functions in Weakened Random Oracle Models},
      howpublished = {Cryptology ePrint Archive, Paper 2009/550},
      year = {2009},
      note = {\url{https://eprint.iacr.org/2009/550}},
      url = {https://eprint.iacr.org/2009/550}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.