Walks on graphs as symmetric or asymmetric tools to encrypt data

Abstract

New results on graph theoretical method of encryption will be presented. The general idea is to treat vertices of a graph as messages, and walks of a certain length as ecnryption tools. We will construct one-time pad algorithms with a certain resistance to attacks when the adversary knows plaintext and ciphertext. Special linguistic graphs of high girth whose vertices (messages) and walks (encoding tools) could be both naturally identified with vectors over the finite field, and with the so-called parallelotopic graphs, which turn out to be efficient tools for symmetric encryption. We will formulate criteria when parallelotopic graph (or the more general graph of tactical configuration) is a graph of absolutely optimal encryption scheme, producing asymptotic one-time pad algorithm. We will show how to convert one-time pads, which are related to geometries of rank 2 of simple groups of Lie type, to a real-life encryption scheme involving potentially infinite text and flexible passwords.

We will discuss families of linguistic and parallelotopic graphs of increasing girth as the source for the generation of asymmetric cryptographic functions and related open key algorithms. We will construct new families of such graphs via group theoretical and geometrical technique.

The software for symmetric and asymmetric ecnryption (prototype model of the package) is ready for demonstration.