On the random-oracle methodology as applied to length-restricted
signature schemes
by Ran Canetti, Oded Goldreich, Shai Halevi
Abstract
In earlier work,
we described a ``pathological'' example of a
signature scheme that is secure in the random-oracle model,
but for which no secure implementation exists.
For that example, however, it was crucial that
the scheme is able to sign ``long messages'' (i.e., messages whose
length is not a-priori bounded). This left open the possibility that
the Random Oracle Methodology is sound with respect to signature
schemes that sign only ``short'' messages
(i.e., messages of a-priori bounded length, smaller than the
length of the keys in use), and are ``memoryless''
(i.e., the only thing kept between different signature
generations is the initial signing-key).
In this work, we extend our negative result to address such signature schemes.
A key ingredient in our proof is a new type
of interactive proof systems, which may be of independent interest.
Versions
Back to Oded Goldreich's homepage
or to General list of Oded Goldreich's papers