A digital signature based on a conventional encryption function, such as DES, is described. This system is as secure as the underlying encryption function and does not rely on the difficulty of factoring or the computational costs of modular arithmetic. The signature system can sign an unlimited number of messages, with signature size increasing logarithmically with the number of messages. Signature size typically ranges from a few hundred bytes to a few kilobytes, and generating a signature may require a few hundred to a few thousand computations of the underlying encryption function. The system uses one-time signatures, which are based on one-way functions. A one-way function is easy to compute but difficult to invert. One-way functions can be based on conventional encryption functions by encrypting a constant with a key. One-way hash functions, which accept large inputs and produce small outputs, can also be based on repeated applications of conventional encryption functions. However, some approaches to one-way hash functions are vulnerable to 'square root' attacks. The system allows signing of one-bit messages by using a one-time signature. For multiple-bit messages, the Lamport-Diffie method is used, which requires 2n x's and 2n y's for an n-bit message. Merkle improved this method by reducing the signature size by almost two-fold. Winternitz further improved the system by reducing the signature size by several folds, allowing the signing of multiple messages with fewer computations. The system can be generalized to an infinite tree of one-time signatures. Each node in the tree performs three functions: authenticating the left and right sub-nodes and signing a message. The root node is authenticated by placing it in the public file. Each node has three signatures: a left signature, a right signature, and a message signature. The system uses a three-dimensional array of x's and y's to store the necessary data. The system allows signing of arbitrary messages with a small memory footprint and efficient computation. However, signing many messages requires a large public file. The system can be extended to a K-ary tree, which reduces the number of signatures needed but increases the computational complexity. The system is efficient and can be used in low-cost applications such as smart cards. The system is based on a conventional encryption function and is secure, with the security not relying on the difficulty of factoring.A digital signature based on a conventional encryption function, such as DES, is described. This system is as secure as the underlying encryption function and does not rely on the difficulty of factoring or the computational costs of modular arithmetic. The signature system can sign an unlimited number of messages, with signature size increasing logarithmically with the number of messages. Signature size typically ranges from a few hundred bytes to a few kilobytes, and generating a signature may require a few hundred to a few thousand computations of the underlying encryption function. The system uses one-time signatures, which are based on one-way functions. A one-way function is easy to compute but difficult to invert. One-way functions can be based on conventional encryption functions by encrypting a constant with a key. One-way hash functions, which accept large inputs and produce small outputs, can also be based on repeated applications of conventional encryption functions. However, some approaches to one-way hash functions are vulnerable to 'square root' attacks. The system allows signing of one-bit messages by using a one-time signature. For multiple-bit messages, the Lamport-Diffie method is used, which requires 2n x's and 2n y's for an n-bit message. Merkle improved this method by reducing the signature size by almost two-fold. Winternitz further improved the system by reducing the signature size by several folds, allowing the signing of multiple messages with fewer computations. The system can be generalized to an infinite tree of one-time signatures. Each node in the tree performs three functions: authenticating the left and right sub-nodes and signing a message. The root node is authenticated by placing it in the public file. Each node has three signatures: a left signature, a right signature, and a message signature. The system uses a three-dimensional array of x's and y's to store the necessary data. The system allows signing of arbitrary messages with a small memory footprint and efficient computation. However, signing many messages requires a large public file. The system can be extended to a K-ary tree, which reduces the number of signatures needed but increases the computational complexity. The system is efficient and can be used in low-cost applications such as smart cards. The system is based on a conventional encryption function and is secure, with the security not relying on the difficulty of factoring.