CDR: Re: why should it be trusted? (NP-Completeness, cracking speed)

[Bill Stewart]

At Tue, 17 Oct 2000 17:39:13 -0700  Nathan Saper <natedog at well.com> wrote
> Unless I'm mistaken, there is no essential physical law that
> determines computing power, exploits of algorithms, etc. 
> The same cannot be said for speed-of-light travel.

Data storage probably requires at least an atom,
or at least one electron, or at least one quark.
There are only so many spare ones of these in the universe.
Speed's a fuzzier issue - Heisenberg's Uncertainty Principle
limits how closely you can know the velocity and location simultaneously,
plus there are speed-of-light limits on how fast communications
between particles can occur, given that the distances are non-zero.
There have also been calculations on energy requirements for
computation (don't remember the rationale; probably in Schneier 2nd Ed.)

Quantum Black Magic may provide ways to cheat on this,
by creating a set of problems for which the waveform has a 
high probability of collapsing in the correct state.
(It's also possible to get wrong answers, 
but NP-hard problems are easy to verify quickly.)
However, extracting the result from the system requires
measuring to a precision corresponding to the number of bits
you're trying to extract from the system - I'm not convinced there's
a way to cheat Heisenberg, in which case you're limited to ~150 bits
(compared to the current resolution of ~5 bits :-)

There's no current mathematical proof that P!=NP, 
or that factoring is in the hard set of problems 
(unlike Linear Programming, which Karmarkar et al. showed
could be done in big-ugly-polynomial time, though
in practice the Simplex method almost always was fast enough.)
Also, most symmetric crypto is based on the principle that
it tweaks bits in sufficiently ugly ways that it breaks up any
more efficient cracking methods other than exponential brute force.


At 07:51 PM 10/17/00 -0400, dmolnar wrote:
>Um, "NP-hard" just means that it's polynomial time reducible to any
>problem in NP (or perhaps the other way around, I always get the
>directions mixed  up). It is fairly straightforward to show this - you

It is the other way around.  By showing that some known NP-complete
problem is reducible to Your Problem (using polynomial work), 
you've shown that any polynomial-time solution to Your Problem
solves the known NP-complete problem in (bigger) polynomial time,
and therefore solves all NP-complete problems.  
To prove NP-completeness, you also have to prove that 
Your Problem is polynomial-time reducible to a (possibly different) 
known NP-complete problem (thence to all others).
(There are also variants like P-Space Completeness,
which came out after I left grad school, which are a bit broader
than NP-completeness.)

"NP-hard" is a fuzzy term - it includes NP-complete problems,
plus things that aren't formulated as decision problems
(like "find the optimum" as opposed to "determine whether X is optimum"),
and some people use the term for problems that are at least
as hard as NP-complete problems but might be also harder.
So they might count something that solves an NP-complete problem
without bothering to check if it's also reducible to an NP-complete
problem,  because they're satisfied with a result that says
"look, this is at least as hard as NP-complete,
so let's use some fast heuristics instead of going for the optimum."


>Put another way, showing a problem is NP-hard doesn't actually show that
>it is "hard." It just shows that the problem is no easier than any problem
>in the class NP. It could still be the case that P = NP, in which case
>there is a rash of suicides in the crypto world...

No, that would be a *Great* *Thing* for academic crypto.
Think of all the brand new exciting research papers that could be
written, and all the searching for new problems that are hard enough,
and kicking holes in new snake oil, and loads of fun in general.

Particularly, anything that proved P=NP would provide lots of tools
for exploring the boundaries between NP-complete problems
and other currently-believed-hard problems such as factoring
(and discrete logarithms, and elliptical curve variations on them.)
We might find out that factoring is *harder* than NP-complete (:-),
though I don't expect that.  My own guesses are that of course P!=NP,
but factoring might not be as hard as NP-complete,
and in particular elliptical curves might or might not be safe
using far fewer bits than regular RSA or DH (though the EC math is
too deep for my current knowledge, so I'm just guessing.)

For *practical* crypto, it would be a major pain to lose factoring,
because most NP-complete problems (e.g. knapsack) don't have forms that
are cryptographically useful - knowing that the right key lets you
solve the problem in polynomial time doesn't mean that it's easy
for the user to *find* a key like that in polynomial time
except by using special subproblems that turn out not to need exponential
time 
to solve them.

So in practice, we'd have to go back to symmetric-key KDCs
(Key Distribution Centers, for systems like Kerberos),
and One-Time Pads for the really paranoid stuff
(like shipping around master keys for the KDCs) for high security,
plus medium security that's basically Highly Refined Snake Oil,
where the cracker only needs to do polynomially more work than
the users, so in practice it's good enough for your credit card number,
but not good enough to keep anti-government secrets away from the NSA
or secret-government-conspiracy secrets safe from Distributed.Net,
so the convenient stuff risks spy-vs-spy and angry-mobs-with-pitchforks
attacks.

Also in practice, that kind of breakthrough isn't likely to mature
for at least a decade (between how long it takes for the hypothetical
breakthrough to occur and how long before the system really
takes to adapt to it), and even if we haven't had the
Great Mythical Nanotech Singularity by then, we'll have enough
computer power and miniaturization technology that it'll be 
much easier to steal keystrokes right off your keyboard and screen,
rather than cracking the crypto, close enough for government work,
so black bag jobs will be common and we'll be back to a spy-vs-spy game.
				Thanks! 
					Bill
Bill Stewart, bill.stewart at pobox.com
PGP Fingerprint D454 E202 CBC8 40BF  3C85 B884 0ABE 4639