Short paper: Practically unbounded one-way chains for authentication with backward secrecy

One-way hash chains have been the preferred choice (over symmetric and asymmetric key cryptography) in security setups where efficiency mattered; despite the ephemeral confidentiality and authentication they assure. They only support forward secrecy and have limitations over the chain size (bounded). In this paper, we show how the use of chameleon functions leads to the generation of practically unbounded one-way chains with constant memory storage requirement, providing forward, and backward secrecy as well. Such a cryptographic tool appears to be a great enabler for a variety of applications that could not be efficiently realized earlier. From our experiments we observed that this new kind of one-way chain formation adds a slight computational burden, which is justifiable by the unique advantages provided under our construction. The basic unit of our construction, chameleon function, can be elegantly used to design trees or even simpler star-like constructs. © 2005 IEEE.