Electrical Engineering
      and Computer Sciences

Electrical Engineering and Computer Sciences

COLLEGE OF ENGINEERING

UC Berkeley

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://www.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://www.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://www.eecs.berkeley.edu/Pubs/TechRpts/1996/5284.html
%F Juels:CSD-96-912