Hash chains with diminishing ranges for sensors

Sensors and other small devices that periodically transmit relatively small packets of information motivate the study of hash chains with small domains and ranges. Hash chain based protocols work using deferred disclosure and it is often assumed their hash functions are one-way, hence essentially unbreakable. However small domains and ranges make hash functions much weaker. If a deterministic hash function’s domain and range are the same and both are very small, then it may not be possible for the hash function to be one-way. In fact, hash chains will size-constrained domains and ranges are likely to cycle quickly. This paper proposes a solution to this challenge - the general hash chain construction. A general hash chain uses several subsequent hash elements at once as input to produce each output hash element. General hash chains have the following properties: (1) repeated hash elements do not necessarily indicate cycles in the hash chain, (2) subsequent elements of these hash chains do not have exponentially diminishing ranges. This makes general hash chains quite strong, given the size constraints on their domains and ranges.