Patent ID: 7404080

Claim:
A method for data authentication using one or more output values of a one-way chain in a processing device comprising a processor coupled to a memory, the one-way chain having at least one starting point and at least one endpoint, the method comprising the steps of: computing in the processor a given one of the output values at a current position in the one-way chain utilizing a first helper value previously stored in the memory for another position in the one-way chain between the current position and the endpoint of the chain; generating an authentication code using a key based on the given output value; sending the authentication code to a receiving party; sending the key to the receiving party for use by the receiving party in verifying the authentication code; and computing in the processor at least a second helper value for a new position in the chain between the current position and the endpoint of the chain, the second helper value being stored in the memory and utilizable to facilitate subsequent computation of another one of the output values in the processor; wherein a storage-computation product associated with generation of the output values of the one-way chain has a complexity O((log s) 2 ) where s denotes the length of the chain.