### Hidden Cliques as Cryptographic Keys

**Authors:**

Juels, Ari

Peinado, Marcus
**Technical Report Identifier:** CSD-96-912
**August 22, 1996**

CSD-96-912.pdf

CSD-96-912.ps

**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 2log2*n*, it is widely conjectured that no polynomial-time algorithm exists which finds a clique of size (1 + epsilon)log2*n* 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)log2*n* for constant delta > 0 is randomly inserted ("hidden") in a random graph, finding a clique of size (1 + epsilon)log2*n* remains hard. In particular, we show that if there exists a polynomial-time algorithm which finds cliques of size (1 + epsilon)log2*n* 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.