### Ari Juels and Marcus Peinado

###
EECS Department

University of California, Berkeley

Technical Report No. UCB/CSD-96-912

August 1996

### http://www2.eecs.berkeley.edu/Pubs/TechRpts/1996/CSD-96-912.pdf

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.

BibTeX citation:

@techreport{Juels:CSD-96-912, Author = {Juels, Ari and Peinado, Marcus}, Title = {Hidden Cliques as Cryptographic Keys}, Institution = {EECS Department, University of California, Berkeley}, Year = {1996}, Month = {Aug}, URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1996/5284.html}, Number = {UCB/CSD-96-912}, 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<i>n</i>, it is widely conjectured that no polynomial-time algorithm exists which finds a clique of size (1 + epsilon)log2<i>n</i> 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<i>n</i> for constant delta > 0 is randomly inserted ("hidden") in a random graph, finding a clique of size (1 + epsilon)log2<i>n</i> remains hard. In particular, we show that if there exists a polynomial-time algorithm which finds cliques of size (1 + epsilon)log2<i>n</i> 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.} }

EndNote citation:

%0 Report %A Juels, Ari %A Peinado, Marcus %T Hidden Cliques as Cryptographic Keys %I EECS Department, University of California, Berkeley %D 1996 %@ UCB/CSD-96-912 %U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1996/5284.html %F Juels:CSD-96-912