• 1-781-515-5000
RSA LABORATIORIES
11 Cambridge Center
Cambridge, MA 02142 - USA

RSA Laboratories

Hiding Cliques for Cryptographic Security

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$, it is widely conjectured that no polynomial-time algorithm exists which finds a clique of size $\geq (1 + \epsilon)\log_2$ with significant probability for any constant $\epsilon > 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 + 2 \epsilon) \log_2$ -- is randomly inserted ("hidden'') in a random graph, finding a clique of size $\geq (1 + \epsilon)\log_2$ remains hard. Our result suggests several cryptographic applications, such as a simple one-way function.