¹Department of Computer Science, Dept of Computer Science and Engg, Madras, India
²Department of Computer Science, Dept of Computer Science and Engg, Kharagpur, India

---

Abstract—In this paper, a technique to generate expander graphs using Cellular Automata (CA) has been presented. The special class of CA, known as the Two Predecessor Single Attractor Cellular Automata (TPSA CA) has been characterized. It has been shown that the expander graphs built using the TPSA-CA are promising and lead to the development of strong one-way functions. The paper proposes an efficient architecture for the one-way function and implements it on an FPGA platform. Most of the widely used key establishment algorithms employ one-way functions based on modular exponentiation that are computationally very expensive. However, the implementation of the proposed architecture shows that the TPSA based one-way algorithm can be implemented very efficiently with very less consumption of computational resources like area and clock cycles. Such a one-way function can be an ideal replacement of modular exponentiation based one-way functions and thus help to develop fast and secure key establishment protocols.

Index Terms—One Way Function, Cellular Automata, Expander Graphs, FPGA Implementations, Area-Delay Product

[PDF]

Cite: D. Mukhopadhyay, P. Joshi, D. RoyChowdhury, "VLSI Architecture of a Cellular Automata based One-Way Function," Journal of Computers vol. 3, no. 5, pp. 46-53, 2008.