Ralph C. Merkle presents a practical digital signature system based on conventional encryption functions, which are already certified. This system avoids the long certification delays required for untested systems. The system uses "tree signatures," which are pre-certified and generate signatures of 1 to 3 kilobytes. It requires a few thousand applications of the underlying encryption function per signature and only a few kilobytes of memory. The system is efficient, with a signature generation time of about 20 milliseconds if the encryption function takes 10 microseconds per block. The paper discusses one-way functions and their role in authentication. It describes the Lamport-Diffie one-time signature, which is secure but has performance drawbacks. An improved version of this signature is presented, along with the Winternitz one-time signature, which reduces the size of signed messages by a factor of 4 to 8. The paper also introduces tree authentication, which allows for efficient authentication of individual elements in a set without storing all elements. This method reduces storage requirements and enables quick verification of digital signatures. The paper concludes that digital signature systems not requiring public key cryptosystems are possible and can be easier to certify. The described system has modest space and time requirements and a signature size of 1 to 3 kilobytes, making it practical for implementation.Ralph C. Merkle presents a practical digital signature system based on conventional encryption functions, which are already certified. This system avoids the long certification delays required for untested systems. The system uses "tree signatures," which are pre-certified and generate signatures of 1 to 3 kilobytes. It requires a few thousand applications of the underlying encryption function per signature and only a few kilobytes of memory. The system is efficient, with a signature generation time of about 20 milliseconds if the encryption function takes 10 microseconds per block. The paper discusses one-way functions and their role in authentication. It describes the Lamport-Diffie one-time signature, which is secure but has performance drawbacks. An improved version of this signature is presented, along with the Winternitz one-time signature, which reduces the size of signed messages by a factor of 4 to 8. The paper also introduces tree authentication, which allows for efficient authentication of individual elements in a set without storing all elements. This method reduces storage requirements and enables quick verification of digital signatures. The paper concludes that digital signature systems not requiring public key cryptosystems are possible and can be easier to certify. The described system has modest space and time requirements and a signature size of 1 to 3 kilobytes, making it practical for implementation.