Abstract ======== We propose an unlimited-time digital signature scheme based on a one-time signature scheme and a random oracle. The random oracle maps a private key p0 to a pair of new private keys (p1,p2); the one-time signature scheme is used with p0 to sign the public keys corresponding to (p1,p2). We apply this method recursively for each bit in a message, with p0'=p1 if the bit is zero and p0'=p2 if the bit is one. The resultant chain of one-time signatures forms our scheme's the signature of the message. Our scheme has applications in long-term digital publishing. Unlike signature schemes like RSA and DSA, it does not rely on number-theoretic assumptions like the hardness of factoring or discrete logs, areas in which substantial cryptoanalytical improvements continue to be made. As long as the random oracle isn't broken, an exhaustive key search is the only way to break the scheme. Additionally, rejecting invalid signatures can be significantly faster than in RSA-like systems. On the other hand, signing is comparatively slow and signatures are very large. Introduction ============ One-time signature schemes [XXX] are based on one-way functions[#]_. Given a one-way function f, the signer generates a set of (pseudo)random numbers and and publishes f(x) for each x in the set. This is the public key. To sign a message, the signer employs a deterministic algorithm to select a subset of the random numbers, and publishes them as the signature. The signature can be verified by running the same deterministic algorithm, checking that the resultant set of numbers has been published, and comparing f(x) for each published number x against the values in the public key. .. [#] A function f is one-way if it is infeasible, for a given y, to find x so that y=f(x). Common examples are block ciphers and cryptographic hash functions. To prevent an attacker from using a subset of the published numbers to sign a different message, the deterministic algorithm is chosen so that no set in its range is a true subset of any other set in its range, or that finding such a pair of sets is infeasible. One-time signatures were originally proposed independently by [XXX] and [XXX]. Since then, numerous variations and improvements have been published [XXX]. Private keys in one-time signature schemes can generally only be used to sign a single message. If the same key were used to sign multiple messages, an attacker might be able to combine the random numbers published in each signature to find a new valid signature. However, some schemes have been recently proposed that allow a small number of messages to be signed without becoming completely insecure [BiBa, betterthanbiba]. Another way to allow n messages to be signed with the same public key is to create n different key pairs, and then compute a hash tree over the public keys. This is only practical for relatively small n. Yet another approach is to sign a new public key as the last message signed with the old key. This way, an arbitrary number of messages can be signed. However, verification time increases, and the signer still needs to keep track of which private keys have already been used in order not to compromise security. Despite the limitation to a small number of signatures per public/private key pair, one-time signatures have two distinct advantages. Firstly, one-way functions can be very fast, and operations on one-way signatures may be orders of magnitude faster than operations in schemes like DSA or RSA. Secondly, one-way functions generally do not rely on unproven number-theoretic assumptions, like the difficulty of factoring large integers [XXX]. In practice, a cryptographic hash function is used in most signature schemes anyway to map messages to a fixed-length digest, which is then signed. As cryptographic hash functions are one-way, also using them as the basis for signature avoids introducing additional cryptographic primitives into the system. In this article, we introduce a new signature scheme that can be used any number of times without keeping track of private keys that have already been used. Our scheme assumes a one-time signature scheme and a random oracle. We then examine how this scheme can be used in a digital publishing context. Our scheme XXX title ==================== The scheme presented in this section XXX We assume a one-time signature scheme which uses a (pseudo)random number as its private key. If *p* is a private key, let *pub(p)* be the public key corresponding to it. For a message m, let *sign(p,m)* be the signature of *m* with private key *p*. Let *verify(pub(p),m,s)* be true for a signature *s* if *sign(p,m)=s*. Assume the above only if *sign(p,m)* is not publicized for more than one *m*. Further, let *R* be a random oracle which deterministically maps a private key to a pair of other private keys. To generate a private/public key pair in our scheme, generate a random number *p* as the private key and use *pub(p)* as the public key. To sign a *b*-bit message *m*,