A time stamping protocol has two stages referred to as the ticketing stage and the certification stage. During the ticketing stage, the document or other identifying data is sent to the TSA. The TSA generates a “ticket” based on the document or other identifying data and a time indication derived from a trusted clock. The ticket, which serves as an unsigned time stamp receipt, is transmitted back to the document originator. During the certification stage, the holder of the ticket requests a certified time stamp receipt by presenting the ticket to the TSA. The TSA verifies the ticket and generates a signed time stamp receipt, called the ticket stub, which is then transmitted back to the document originator. The ticket stub serves as a “universal time-stamp” that the holder of the ticket stub can use to prove the date of the document.