Hiding Cliques for Cryptographic Security

We demonstrate how a well studied combinatorial optimization problem may be used as a new cryptographic primitive. The problem in question is that of finding a "large" clique in a random graph. While the largest clique in a random graph with n vertices and edge probability p is very likely to be of size about 2 log1/p n, it is widely conjectured that no polynomial-time algorithm exists which finds a clique of size (1 + ) log1/p n with significant probability for any constant > 0. We present a very simple method of exploiting this conjecture by "hiding" large cliques in random graphs. In particular, we show that if the conjecture is true, then when a large clique - of size, say, (1 + 2) log1/p n - is randomly inserted ("hidden") in a random graph, finding a clique of size (1 + ) log1/p n remains hard. Our analysis also covers the case of high edge probabilities, which allows us to insert cliques of size up to n1/4- ( > 0). Our result suggests several cryptograph ic applications, such as a simple one-way function.