<p>As pointed out by many other posters, it is possible to base cryptography on NP-hard or NP-complete problems.</p>
<p>However, the common methods for cryptography are going to be based on difficult mathematics (difficult to crack, that is).  The truth is that it is easier to serialize numbers as a traditional key than to create a standardized string that solves an NP-hard problem.  Therefore, practical crypto is based on mathematical problems that are not yet proven to be NP-hard or NP-complete (so it is conceivable that some of these problems are in P).</p>
<p>In ElGamal or RSA encryption, breaking it requires the cracking the discrete logarithm, so look at this <a href="http://en.wikipedia.org/wiki/Discrete_logarithm" rel="nofollow noreferrer">wikipedia</a> article.</p>
<blockquote>
<p>No efficient algorithm for computing general discrete logarithms logbg is known. The naive algorithm is to raise b to higher and higher powers k until the desired g is found; this is sometimes called trial multiplication. This algorithm requires running time linear in the size of the group G and thus exponential in the number of digits in the size of the group. There exists an efficient quantum algorithm due to Peter Shor however (<a href="http://arxiv.org/abs/quant-ph/9508027" rel="nofollow noreferrer">http://arxiv.org/abs/quant-ph/9508027</a>).</p>
<p>Computing discrete logarithms is apparently difficult. Not only is no efficient algorithm known for the worst case, but the average-case complexity can be shown to be at least as hard as the worst case using random self-reducibility.</p>
<p>At the same time, the inverse problem of discrete exponentiation is not (it can be computed efficiently using exponentiation by squaring, for example). This asymmetry is analogous to the one between integer factorization and integer multiplication. Both asymmetries have been exploited in the construction of cryptographic systems.</p>
</blockquote>
<p>The widespread belief is that these are NP-complete, but maybe can't be proven so.  Note that quantum computers may break crypto efficiently!</p>
Are there public key cryptography algorithms that are provably NP-hard to defeat?
<p>Should practical quantum computing become a reality, I am wondering if there are any public key cryptographic algorithms that are based on NP-complete problems, rather than integer factorization or discrete logarithms.</p>

<p>Edit:</p>

<p>Please check out the "Quantum computing in computational complexity theory" section of
<a href="http://en.wikipedia.org/wiki/Quantum_computer" rel="noreferrer">the wiki article on quantum computers.</a>  It points out that the class of problems quantum computers can answer (BQP) is believed to be strictly easier than NP-complete. </p>

<p>Edit 2:</p>

<p>'Based on NP-complete' is a bad way of expressing what I'm interested in.</p>

<p>What I intended to ask is for a Public Key encryption algorithm with the property that any method for breaking the encryption can also be used to break the underlying NP-complete problem.  This means breaking the encryption proves P=NP.</p>