On the random-oracle methodology as applied to length-restricted signature schemes

by Ran Canetti, Oded Goldreich, Shai Halevi


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.


Back to Oded Goldreich's homepage or to General list of Oded Goldreich's papers