A Note on the Random Oracle Methodology

Mototsugu NISHIOKA  Naohisa KOMATSU  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E91-A    No.2    pp.650-663
Publication Date: 2008/02/01
Online ISSN: 1745-1337
DOI: 10.1093/ietfec/e91-a.2.650
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Cryptography and Information Security
random oracle model,  standard computational model,  signature scheme,  encryption scheme,  

Full Text: PDF>>
Buy this Article

Canetti et al. [5] showed that there exist signature and encryption schemes that are secure in the random oracle (RO) model, but for which any implementation of the RO (by a single function or a function ensemble) results in insecure schemes. Their result greatly motivates the design of cryptographic schemes that are secure in the standard computational model. This paper gives some new results on the RO methodology. First, we give the necessary and sufficient condition for the existence of a signature scheme that is secure in the RO model but where, for any implementation of the RO, the resulting scheme is insecure. Next, we show that this condition induces a signature scheme that is insecure in the RO model, but that there is an implementation of the RO that makes the scheme secure.