Hidden Cliques as Cryptographic Keys

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