A time-stamping protocol for time-stamping digital documents uses a time-based signature key. A document or other identifying data is sent to a time stamping authority TSA. The TSA has a time-based signature key that the TSA uses to sign time stamp receipts. The signature key is associated with a fixed time reference that is stored in a public key certificate also containing the public verification key. Upon receiving the document, the TSA creates a time stamp receipt by computing a time difference between the time reference associated with the signature key and the time the document was received. The time difference is appended to the document to create a time stamp receipt and the receipt is then signed by the TSA and transmitted to the requestor.