Paper 2003/150

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

Ran Canetti, Oded Goldreich, and 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.

Metadata
Available format(s)
PDF PS
Category
Foundations
Publication info
Published elsewhere. Unknown where it was published
Keywords
Digital signaturesRandom-oracle model
Contact author(s)
shaih @ watson ibm com
History
2003-07-31: received
Short URL
https://ia.cr/2003/150
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2003/150,
      author = {Ran Canetti and Oded Goldreich and Shai Halevi},
      title = {On the random-oracle methodology as applied to length-restricted signature schemes},
      howpublished = {Cryptology ePrint Archive, Paper 2003/150},
      year = {2003},
      note = {\url{https://eprint.iacr.org/2003/150}},
      url = {https://eprint.iacr.org/2003/150}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.