Hiding Cliques for Cryptographic Security
Ari Juels, Marcus Peinado · 1998
) Ari Juels RSA Laboratories 20 Crosby Dr. Bedford, MA 01730 [email protected] Marcus Peinado y Institute for Algorithms and Scientific Computing German National Research Center for Information Technology (GMD) 53754 Sankt Augustin, Germany [email protected] Abstract We demonstrate how a well studied combinatorial optimization problem may be introduced as a new cryptographic function. The problem in question is that of finding a "large" clique in a random graph. While the largest clique in a random graph is very likely to be of size about 2 log 2 n, it is widely conjectured that no polynomial-time algorithm exists which finds a clique of size (1 + ffl) log 2 n with significant probability for any constant ffl ? 0. We present a very simple method of exploiting this conjecture by "hiding" large cliques in random graphs. In particular, we show that if the conjecture is true, then when a large clique -- of size, say, (1 + 2ffl) log 2 n -- is randomly inserted ("hidden") in a random graph, fi...