Our main result gives a way to instantiate the
random oracle with a concrete hash function in
\"full domain hash\" applications.
The term full domain hash was first proposed by Bellare and
Rogaway and referred to a signature scheme from any
trapdoor permutation that was part of their seminal work introducing
the random oracle heuristic. Over time the term full domain hash has
informally encompassed a broader range of notable cryptographic
schemes including the Boneh-Franklin IBE scheme and
Boneh-Lynn-Shacham (BLS) signatures.
All of the above described schemes required a hash function that had
to be modeled as a random oracle to prove security. Our work utilizes
recent advances in indistinguishability obfuscation to construct
specific hash functions for use in these schemes. We then prove
security of the original cryptosystems when instantiated with
our specific hash function.
Of particular interest, our work evades the impossibility result of
Dodis, Oliveira, and Pietrzak, who showed that there can
be no black-box construction of hash functions that allow Full-Domain
Hash Signatures to be based on trapdoor permutations. This indicates
that our techniques applying indistinguishability obfuscation may be
useful in the future for circumventing other such black-box