Non-adaptive programmability of random oracle

Rishiraj Bhattacharyya, Pratyay Mukherjee

Research output: Contribution to journalArticlepeer-review

4 Citations (Scopus)

Abstract

Random Oracles serve as an important heuristic for proving security of many popular and important cryptographic primitives. But, at the same time they are criticized due to the impossibility of practical instantiation. Programmability is one of the most important features behind the power of Random Oracles. Unfortunately, in the standard hash functions, the feature of programmability is limited. In recent years, there have been endeavors to restrict programmability of random oracles. However, we observe that the existing models allow adaptive programming, that is, the reduction can program the random oracle adaptively in the online phase of the security game depending on the query received from the adversary, and thus are quite far from the standard model.In this paper, we introduce a new feature called non-adaptive programmability of random oracles, where the reduction can program the random oracle only in the pre-processing phase. In particular, it might non-adaptively program the RO by setting a regular function as a post-processor on the oracle output. We call this new model Non-Adaptively-Programmable Random Oracle (NAPRO) and we show that this model is actually equivalent to so-called Non-Programmable Random Oracle (NPRO) introduced by Fischlin et al. [8], hence too restrictive.However, we also propose a slightly stronger model, called Weak-Non-Adaptively-Programmable Random Oracle (WNAPRO), where in addition to non-adaptive programming, the reduction is allowed to adaptively extract some "auxiliary information" from the RO and this "auxiliary information" interestingly plays crucial role in the security proof allowing several important RO proofs to go through! In particular we prove the following results in WNAPRO model.1.RSA-Full-Domain Hash signature scheme (RSA-FDH), and Boneh-Franklin ID-based encryption scheme (BF-IDE) are secure in the WNAPRO model. This is in sharp contrast to strong blackbox proofs of FDH schemes, where full programmability seems to be necessary.2.Shoup's Trapdoor-permutation based Key-encapsulation Mechanism (TDP-KEM) cannot be proven secure via blackbox reduction from ideal trapdoor-permutations in the WNAPRO model.

Original languageEnglish
Pages (from-to)97-114
Number of pages18
JournalTheoretical Computer Science
Volume592
DOIs
Publication statusPublished - 9 Aug 2015
Externally publishedYes

Bibliographical note

Funding Information:
We thank Ivan Dåmgard and Vipul Goyal for useful discussions at the beginning of this work. Part of this work was done when both authors were associated with the Centre of Excellence in Cryptology of Indian Statistical Institute, Kolkata, and were supported by Ministry of Defense of Government of India. Rishiraj was a member of ARIC team of ENS-Lyon, France when the results were finalized and submitted.

Publisher Copyright:
© 2015 Elsevier B.V.

Keywords

  • Programmability
  • Random oracle
  • RSA-FDH
  • TDP-KEM

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

Dive into the research topics of 'Non-adaptive programmability of random oracle'. Together they form a unique fingerprint.

Cite this