A study of the random oracle model seems to be
concentrated to showing
the gap between the schemes in the random
oracle model and the schemes whose random oracles are replaced with
functions chosen at random from some function
ensembles.
We consider a different direction on the
study of the schemes in the random oracle model.
We focus on the size of the tables necessary to describe
all of the entries to be potentially queried in
the random oracle model.
We show how to reduce
the table sizes of the
schemes for encryption and signature
in the random oracle model.
In particular, we apply this idea to PSS-R
and OAEP and show the security of our schemes.