A cellular automata based HB#-like low complexity authentication technique

This paper addresses the problem of developing low-complexity authentication challenge-response protocols based on employment of pseudorandom sequences generated by cellular automata (CA). The proposed protocol is an improved variant of the recently reported HB^# protocol. Oppositely from the reported HB-protocols the proposed one is based in the following: (i) The response vector consists of the effective bits and dummy bits embedded in a pseudorandom manner: The effective bits are corrupted parity-check bits, and the dummy ones are pure random bits; (ii) The states of secret key controlled CA are employed for generation of the effective response bits and for the pseudorandom embedding of the effective and the dummy bits. The proposed protocol provides a framework for increasing the security and reducing the implementation complexity and communications overhead in comparison with the previously reported HB^# one.