Global Sales Contact List

Contact   A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

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

Notes:
Connect with EMCConnect with EMC
Need help immediately? EMC Sales Specialists are standing by to answer your questions real time.
Use Live Chat for fast, direct access to EMC Customer Service Professionals to resolve your support questions.
Explore and compare EMC products in the EMC Store, and get a price quote from EMC or an EMC partner.
We're here to help. Send us your sales inquiry and an EMC Sales Specialist will get back to you within one business day.
Want to talk? Call us to speak with an EMC Sales Specialist live.