RSA Laboratories

Hiding Cliques for Cryptographic Security

Ari Juels and Marcus Peinado

Citation: A. Juels and M. Peinado. Hiding Cliques for Cryptographic Security. In Proceedings of the ninth annual ACM-SIAM Symposium on Discrete Algorithms (SODA), ACM Press, 1998. Journal version to appear in Cryptography, Codes, and Designs.

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.

Note: This is far from being practical, but interesting inasmuch as it demonstrates the possibility of a combinatorial basis for cryptographic functions.

Click here for paper

Full Publication List