Cryptographic applications of graph theoretic constructions
Abstract
While the difficulty of solving certain graph theoretical problems has been at the heart of important questions in complexity theory, the hard problems used for cryptographic purposes are usually number theoretic in nature. We explore the use of graph structures for cryptographic purposes.
Finding a hidden clique in an otherwise random graph has potential as a hard problem. We extend a previous result of Juels and Peinado to demonstrate that, assuming it is hard to find a clique of size (1+epsilon) log_(1/p)(n) in a random graph from G_(n,p), it is also hard to find a hidden clique of the same size embedded in a graph from G_(n,p); this assumption has been an open problem for 30 years. Although our result holds asymptotically, the problem can be solved with non-trivial probability for graphs with, say, 1000 vertices. Hidden cliques can be used in a zero-knowledge protocol for authentication or in a generalized encryption scheme. We discuss the practicality of graph-based cryptographic systems and conclude that protocols based on hidden cliques exchange data structures of too large a size to be feasible.
We also report on the infeasibility of using knowledge of hidden Hamiltonian cycles or knowledge of graph colourings as the basis of a cryptosystem.
