Implementation and Evaluation of a Novel Encryption Algorithm Based on Graph Traversal

Henry Hetzel, Dr. Lydia Ray, Department of Computer Science, Columbus State University, 4225 University Ave, Columbus, GA 31907

Wireless embedded systems with tiny sensors are helping cyberspace expand beyond traditional digital devices, thereby creating Internet of Things (IoT) and Cyber Physical Systems (CPS). The growing need for cybersecurity in the expanding cyberspace poses new challenges for cryptography. Existing robust cryptosystems require a lot of computing power and memory, and hence are not good fit for networks that contain many tiny sensors with very little computing power and memory. We need lightweight cryptosystems that will provide good security at minimum expense.  Motivated by this need, I have designed a non-traditional, lightweight cryptosystem based on graph traversal. Instead of encrypting data, this algorithm emulates a playbook that sports teams would use to send and receive covert instructions. A randomly generated connected graph with nodes storing alphabets and numbers is distributed to both the sender and the receiver. Instead of transmitting the secret message, the sender sends graph traversal instructions that help the receiver generate the secret message on her own device. This involves little computing time and resources. Nodes are randomly chosen for storing numbers and letters, thereby adding to the strength of the system. Thus, even if the traversal instructions are intercepted, regenerating the random graph will be computationally expensive, if not infeasible. I hypothesize that my cryptosystem reasonably robust against brute force attacks, frequency analysis and cryptanalysis. I am currently implementing the application that generates the random graph and creates a set of traversal instructions for an input message. I will compute the cost of encryption and decryption in terms of computing resources. Then I will implement a brute-force attack algorithm and will compute the average time required for a message to be cracked. I will also investigate the strength of my system against frequency analysis and cryptanalysis and compare all results with modern symmetric key cryptosystems.  

Additional Abstract Information

Presenter: Henry Hetzel

Institution: Columbus State University

Type: Oral

Subject: Computer Science

Status: Approved

Time and Location

Session: Oral 3
Date/Time: Mon 4:30pm-5:30pm
Session Number: 345
List other presenters in this same room and session