A method for time stamping a digital document is disclosed. The document originator creates a time stamp receipt by combining the document or other identifying data and a digital time indication. The time stamp receipt is submitted to a time stamping authority having a trusted clock. The time stamping authority optionally validates the time stamp receipt and then computes the age of the time stamp receipt. The time stamping authority creates an aged time stamp receipt by combining the identifying data and time indication contained in the submitted time stamp receipt with the computed age of the time stamp receipt. The time stamping authority cryptographically binds the time information and identifying data in the aged time stamp receipt, e.g., by signing the combination of the identifying data, time indication, and computed age with a private signature generation key.