What you say is true, but it's mathematically much easier to explore the boundary between poly-time and super-poly-time than it is to work with the real-world constraints you describe. In practice, anything with a super-polynomial difficulty can be made too hard for your attacker with an appropriate keysize; people are less likely to be confident of that with poly-time problems.
Factorisation is super-polynomial but sub-exponential. I don't think Moore's Law will be threatening 4096-bit keys for some time to come... --
Basically, it means you can break a file of length L into N chunks each of length L/M, such that only M chunks are needed to reconstruct the file. It's exactly the right thing for these circumstances. --
The trouble with news is one lost article screws your download. But that's what error correction is for! A simple Hamming code allows you to, say, break the file into 26 data shares and add 5 error-correcting shares such that the file can be reconstructed after one share is lost; you can do better with more sophisticated error correction schemes.
I haven't seen any P2P proposals which make use of error correction technology, and it does seem like it might be useful. --
Misdesign of the USPTO database means I can't follow your link; everyone will have to do their own search. Oh well, that they're idiots we knew.
However, it looks as if the one relevant live trademark, held by "SSH Communications Security", is I think meant to cover the name as well as the logo: thus the opening line "Word Mark: SSH" and the "Mark Drawing Code: (5) WORDS, LETTERS, AND/OR NUMBERS IN STYLIZED FORM". --
Thanks! This gives me a lot to think about. Here's how I'd attack the problems you raise, though as I say I'm no expert and this could be nonsense.
On cheap mics. Bear in mind that you help the software out with calibration: play the mic a tuning fork and let the software figure out the parameters of the distortion compensation. Sure, tolerances will have to be higher than those of the cheapest mics to remove pure random noise (eg thermal noise), but software could still improve the mics.
On active soundproofing. First, renting a soundproof room is really expensive and inconvenient for lots of musicians who'd rather record in their bedroom. So it doesn't have to be all that good or all that cheap before people will use it. Second, I'm hoping that we can make mikes cheaper! Third, I'm assuming that processing power is basically free, since it halves in price every eighteen months. Fourth, in theory the software might be able to do its own setup; set the mikes up, leave the room for 20 minutes, and the software uses the noise it's supposed to be cancelling to figure out the relative positions of the microphones and the cancellation parameters.
The difference doesn't have to be negligible. The quality might be worse. As we move away from the world of big budget record company bonanzas, we'll see more people sacrificing quality for savings in money and convenience. --
First, I won't be that surprised if we start hearing a lot more music made with lower production values.
It would be cool, though, if software could be used to make good mikes cheaper, or to solve the soundproofing problem. Could we build directional mikes with interferometary implemented on the PC? Is there a way of making mikes cheaper that introduces a systematic distortion that could be undone after capture? Could we do "active soundproofing" with extra mikes away from the main mike, that capture information about what extraneous noise will be arriving so it can be dulled in postprocessing?
In general, the purely digital end of things improves with Moore's Law and gets cheap fast while the analogue end improves very slowly and stays expensive. If there were ways of pushing the burden over to the digital end to make the analogue end easier, that could be a route to making things cheaper.
Imagine for a moment that the disk in the DVD weighed *far more* than the ISS. Imagine it's a huge disk, floating in the vacuum of space on perfect bearings, and the ISS is just a thin shell around it. Now motors attached to the thin shell introduce torsion on the bearings: surely the shell will spin, not the disk?
Microsoft do lots of evil things, but when was the last time you heard of them threatening to sue competitors over a patent or trademark? That's not really the way they operate. You're thinking of Apple, or IBM, or another such litigous nasty.
And it sounds like, in this instance, they're in the right. Much as I loathe them, this isn't the way I'd like to see them lose. --
I think there are just as many gay people in whatever profession, but you're more likely to come out if you're in computing, because it's less likely to hurt your career.
And ISTR the "Stanford guy" is Paul Asente, who was once a regular poster to soc.motss (and may still be for all I know). I once asked him in email "is X your fault?" He replied "not entirely" --
Ron Rivest indicated he was happy to generate an RSA challenge for anyone who thought they had a break. Why don't you ask him for a challenge, break it, and then the world will believe you?
Alternatively, piss off and stop spreading FUD. --
RSA is built on the assumption that the RSA problem is hard. This would imply point 3, and it would imply that factoring is hard, but RSA might still be strong even if both of your points 1 and 2 were false. In fact I don't think factoring is believed to be NP-complete, but it is believed to be outside P. --
1. Yes, factorisation is the most effective attack on RSA known by far. Well, there's other stuff like low exponent attacks or chosen-ciphertext attacks which you can avoid with good practice, but factoring is the best approach given only the public key and one ciphertext.
2. I define "really hard" as "intractable": ie "yielding to no polynomial-time algorithm" or "outside P" in short. Assuming P != NP, I see no reason to believe that all problems in NP but outside P will be NP-complete.
3. We currently have no means to prove any cryptographic problem intractable. Thus the best we can do is base our cryptosystems on the best-tested assumptions. The RSA problem is certainly one of the best studied problems in cryptography. --
I've become wary of people who deliberately post misapprehensions because they think that helpfulness is laughable; I got a bit paranoid there. Glad to know I was wrong.
You just don't know anything about peer review, do you? How many of these sorts
of activities have you participated in?
Ian Goldberg is just one of the best crypto-hackers out there: I can't think of anyone else who combines his level of original contribution to cryptographic theory with such prodigious creation of useful free software for crypto purposes. I suspect that if he's complaining of insufficient access to the standards process for cryptanalytic purposes, he does so with good reason. --
The TSP problem is "is there a path within this threshold?". it's in NP because there's an obvious poly-time algorithm for determining whether a particular path is no longer than the threshold.
For some reason optimisation problems are the most popular examples of NP-complete problems, but they're harder to think about than simple decision problems, because you have to look at them through this layer of abstraction. NP problems don't ask "what's the best you can do", they ask "can this be done?", so for an optimisation problem you have a family of questions "can this be done in 100 miles of travel?", "can this be done in 50 miles?" and so on. --
"Less than exponential time" != "polynomial time". Factoring is slower than polynomial time but faster than exponential time.
"breaking RSA" != "recovering the private key". You're right that recovering the private key allows you to factor N. But it hasn't been proven that being able to recover the plaintext to arbitrary ciphertext given only the public key gives you a way to find the private key, and so in that sense RSA is not provably as hard as factoring. Some other cryptosystems, like Rabin and Blum-Blum-Shub, have this property. --
This is a troll, but for the benefit of those who might be misled:
Problems in NP have yes/no answers, and the question can always be cast as "is there a string with this property?" where you can check a candidate string in P time (on the size of the problem). In this sense, the TSP doesn't ask "what's the shortest route?". It asks "is there a route shorter than this?"
NP-complete problems are as hard as any in NP: given any problem in NP, you can re-cast it as an instance of the Travelling Salesman problem (in polynomial time), so if you solve TSP, you effectively solve all of NP, and thus proven that P = NP.
Factoring is neither proven in P nor proven NP-complete. --
The GPL is of course a license, and it takes a special kind of brain damage to think it isn't. But it's a license designed to achieve RMS's tool of maximising software freedom, so it's a political tool to that end.
It's funny how those who GPL their code get more heat from the likes of idiot you replied to than closed source software providers who give us less freedom with their code. --
At the time of/.'s creation, I'm pretty sure Perl was the only Open Source language with sufficiently mature support for that sort of thing. I suspect that complaint was just a troll. --
"What, the term that says we own everything you ever think of while you work for us, even if it's a recipe for cookies? The one that says you must never sue us? The one that says we can claim the money off you if you make a mistake that we feel loses us money? Those are perfectly standard terms. Any contract would have them; they're normal throughout the industry. Don't be so unreasonable and difficult; show a little trust. Sign."
*Don't* sign. Those terms are not normal. I have had contracts modified before starting work because the terms are overbroad. My current contract does not contain any overbroad terms (and I had that clarified too). I recently read my flatmate's contract and it contained no overbroad or nasty terms. Don't let an employer fob you off with this nonsense; nasty contracts are a sign of contempt for the employees and if they're not prepared to fix the problems, if they expect all the trust to be on your side, then you don't want to work there. Look elsewhere.
I've never been shown a contract until after informal acceptance of an offer myself, but *next* time I'm going to insist on seeing the contract before coming to a second interview. I've seen some incredibly nasty ones, and I don't want to get my hopes worked up about a job I find myself unable to accept. --
Slashdot Mirror
Snopes has the true story of the space pen. Interesting story, it's nice to know the truth.
--
What you say is true, but it's mathematically much easier to explore the boundary between poly-time and super-poly-time than it is to work with the real-world constraints you describe. In practice, anything with a super-polynomial difficulty can be made too hard for your attacker with an appropriate keysize; people are less likely to be confident of that with poly-time problems.
Factorisation is super-polynomial but sub-exponential. I don't think Moore's Law will be threatening 4096-bit keys for some time to come...
--
I had thought of IDA as a secret sharing scheme like Shamir's. Thanks for bringing this to my attention!
I found the original paper:
MICHAEL O RABIN : Efficient Dispersal of Information for Security, Load Balancing, and Fault Tolerance
Basically, it means you can break a file of length L into N chunks each of length L/M, such that only M chunks are needed to reconstruct the file. It's exactly the right thing for these circumstances.
--
The trouble with news is one lost article screws your download. But that's what error correction is for! A simple Hamming code allows you to, say, break the file into 26 data shares and add 5 error-correcting shares such that the file can be reconstructed after one share is lost; you can do better with more sophisticated error correction schemes.
I haven't seen any P2P proposals which make use of error correction technology, and it does seem like it might be useful.
--
Misdesign of the USPTO database means I can't follow your link; everyone will have to do their own search. Oh well, that they're idiots we knew.
However, it looks as if the one relevant live trademark, held by "SSH Communications Security", is I think meant to cover the name as well as the logo: thus the opening line "Word Mark: SSH" and the "Mark Drawing Code: (5) WORDS, LETTERS, AND/OR NUMBERS IN STYLIZED FORM".
--
I believe the expression is "w00t!"
--
Thanks! This gives me a lot to think about. Here's how I'd attack the problems you raise, though as I say I'm no expert and this could be nonsense.
On cheap mics. Bear in mind that you help the software out with calibration: play the mic a tuning fork and let the software figure out the parameters of the distortion compensation. Sure, tolerances will have to be higher than those of the cheapest mics to remove pure random noise (eg thermal noise), but software could still improve the mics.
On active soundproofing. First, renting a soundproof room is really expensive and inconvenient for lots of musicians who'd rather record in their bedroom. So it doesn't have to be all that good or all that cheap before people will use it. Second, I'm hoping that we can make mikes cheaper! Third, I'm assuming that processing power is basically free, since it halves in price every eighteen months. Fourth, in theory the software might be able to do its own setup; set the mikes up, leave the room for 20 minutes, and the software uses the noise it's supposed to be cancelling to figure out the relative positions of the microphones and the cancellation parameters.
The difference doesn't have to be negligible. The quality might be worse. As we move away from the world of big budget record company bonanzas, we'll see more people sacrificing quality for savings in money and convenience.
--
First, I won't be that surprised if we start hearing a lot more music made with lower production values.
It would be cool, though, if software could be used to make good mikes cheaper, or to solve the soundproofing problem. Could we build directional mikes with interferometary implemented on the PC? Is there a way of making mikes cheaper that introduces a systematic distortion that could be undone after capture? Could we do "active soundproofing" with extra mikes away from the main mike, that capture information about what extraneous noise will be arriving so it can be dulled in postprocessing?
In general, the purely digital end of things improves with Moore's Law and gets cheap fast while the analogue end improves very slowly and stays expensive. If there were ways of pushing the burden over to the digital end to make the analogue end easier, that could be a route to making things cheaper.
Genuine question, is this a mistaken hope?
--
Imagine for a moment that the disk in the DVD weighed *far more* than the ISS. Imagine it's a huge disk, floating in the vacuum of space on perfect bearings, and the ISS is just a thin shell around it. Now motors attached to the thin shell introduce torsion on the bearings: surely the shell will spin, not the disk?
The earlier answer was correct.
--
Microsoft do lots of evil things, but when was the last time you heard of them threatening to sue competitors over a patent or trademark? That's not really the way they operate. You're thinking of Apple, or IBM, or another such litigous nasty.
And it sounds like, in this instance, they're in the right. Much as I loathe them, this isn't the way I'd like to see them lose.
--
I think there are just as many gay people in whatever profession, but you're more likely to come out if you're in computing, because it's less likely to hurt your career.
And ISTR the "Stanford guy" is Paul Asente, who was once a regular poster to soc.motss (and may still be for all I know). I once asked him in email "is X your fault?" He replied "not entirely"
--
If this is true, you can easily prove it.
Ron Rivest indicated he was happy to generate an RSA challenge for anyone who thought they had a break. Why don't you ask him for a challenge, break it, and then the world will believe you?
Alternatively, piss off and stop spreading FUD.
--
RSA is built on the assumption that the RSA problem is hard. This would imply point 3, and it would imply that factoring is hard, but RSA might still be strong even if both of your points 1 and 2 were false. In fact I don't think factoring is believed to be NP-complete, but it is believed to be outside P.
--
If the NP-complete problems are in P, all NP problems are in P, including factoring: that's what P=NP means.
--
1. Yes, factorisation is the most effective attack on RSA known by far. Well, there's other stuff like low exponent attacks or chosen-ciphertext attacks which you can avoid with good practice, but factoring is the best approach given only the public key and one ciphertext.
2. I define "really hard" as "intractable": ie "yielding to no polynomial-time algorithm" or "outside P" in short. Assuming P != NP, I see no reason to believe that all problems in NP but outside P will be NP-complete.
3. We currently have no means to prove any cryptographic problem intractable. Thus the best we can do is base our cryptosystems on the best-tested assumptions. The RSA problem is certainly one of the best studied problems in cryptography.
--
I've become wary of people who deliberately post misapprehensions because they think that helpfulness is laughable; I got a bit paranoid there. Glad to know I was wrong.
--
--
The TSP problem is "is there a path within this threshold?". it's in NP because there's an obvious poly-time algorithm for determining whether a particular path is no longer than the threshold.
For some reason optimisation problems are the most popular examples of NP-complete problems, but they're harder to think about than simple decision problems, because you have to look at them through this layer of abstraction. NP problems don't ask "what's the best you can do", they ask "can this be done?", so for an optimisation problem you have a family of questions "can this be done in 100 miles of travel?", "can this be done in 50 miles?" and so on.
--
You're substantially right. Two nitpicks:
"Less than exponential time" != "polynomial time". Factoring is slower than polynomial time but faster than exponential time.
"breaking RSA" != "recovering the private key". You're right that recovering the private key allows you to factor N. But it hasn't been proven that being able to recover the plaintext to arbitrary ciphertext given only the public key gives you a way to find the private key, and so in that sense RSA is not provably as hard as factoring. Some other cryptosystems, like Rabin and Blum-Blum-Shub, have this property.
--
Could you give references for any papers offering cryptanalysis of any version of the WEP protocol?
I'd also be curious to know more about your participation in the cryptographic community that you refer to - maybe we've met and I don't know it?
--
This is a troll, but for the benefit of those who might be misled:
Problems in NP have yes/no answers, and the question can always be cast as "is there a string with this property?" where you can check a candidate string in P time (on the size of the problem). In this sense, the TSP doesn't ask "what's the shortest route?". It asks "is there a route shorter than this?"
NP-complete problems are as hard as any in NP: given any problem in NP, you can re-cast it as an instance of the Travelling Salesman problem (in polynomial time), so if you solve TSP, you effectively solve all of NP, and thus proven that P = NP.
Factoring is neither proven in P nor proven NP-complete.
--
Wen U 1/2 to reed /. lik it wos writen bi Bascule thi Teller, it bicums a bit hard on thi Is.
--
The GPL is of course a license, and it takes a special kind of brain damage to think it isn't. But it's a license designed to achieve RMS's tool of maximising software freedom, so it's a political tool to that end.
It's funny how those who GPL their code get more heat from the likes of idiot you replied to than closed source software providers who give us less freedom with their code.
--
At the time of /.'s creation, I'm pretty sure Perl was the only Open Source language with sufficiently mature support for that sort of thing. I suspect that complaint was just a troll.
--
"What, the term that says we own everything you ever think of while you work for us, even if it's a recipe for cookies? The one that says you must never sue us? The one that says we can claim the money off you if you make a mistake that we feel loses us money? Those are perfectly standard terms. Any contract would have them; they're normal throughout the industry. Don't be so unreasonable and difficult; show a little trust. Sign."
*Don't* sign. Those terms are not normal. I have had contracts modified before starting work because the terms are overbroad. My current contract does not contain any overbroad terms (and I had that clarified too). I recently read my flatmate's contract and it contained no overbroad or nasty terms. Don't let an employer fob you off with this nonsense; nasty contracts are a sign of contempt for the employees and if they're not prepared to fix the problems, if they expect all the trust to be on your side, then you don't want to work there. Look elsewhere.
I've never been shown a contract until after informal acceptance of an offer myself, but *next* time I'm going to insist on seeing the contract before coming to a second interview. I've seen some incredibly nasty ones, and I don't want to get my hopes worked up about a job I find myself unable to accept.
--