Hiding Cliques for Cryptographic Security

作者：Ari Juels, Marcus Peinado · 年份：1998 · 被引用次数：27 · 研究领域：Complexity and Algorithms in Graphs、Limits and Structures in Graph Theory、Cryptography and Data Security

) Ari Juels RSA Laboratories 20 Crosby Dr. Bedford, MA 01730 ari@rsa.com Marcus Peinado y Institute for Algorithms and Scientific Computing German National Research Center for Information Technology (GMD) 53754 Sankt Augustin, Germany peinado@gmd.de 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...