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 log(1/p)n, it is widely conjectured that no polynomial-time algorithm exists which finds a clique of size greater than or equal to (1 + epsilon)\log(1/p)n with significant probability for any constant epsilon > 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 epsilon) log(1/p)n-is randomly inserted ("hidden'') in a random graph, finding a clique of size greater than or equal to (1 + epsilon)\log(1/p)n remains hard. Our analysis also covers the case of high edge probabilities which allows us to insert cliques of size up to n(1/4-epsilon) (epsilon>0). Our result suggests several cryptographic applications, such as a simple one-way function.
cliques random graphs graph-based crypto systems