  While the reliable use of some NP-complete problem in tandem with the
assumption that P is not equal to NP has eluded cryptographers due to lack of
results showing average-case hardness, one alternative which has been explored
is reliance on assumptions that solving certain NP-hard optimization problems
within some degree of accuracy is computationally difficult in specific
instance classes. In this work, we explore one such example of this effort
which attempts to provide cryptographic primitives by relying on the planted
clique conjecture. More specifically, we (1) present this construction in
summary, (2) propose a simple cryptanalytic method using only approximation
algorithms, and (3) consider the feasibility of such cryptanalysis in the
context of existing approximation algorithms for the maximum clique problem. We
ultimately find that recent advances in the area of combinatoric approximation
algorithms fatally hinders the prospect of any serious application of existing
candidate constructions based upon the planted clique conjecture.
