On Tue, 17 Oct 2000, Jordan Dimov wrote:

...

Could a factoring breakthrough happen to convert this exptime problem to polynomial time? Maybe. I said as much. Is it likely? See discussions on progress toward proving factoring to be NP-hard (it hasn't been proved to be such, though it is suspected to be so, i.e., that there will never be "easy" methods of factoring arbitrary large numbers).

Geee... Since when are problems "proven" to be NP-hard?? Go back to your favorite undergrad institution and take a course on computational complexity again.

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 exhibit a reduction to another problem you already know to be NP-hard. The "original" such problem is bounded halting : given a TM description M, an input x, and a polynomial bound p(n), does M halt on input x in p(length(x)) time? The famous theorem of Cook consists exactly of a reduction relating SATISFIABILITY and bounded halting. That's annoying. But once it's done you can give reductions to SATISFIABILITY instead. See Garey & Johnson's book for more examples. 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... At the same time, it is believed unlikely that factoring is NP-hard. This is because "factoring" (the function problem 'find the factors of n'; not sure exactly how to formalize as a decision problem) is in NP intersect coNP. If factoring is NP-hard, then NP = coNP. This is believed to not be the case (but of course not proven). In addition, it's not at all clear how you could solve arbitrary SAT instances given an oracle for factoring. Try it and see.

...

You don't appear to be familiar with the literature. I suggest you do some reading.

Yeah, right. And you are familiar.

He has the outline right, if not all the details. -David

At Tue, 17 Oct 2000 17:39:13 -0700 Nathan Saper <natedog@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@pobox.com PGP Fingerprint D454 E202 CBC8 40BF 3C85 B884 0ABE 4639