This paper introduces a practical digital signature system based on conventional encryption functions, which can be implemented quickly without the lengthy certification process required for untested systems. The system is "pre-certified" due to the security of the underlying encryption function. The key contributions include: 1. **One-Way Functions**: The paper discusses the concept of one-way functions, which are easy to compute but difficult to invert. These functions are crucial for authentication and can be parameterized to improve security. 2. **Lamport-Diffie One-Time Signature**: This signature method uses a one-way function to sign a single bit of information. It involves generating a vector \( Y \) from a set of one-way function outputs, which can be used to sign multiple messages by revealing or concealing specific bits of \( Y \). 3. **Improved One-Time Signature**: An improvement to the Lamport-Diffie method reduces the size of signed messages by almost half by appending a count of zero bits to the message before signing. 4. **Winternitz Improvement**: This further reduces the size of the signed message by a factor of 4 to 8 by signing multiple bits with a single one-way function output, making it suitable for signing larger messages. 5. **Tree Authentication**: A protocol is described to authenticate any user's \( Y_i \) without requiring a large storage of authentication paths. This is achieved through a "divide and conquer" technique, where the authentication path for a leaf node can be quickly regenerated using previously computed values. 6. **Path Regeneration Algorithm**: An efficient algorithm is presented to sequentially generate authentication paths for multiple users with modest time and space requirements. The algorithm uses incremental computation to minimize peak memory usage and computational load. The paper concludes that such a digital signature system is not only possible but also easier to certify, with modest space and time requirements and a signature size of 1 to 3 kilobytes. The method can be implemented quickly without the delays associated with certification.This paper introduces a practical digital signature system based on conventional encryption functions, which can be implemented quickly without the lengthy certification process required for untested systems. The system is "pre-certified" due to the security of the underlying encryption function. The key contributions include: 1. **One-Way Functions**: The paper discusses the concept of one-way functions, which are easy to compute but difficult to invert. These functions are crucial for authentication and can be parameterized to improve security. 2. **Lamport-Diffie One-Time Signature**: This signature method uses a one-way function to sign a single bit of information. It involves generating a vector \( Y \) from a set of one-way function outputs, which can be used to sign multiple messages by revealing or concealing specific bits of \( Y \). 3. **Improved One-Time Signature**: An improvement to the Lamport-Diffie method reduces the size of signed messages by almost half by appending a count of zero bits to the message before signing. 4. **Winternitz Improvement**: This further reduces the size of the signed message by a factor of 4 to 8 by signing multiple bits with a single one-way function output, making it suitable for signing larger messages. 5. **Tree Authentication**: A protocol is described to authenticate any user's \( Y_i \) without requiring a large storage of authentication paths. This is achieved through a "divide and conquer" technique, where the authentication path for a leaf node can be quickly regenerated using previously computed values. 6. **Path Regeneration Algorithm**: An efficient algorithm is presented to sequentially generate authentication paths for multiple users with modest time and space requirements. The algorithm uses incremental computation to minimize peak memory usage and computational load. The paper concludes that such a digital signature system is not only possible but also easier to certify, with modest space and time requirements and a signature size of 1 to 3 kilobytes. The method can be implemented quickly without the delays associated with certification.