Granboulan proposed the signature scheme
in the ideal cipher model named OPSSR
that achieves the lower bound for message expansion.
In this paper, we propose a scheme
which can give the security
equivalent to that of OPSSR
in the random permutation model
that is weaker than the ideal cipher model.
We also show exact security proof.
We extend our scheme to the multi key setting.
By the results of this paper,
we partially solve the open problems posed by Granboulan.