Hidden Cliques as Cryptographic Keys

Ari Juels and Marcus Peinado

EECS Department, University of California, Berkeley

Technical Report No. UCB/CSD-96-912

, 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<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.

BibTeX citation:

@techreport{Juels:CSD-96-912,
    Author= {Juels, Ari and Peinado, Marcus},
    Title= {Hidden Cliques as Cryptographic Keys},
    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