Hiding Cliques for Cryptographic Security

We demonstrate how a well studied combinatorial optimizationproblem may be used as a new cryptographic primitive. The problemin question is that of finding a "large" clique in a randomgraph. While the largest clique in a random graph with nvertices and edge probability p is very likely tobe of size about , it is widely conjecturedthat no polynomial-time algorithm exists which finds a cliqueof size with significantprobability for any constant > 0. We presenta very simple method of exploiting this conjecture by hidinglarge cliques in random graphs. In particular, we show that ifthe conjecture is true, then when a large clique—of size,say, is randomlyinserted (hidden) in a random graph, finding a clique ofsize remains hard.Our analysis also covers the case of high edge probabilitieswhich allows us to insert cliques of size up to . Our result suggests several cryptographicapplications, such as a simple one-way function.