Douglas Stebila
Cryptographic applications of graph theoretic constructions
Supervisor: Prof Dominic J. A. Welsh.
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 (A. Juels and M. Peinado. Hiding cliques for cryptographic security. In Proc. 9th Ann. ACM-SIAM Symp. on Discrete Algorithms, pages 678-684, 1998.) to demonstrate that, assuming it is hard to find a clique of size (1+ε) log1/p(n) in a random graph from Gn,p, it is also hard to find a hidden clique of the same size embedded in a graph from Gn,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.
Reference
Douglas Stebila. Cryptographic applications of graph theoretic constructions. MSc thesis, University of Oxford. September 2004.