Hidden Cliques as Cryptographic Keys
Abstract: We demonstrate in this paper a very simple method for "hiding" large cliques in random graphs. While the largest clique in a random graph is very likely to be of size about 2log2n, it is widely conjectured that no polynomial-time algorithm exists which finds a clique of size (1 + epsilon)log2n with significant probability for any constant epsilon > 0. We show that if this conjecture is true, then when a clique of size at most (2 - delta)log2n for constant delta > 0 is randomly inserted ("hidden") in a random graph, finding a clique of size (1 + epsilon)log2n remains hard. In particular, we show that if there exists a polynomial-time algorithm which finds cliques of size (1 + epsilon)log2n in such graphs with probability 1/poly, then the same algorithm will find cliques in completely random graphs with probability 1/poly. Given the conjectured hardness of finding large cliques in random graphs, we therefore show that hidden cliques may be used as cryptographic keys.