Back when Cheswick and Bellovin were doing the original Bell Labs firewalls, and caught a Dutch teenager trying to hack into their site, the Netherlands didn't have any computer security laws that made it illegal. "So we called his mom...."
I'd missed your point about the relationship of side panel and Ctrl +/- - but I was getting quite annoyed at how wide the side panel was, given that I normally run two or three Ctrl+ steps on/.:-) Looks like it's a lot less annoying without doing that. But yeah, there are lots of other problems with the new layout, like the changes in the "look at your own comments and see if there are any replies" section, which made it much harder to find this.
Molly's Revenge are one of the local Irish bands seen here in the Bay Area. (Apparently they were a follow-on to an earlier band called Dance Around Molly, but with a name like "Molly's Revenge" they eventually had to wrote a song involving someone named Molly and some revenge...)
It's one thing if the search warrant is "search one specific individual's home looking for his PC and trying to get log information on it." It's quite another if the search warrant is "order Comcast to produce all the information they have on the following list of 45000 IP addresses." Sometimes the Feds tell you one kind of number, sometimes they tell you another. (For instance, the numbers of legal wiretaps they'll admit to are usually quite small, obfuscating the broad scope of some of those wiretaps, but sometimes they're giving you numbers of a quality similar to the "street value of the drug seizure" type to inflate how macho they are.)
Also, realistically, while "Anonymous" might be everybody who's read/b/ at one time or another, but the actual number of people who organized the DDOS attacks and asked for volunteers to run LOIC is probably fairly small, and if they didn't do a good enough job of anonymization, it's possible that they might really be punishing the key players and making clear that they know how to do it on future attacks. On the other hand, if they're just picking a random 40 easy targets who ran LOIC, charging them with conspiracy to commit [crimes defined in ways to make them felonies], and threatening to fine them each for the amount of damage that was done to Paypal et. al's business, that could discourage future participants.
I'm of an age to need reading glasses, and I've been using the feature in Firefox, Chrome, and IE that you do Control Plus or Control Minus and it adjusts the font size. It's working fine here - it keeps track of settings on a domain name basis, so meta.slashdot.org didn't remember the settings I'd used on www.slashdot.org, but it does ok.
There seems to be too much white space in the new design, which is a bit annoying on my laptop but should be just fine on your big screen.
Hi, it's a week late for a normal reply, but your article just came up for metamoderation. Slashdot Guidelines are that articles deserve positive moderation if they're trying to contribute what the author thinks is something positive to the discussion, and shouldn't get negative moderation even if you think they're wrong, and metamoderation should reinforce this.
You, Sir or Maam, fall into both categories, so as a metamoderator, I gave you a "+", but I'm posting this to rant at you for being seriously wrong. I'm not likely to read your response or follow it up - I try to minimize the amount of complaining to wrong-headed partisan Democrats I do, and ranting at wrong-headed partisan Republicans is hopeless so I try not to do it at all, but in the interest of balance I'm posting a brief rant to make up for the positive feedback the metamoderation gave you.
Obama's candidacy was supposed to be about Hopey Changey Stuff, restoring the basic American civilized values that the Bush/Cheney/Rove Administration discarded, getting us out of the Iraq War, and implementing a bunch of traditional Democratic Party goals, like helping poor people, and it was supposed to be about fixing the economy which Bush so irresponsibly trashed. The reasons the Democrats picked him over Hilary Clinton were primarily his inspiring speaking and her lack of commitment to getting us out of Iraq (neither one would have gotten us out of Afghanistan, and while Dennis Kucinich and a couple of the other minor candidates might have, they weren't serious players; I forget where Edwards stood before he self-destructed.)
Obama promised to fix the atrocity of America's illegal treatment of prisoners in Guantanamo Bay, and his first week in office he told us he'd be doing it, and then he chickened out and let the Republicans and conservative Democrats pretend that giving fair trials to people America had tortured would cause the terrorists under your beds to eat The Homeland's children. And beyond that, instead of having his Justice Department prosecuting war criminals or at least abrogating the policies the Bush League set while they were in office, Holder and friends have been defending them. And while they're probably not torturing prisoners any more, and there's a bit more adult supervision, they still haven't given these people fair trials, and there's a serious lack of transparency about how the official prisons in Iraq and Afghanistan are treating prisoners, much less about whether they're still running unofficial secret prisons.
Warrantless Wiretapping - As with war crimes, the Justice Department is defending this set of Bush Policies, because the folks they work for like to avoid any legal and Constitutional restrictions on arbitrary surveillance and prosecution.
Extrajudicial Assassination By Executive Order - No, Obama didn't promise that he'd do it while he was out campaigning, he just announced it after he got into office. I suppose he gets some transparency points for admitting it; even Darth Cheney Himself wouldn't have said he was going to have people assassinated, he would have just done it and kept it hidden.
Immigration reform - there's a lot that could and should have been done to make La Migra treat people fairly and openly, and to fix the immigration-detention prisons which are an offense to civilized society. And Obama's kept them as part of the Homeland Security Mafia which should have been broken up. However, the fundamental questions are more political - some people think "reform" means sending all the brown people back to Mexico even if they're not from there, and some people think it means having Congress follow its Constitutionally mandated duty of setting up processes for naturalizing immigrants, and the right-wing propaganda machine has been pushing anti-immigrant hatred for years, so it's been tough for moderate Republicans to say anything (and on this issue, Bush was a moderate, even if it was just because he liked cheap imm
icanhascheeseburger.com - blocked: You can not has cheeseburger. Here is bukkit.
facebook.com - blocked: Medical plan does not cover ADD treatment. $MANAGER has just become Godfather. $CAFETERIA has canoli today. $HR-Department has given you a shrubbery!
As of a week or two ago, the Usual Internet Pundits were reporting that spam was back up to its Pre-Christmas-Break levels. December and January may still count as low-volume months, because the botnets took two weeks off, but the bots are rested, relaxed, and back at work making the Internets a profitable place for blood-sucking parasites again.
One of the more serious problems with the military-industrial complex's development process, besides obvious little things like threatening to kill millions of people and possibly initiate nuclear winter, is that it takes a large number of scientists and engineers and diverts them away from useful civilian technology and diverts their talents to working on projects that ideally will never be used, and hides any parts of that work that could be useful away where the public can't use it.
There are occasionally useful technologies that escape - this "Internet" thing really is more convenient than uucp and Usenet were, and GPS is really cool but there are other ways to implement wide-area navigation systems without satellites. But they guys who were making tank engines 20% more efficient could have been doing that for truck engines or car engines, and the people working on improving small supersonic airplanes could have been improving civilian passenger or cargo airplanes instead.
But seriously, American stealth bombers were designed to work well over oceans and Russian terrain, and apparently didn't work so well over open desert terrain.
Ok, it's mostly crowded with spam and pr0n\\\\binaries, and ISPs have mostly stopped providing news service as a standard feature of an account, and I haven't had a decent NNTP reader in a decade or more, but yeah, Usenet's still around. I stopped being able to read all of it (printed on paper, 4-up double-sided) some time in the 80s, stopped being able to read more than a couple of newsgroups later in the 90s, but Google Groups still provides access if I need to look for things, and the last time I checked Google still had DejaNews articles with spotty coverage of stuff I'd written almost three decades ago.
It's more like the Kennedy assassination - who wouldn't gain by smearing Wikileaks here? Even Wikileaks themselves* might have planted it as a diversion as opposed to surreptitiously leaving it behind. Or maybe it's a Murder on the Orient Express plot, where either a whole bunch of players conspired together to do it, or else some stranger walked in the door, planted it, and walked out unseen.
*Yes, I do reject any of the conspiracy suggestions that say Kennedy himself was behind it, except the one on Red Dwarf which might have been true, but between several Mafia families, the CIA, Cuba, anti-Castro Cubans, the Pentagon, Military-Industrial Complex businesses, several jealous ex-husbands, Bobby, Jackie, Frankie, Marilyn, J.Edgar, J.Edgar's dress-maker, and the Lone Gunmen, it really was a race to get there first....
If it's actually related to Wikileaks, as opposed to a US-or-Euro-government spook job, it's more likely to be a Tor node. For that matter, even if it is a CIA plant, it could well be a Tor node, and similarly, if it's a fake scapegoat machine that the former bank minister is using to cover his tracks, a Tor node would be a good choice.
Yup. It could just as easily have been left there by the former third assistant clerk to the Finance Minister, who got sacked when Iceland's banking system collapsed, and who was too polite to take his severance pay in used hardware.
If you're working in a given field, there may be problems that are more like the one you're working on than 3-SAT, so you can reduce to/from them, which will often be much easier and more efficient to prove, even if it's a less efficient way to solve 3-SAT. If your goal is theoretical, that's fine - Reduce FOO to BAR, BAR is known to be NP-Complete, Deliver Thesis.
If your goal is practical, because you want to solve real instances of FOO, tell you it's NP-hard may say you shouldn't try to find the optimal solution but look for near-optimal heuristics, or maybe you should reduce it to BAR, which already has a good near-optimal heuristic or has an optimal solution that's usually but not always fast. Or it may be that knowing that FOO is NP-hard tells you to give up and solve a different problem instead (e.g. in cryptography, where inexact solutions are useless so maybe you should put a keylogger in your enemy's keyboard or drug the courier who's got the one-time pads instead.)
To be precise, probably nobody's built one on purpose...
If you're asking whether non-determinism exists in the physical world, that's really a metaphysical question, and you should ask a philosopher or your local quantum mechanic. In the cryptography business, the closest related problem is "If you've stolen a key from your target, can you tell if it's the right one?"
The original Turing machines had infinitely long tapes, which is easy to do if you don't have to build one of them. Since the original work in NP-Completeness, there have been a bunch of further problem classes defined that may constrain the size of the Turing machine, e.g. PSPACE problems with can only be run on a system with space that's bounded by a polynomial function of the size of the problem, so you potentially could build them for some reasonable sets of problems. More years, more PhD theses, more professors needing to publish papers, more problem categories.
R's a pretty schmart guy, and while I haven't mean S or A, I'd bet that's true about them as well.
N = PQ, where P and Q are primes. If you know P and Q, you can determine the encryption and decryption keys in polynomial time, and use them in polynomial time, which is why using RSA at all is practical. If an oracle gives you p and q, you can determine in polynomial time whether N = pq, therefore RSA is in NP. The best-known algorithms for factoring are around e^(n/3), which means that you can make it the work your attacker needs to do exceed the predicted lifetime of your planet while still only needing to do small amounts of work yourself, so that means that RSA provides security while remaining practical.
If P=NP, then there is an algorithm to determine P and Q from N in polynomial time, and therefore an attacker can determine your keys in polynomial time, so you're not secure. It may be that the polynomial is something large and annoying, like O(N^10) to crack vs. O(N^4) to generate keys, in which case a defender with moderate resources might still be able to protect her data against an attacker with relatively large resources, but it's more likely that a defender wouldn't be able to create practical-sized keys with age-of-the-planet attack times.
Factoring is not believed to be NP-complete, so it's possible that somebody could solve factoring without solving 3-SAT, but this guy's apparently claiming to be able to solve 3-SAT, at least to accuracy-of-the-media levels of interestingness.
The secure channel for a one-time pad is a guy with a briefcase handcuffed to his arm, optionally wearing a tuxedo or a uniform or accompanied by an armed guard. Occasionally there are other options, such as a pressurized conduit between nearby buildings, with the data carried over a fiber-optic system, but that's also depending on physical security for protection.
If you've transmitted your code pad over any physically eavesdroppable medium, it's no longer a one-time pad, it's just a chunk of data encrypted with whatever encryption algorithm the transmission medium used, no matter what the sales guy for the "one-time pad" company told you.
> You appear to have used a sociological argument as proof of a mathematical statement.
Absolutely correct!
> You fail.
No. It's not meant to be a conclusive proof, it's just the way to bet. A proof that P=NP would be Really Cool, and do all kinds of really useful things for the Real World as well as for mathematicians, even though for a cryptographer or computer security designer it would be a major pain in the ass\\\\\\\\\ New Business Opportunity.
We've already got to deal with Quantum Computers as a potential future threat model, so we're not forgetting how to do hashes and Key Distribution Centers, and making sure to design protocols that let you use longer key sizes if you need them, and if P=NP we'll have to live with that as well, though it probably tips the balance to make it possible for a government-sized attacker to beat a PC-using communicator, as opposed to today when it's the other way around.
I've already been through this sort of thing before. I was an operations researcher in college, and a couple of years after I graduated, Karmarkar came out with his linear programming algorithm, which was in P rather than exponential like Dantzig's Simplex algorithm. On the other hand, simplex was usually pretty fast, and almost never in the slow cases for real problems, and Karmarkar's was something like O(n^6), which was annoyingly slow and large for real problems, but computers have been gotten a lot faster in the last three decades. On another hand, the Internet and computerized typesetting have made the Net.Kook problem much harder than the days that kooks had to use carbon paper and bad typewriters.
Sure, there are problems that are exponentially hard that you can still often solve for small n, and there are problems that are exponentially hard in the worst case but usually only take polynomial time if you're lucky, and sometimes you can depend on usually being lucky, and there are problems that are exponentially hard if you need the best answer, but have polynomial solutions that will get you within X% of the best answer, which may be good enough.
Cryptography is not any of those problems - you can solve for small n, so the crypto designer just uses a key that's long enough not to be small, and maybe encryption takes twice as long but cracking takes 2^100 times as long. Inexact answers are good enough for the Travelling Salesman Problem, because taking 50% longer to reach all your destinations is still feasible, but guessing one bit wrong in a crypto key usually means that half the output bits are different and you don't know which ones.
My department once had a bunch of physicists writing simulation code, because some of what they were simulating behaved in physics-like ways. I was running the computer, because that was back when you often wanted Computer Nerds to do that for you, though I was really a simulation jock and math nerd.
They were in fact using linear searches through a linked list to manage their event queue in O(n^2) time, and when I made them use a heap to get O(n log n) behaviour, I was disappointed that it only sped up their system by a factor of 5; apparently their code was doing some work besides managing the event list. Also, the system they were modelling basically bounced randomly around a large matrix that didn't fit into our huge 4MB RAM (this was ~1984), and crawling through the linked lists got them some physical locality so it wasn't always paging. A couple of years into the project, memory technology and price had improved enough that we were able to upgrade the VAX to 16MB, and suddenly the program could run in an hour instead of a week, though by that time we'd been able do enough research to tell the end user that the solution we were modelling wasn't really a good one, so being able to run a few hundred more examples a week let us pile on results to help convince them.
Lots of really smart mathematicians have been trying to find proofs that P==NP for a long time, and they've got lots of good tools to work with. None of them have succeeded. They've also been trying to prove that P!=NP, but that's probably much harder to prove, or at least to validate, since a constructive proof that P=NP has lots of testable examples.
Occasionally people make assertions that they've got a proof that either P==NP, or P!=NP; if they're smart they get them peer-reviewed and find the mistake, but maybe they get to improve our understanding of the general problem or some more specific hard problem, so at least they get a paper out of it. If they're not smart, they just publish it on the InterWebs, and either become net.kooks or have someone gently explain to them how the academic research process works, but the fact that they don't know suggests that they haven't read all the standard research. If they're greedy, they try to patent it, and if it gets past the Patent Examiners they can try selling it to a Patent Troll.
Slashdot Mirror
Back when Cheswick and Bellovin were doing the original Bell Labs firewalls, and caught a Dutch teenager trying to hack into their site, the Netherlands didn't have any computer security laws that made it illegal. "So we called his mom...."
I'd missed your point about the relationship of side panel and Ctrl +/- - but I was getting quite annoyed at how wide the side panel was, given that I normally run two or three Ctrl+ steps on /. :-) Looks like it's a lot less annoying without doing that. But yeah, there are lots of other problems with the new layout, like the changes in the "look at your own comments and see if there are any replies" section, which made it much harder to find this.
Molly's Revenge are one of the local Irish bands seen here in the Bay Area. (Apparently they were a follow-on to an earlier band called Dance Around Molly, but with a name like "Molly's Revenge" they eventually had to wrote a song involving someone named Molly and some revenge...)
It's one thing if the search warrant is "search one specific individual's home looking for his PC and trying to get log information on it." It's quite another if the search warrant is "order Comcast to produce all the information they have on the following list of 45000 IP addresses." Sometimes the Feds tell you one kind of number, sometimes they tell you another. (For instance, the numbers of legal wiretaps they'll admit to are usually quite small, obfuscating the broad scope of some of those wiretaps, but sometimes they're giving you numbers of a quality similar to the "street value of the drug seizure" type to inflate how macho they are.)
Also, realistically, while "Anonymous" might be everybody who's read /b/ at one time or another, but the actual number of people who organized the DDOS attacks and asked for volunteers to run LOIC is probably fairly small, and if they didn't do a good enough job of anonymization, it's possible that they might really be punishing the key players and making clear that they know how to do it on future attacks. On the other hand, if they're just picking a random 40 easy targets who ran LOIC, charging them with conspiracy to commit [crimes defined in ways to make them felonies], and threatening to fine them each for the amount of damage that was done to Paypal et. al's business, that could discourage future participants.
Try doing Control-Plus - works fine for increasing the font size, but it does aggravate the whitespace problem.
I'm of an age to need reading glasses, and I've been using the feature in Firefox, Chrome, and IE that you do Control Plus or Control Minus and it adjusts the font size. It's working fine here - it keeps track of settings on a domain name basis, so meta.slashdot.org didn't remember the settings I'd used on www.slashdot.org, but it does ok.
There seems to be too much white space in the new design, which is a bit annoying on my laptop but should be just fine on your big screen.
Hi, it's a week late for a normal reply, but your article just came up for metamoderation. Slashdot Guidelines are that articles deserve positive moderation if they're trying to contribute what the author thinks is something positive to the discussion, and shouldn't get negative moderation even if you think they're wrong, and metamoderation should reinforce this.
You, Sir or Maam, fall into both categories, so as a metamoderator, I gave you a "+", but I'm posting this to rant at you for being seriously wrong. I'm not likely to read your response or follow it up - I try to minimize the amount of complaining to wrong-headed partisan Democrats I do, and ranting at wrong-headed partisan Republicans is hopeless so I try not to do it at all, but in the interest of balance I'm posting a brief rant to make up for the positive feedback the metamoderation gave you.
Obama's candidacy was supposed to be about Hopey Changey Stuff, restoring the basic American civilized values that the Bush/Cheney/Rove Administration discarded, getting us out of the Iraq War, and implementing a bunch of traditional Democratic Party goals, like helping poor people, and it was supposed to be about fixing the economy which Bush so irresponsibly trashed. The reasons the Democrats picked him over Hilary Clinton were primarily his inspiring speaking and her lack of commitment to getting us out of Iraq (neither one would have gotten us out of Afghanistan, and while Dennis Kucinich and a couple of the other minor candidates might have, they weren't serious players; I forget where Edwards stood before he self-destructed.)
Obama promised to fix the atrocity of America's illegal treatment of prisoners in Guantanamo Bay, and his first week in office he told us he'd be doing it, and then he chickened out and let the Republicans and conservative Democrats pretend that giving fair trials to people America had tortured would cause the terrorists under your beds to eat The Homeland's children. And beyond that, instead of having his Justice Department prosecuting war criminals or at least abrogating the policies the Bush League set while they were in office, Holder and friends have been defending them. And while they're probably not torturing prisoners any more, and there's a bit more adult supervision, they still haven't given these people fair trials, and there's a serious lack of transparency about how the official prisons in Iraq and Afghanistan are treating prisoners, much less about whether they're still running unofficial secret prisons.
Warrantless Wiretapping - As with war crimes, the Justice Department is defending this set of Bush Policies, because the folks they work for like to avoid any legal and Constitutional restrictions on arbitrary surveillance and prosecution.
Extrajudicial Assassination By Executive Order - No, Obama didn't promise that he'd do it while he was out campaigning, he just announced it after he got into office. I suppose he gets some transparency points for admitting it; even Darth Cheney Himself wouldn't have said he was going to have people assassinated, he would have just done it and kept it hidden.
Immigration reform - there's a lot that could and should have been done to make La Migra treat people fairly and openly, and to fix the immigration-detention prisons which are an offense to civilized society. And Obama's kept them as part of the Homeland Security Mafia which should have been broken up. However, the fundamental questions are more political - some people think "reform" means sending all the brown people back to Mexico even if they're not from there, and some people think it means having Congress follow its Constitutionally mandated duty of setting up processes for naturalizing immigrants, and the right-wing propaganda machine has been pushing anti-immigrant hatred for years, so it's been tough for moderate Republicans to say anything (and on this issue, Bush was a moderate, even if it was just because he liked cheap imm
Imagine if your attack dogs and trigger-happy roommate were espresso fiends?
As of a week or two ago, the Usual Internet Pundits were reporting that spam was back up to its Pre-Christmas-Break levels. December and January may still count as low-volume months, because the botnets took two weeks off, but the bots are rested, relaxed, and back at work making the Internets a profitable place for blood-sucking parasites again.
One of the more serious problems with the military-industrial complex's development process, besides obvious little things like threatening to kill millions of people and possibly initiate nuclear winter, is that it takes a large number of scientists and engineers and diverts them away from useful civilian technology and diverts their talents to working on projects that ideally will never be used, and hides any parts of that work that could be useful away where the public can't use it.
There are occasionally useful technologies that escape - this "Internet" thing really is more convenient than uucp and Usenet were, and GPS is really cool but there are other ways to implement wide-area navigation systems without satellites. But they guys who were making tank engines 20% more efficient could have been doing that for truck engines or car engines, and the people working on improving small supersonic airplanes could have been improving civilian passenger or cargo airplanes instead.
It must not be one of ours, then!
But seriously, American stealth bombers were designed to work well over oceans and Russian terrain, and apparently didn't work so well over open desert terrain.
Ok, it's mostly crowded with spam and pr0n\\\\binaries, and ISPs have mostly stopped providing news service as a standard feature of an account, and I haven't had a decent NNTP reader in a decade or more, but yeah, Usenet's still around. I stopped being able to read all of it (printed on paper, 4-up double-sided) some time in the 80s, stopped being able to read more than a couple of newsgroups later in the 90s, but Google Groups still provides access if I need to look for things, and the last time I checked Google still had DejaNews articles with spotty coverage of stuff I'd written almost three decades ago.
It's more like the Kennedy assassination - who wouldn't gain by smearing Wikileaks here? Even Wikileaks themselves* might have planted it as a diversion as opposed to surreptitiously leaving it behind. Or maybe it's a Murder on the Orient Express plot, where either a whole bunch of players conspired together to do it, or else some stranger walked in the door, planted it, and walked out unseen.
*Yes, I do reject any of the conspiracy suggestions that say Kennedy himself was behind it, except the one on Red Dwarf which might have been true, but between several Mafia families, the CIA, Cuba, anti-Castro Cubans, the Pentagon, Military-Industrial Complex businesses, several jealous ex-husbands, Bobby, Jackie, Frankie, Marilyn, J.Edgar, J.Edgar's dress-maker, and the Lone Gunmen, it really was a race to get there first....
If it's actually related to Wikileaks, as opposed to a US-or-Euro-government spook job, it's more likely to be a Tor node. For that matter, even if it is a CIA plant, it could well be a Tor node, and similarly, if it's a fake scapegoat machine that the former bank minister is using to cover his tracks, a Tor node would be a good choice.
Yup. It could just as easily have been left there by the former third assistant clerk to the Finance Minister, who got sacked when Iceland's banking system collapsed, and who was too polite to take his severance pay in used hardware.
If you're working in a given field, there may be problems that are more like the one you're working on than 3-SAT, so you can reduce to/from them, which will often be much easier and more efficient to prove, even if it's a less efficient way to solve 3-SAT. If your goal is theoretical, that's fine - Reduce FOO to BAR, BAR is known to be NP-Complete, Deliver Thesis.
If your goal is practical, because you want to solve real instances of FOO, tell you it's NP-hard may say you shouldn't try to find the optimal solution but look for near-optimal heuristics, or maybe you should reduce it to BAR, which already has a good near-optimal heuristic or has an optimal solution that's usually but not always fast. Or it may be that knowing that FOO is NP-hard tells you to give up and solve a different problem instead (e.g. in cryptography, where inexact solutions are useless so maybe you should put a keylogger in your enemy's keyboard or drug the courier who's got the one-time pads instead.)
To be precise, probably nobody's built one on purpose...
If you're asking whether non-determinism exists in the physical world, that's really a metaphysical question, and you should ask a philosopher or your local quantum mechanic. In the cryptography business, the closest related problem is "If you've stolen a key from your target, can you tell if it's the right one?"
The original Turing machines had infinitely long tapes, which is easy to do if you don't have to build one of them. Since the original work in NP-Completeness, there have been a bunch of further problem classes defined that may constrain the size of the Turing machine, e.g. PSPACE problems with can only be run on a system with space that's bounded by a polynomial function of the size of the problem, so you potentially could build them for some reasonable sets of problems. More years, more PhD theses, more professors needing to publish papers, more problem categories.
R's a pretty schmart guy, and while I haven't mean S or A, I'd bet that's true about them as well.
N = PQ, where P and Q are primes. If you know P and Q, you can determine the encryption and decryption keys in polynomial time, and use them in polynomial time, which is why using RSA at all is practical. If an oracle gives you p and q, you can determine in polynomial time whether N = pq, therefore RSA is in NP. The best-known algorithms for factoring are around e^(n/3), which means that you can make it the work your attacker needs to do exceed the predicted lifetime of your planet while still only needing to do small amounts of work yourself, so that means that RSA provides security while remaining practical.
If P=NP, then there is an algorithm to determine P and Q from N in polynomial time, and therefore an attacker can determine your keys in polynomial time, so you're not secure. It may be that the polynomial is something large and annoying, like O(N^10) to crack vs. O(N^4) to generate keys, in which case a defender with moderate resources might still be able to protect her data against an attacker with relatively large resources, but it's more likely that a defender wouldn't be able to create practical-sized keys with age-of-the-planet attack times.
Factoring is not believed to be NP-complete, so it's possible that somebody could solve factoring without solving 3-SAT, but this guy's apparently claiming to be able to solve 3-SAT, at least to accuracy-of-the-media levels of interestingness.
The secure channel for a one-time pad is a guy with a briefcase handcuffed to his arm, optionally wearing a tuxedo or a uniform or accompanied by an armed guard. Occasionally there are other options, such as a pressurized conduit between nearby buildings, with the data carried over a fiber-optic system, but that's also depending on physical security for protection.
If you've transmitted your code pad over any physically eavesdroppable medium, it's no longer a one-time pad, it's just a chunk of data encrypted with whatever encryption algorithm the transmission medium used, no matter what the sales guy for the "one-time pad" company told you.
> You appear to have used a sociological argument as proof of a mathematical statement.
Absolutely correct!
> You fail.
No. It's not meant to be a conclusive proof, it's just the way to bet. A proof that P=NP would be Really Cool, and do all kinds of really useful things for the Real World as well as for mathematicians, even though for a cryptographer or computer security designer it would be a major pain in the ass\\\\\\\\\ New Business Opportunity.
We've already got to deal with Quantum Computers as a potential future threat model, so we're not forgetting how to do hashes and Key Distribution Centers, and making sure to design protocols that let you use longer key sizes if you need them, and if P=NP we'll have to live with that as well, though it probably tips the balance to make it possible for a government-sized attacker to beat a PC-using communicator, as opposed to today when it's the other way around.
I've already been through this sort of thing before. I was an operations researcher in college, and a couple of years after I graduated, Karmarkar came out with his linear programming algorithm, which was in P rather than exponential like Dantzig's Simplex algorithm. On the other hand, simplex was usually pretty fast, and almost never in the slow cases for real problems, and Karmarkar's was something like O(n^6), which was annoyingly slow and large for real problems, but computers have been gotten a lot faster in the last three decades. On another hand, the Internet and computerized typesetting have made the Net.Kook problem much harder than the days that kooks had to use carbon paper and bad typewriters.
Sure, there are problems that are exponentially hard that you can still often solve for small n, and there are problems that are exponentially hard in the worst case but usually only take polynomial time if you're lucky, and sometimes you can depend on usually being lucky, and there are problems that are exponentially hard if you need the best answer, but have polynomial solutions that will get you within X% of the best answer, which may be good enough.
Cryptography is not any of those problems - you can solve for small n, so the crypto designer just uses a key that's long enough not to be small, and maybe encryption takes twice as long but cracking takes 2^100 times as long. Inexact answers are good enough for the Travelling Salesman Problem, because taking 50% longer to reach all your destinations is still feasible, but guessing one bit wrong in a crypto key usually means that half the output bits are different and you don't know which ones.
My department once had a bunch of physicists writing simulation code, because some of what they were simulating behaved in physics-like ways. I was running the computer, because that was back when you often wanted Computer Nerds to do that for you, though I was really a simulation jock and math nerd.
They were in fact using linear searches through a linked list to manage their event queue in O(n^2) time, and when I made them use a heap to get O(n log n) behaviour, I was disappointed that it only sped up their system by a factor of 5; apparently their code was doing some work besides managing the event list. Also, the system they were modelling basically bounced randomly around a large matrix that didn't fit into our huge 4MB RAM (this was ~1984), and crawling through the linked lists got them some physical locality so it wasn't always paging. A couple of years into the project, memory technology and price had improved enough that we were able to upgrade the VAX to 16MB, and suddenly the program could run in an hour instead of a week, though by that time we'd been able do enough research to tell the end user that the solution we were modelling wasn't really a good one, so being able to run a few hundred more examples a week let us pile on results to help convince them.
be a shame if it never finished, or took longer than the age of the universe on a computer the size of a planet before you got an answer.
You want an answer before you need to get your PhD. thesis written, maybe we can fix somethin' for you.
Lots of really smart mathematicians have been trying to find proofs that P==NP for a long time, and they've got lots of good tools to work with. None of them have succeeded. They've also been trying to prove that P!=NP, but that's probably much harder to prove, or at least to validate, since a constructive proof that P=NP has lots of testable examples.
Occasionally people make assertions that they've got a proof that either P==NP, or P!=NP; if they're smart they get them peer-reviewed and find the mistake, but maybe they get to improve our understanding of the general problem or some more specific hard problem, so at least they get a paper out of it. If they're not smart, they just publish it on the InterWebs, and either become net.kooks or have someone gently explain to them how the academic research process works, but the fact that they don't know suggests that they haven't read all the standard research. If they're greedy, they try to patent it, and if it gets past the Patent Examiners they can try selling it to a Patent Troll.