ISSN : 1796-203X
Volume : 3    Issue : 5    Date : May 2008

VLSI Architecture of a Cellular Automata based One-Way Function
D. Mukhopadhyay, P. Joshi, and D. RoyChowdhury
Page(s): 46-53
Full Text:
PDF (503 KB)

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