Here (the University of Iowa'sDepartment of Computer Science), the general policy is that Wikipedia is not an academic reference and citing it will get you dinged hard. Reading the Wiki is fine, but you have to go to print media for citations--even preprints of journal articles are considered suspect and only accepted grudgingly.
In my experience talking to people at various institutions, very few places accept Wikipedia as a reference. I would suggest that you talk to your professors and ask them outright whether Wikipedia is an accepted reference in the department. It may prevent some unpleasant surprises in the future.
This is not actually good advice. When interviewed by federal agents, the proper response is I'd love to help, but I need to talk to my attorney first. I'll have him get in touch with you.
If you express an unwillingness to talk to the agents, that can be used to support warrants against you, on the grounds that it's indicative of some sort of suspicious behavior. If you express a willingness to talk but you assert your right to counsel before any conversation, they can't use that to support a warrant.
The key is to say this, to smile, to accept their business cards, to offer them a cup of coffee, to be sociable and cooperative without telling them anything. Once they're gone, call your lawyer and have your lawyer place the phone calls. If you and your lawyer decide that cooperation is called for, then your attorney will arrange a time to talk to the agents. If you and your lawyer decide to clam up, your lawyer will have a lot of experience in how to keep your silence from being used against you.
Any advice on how to deal with the FBI which does not reduce down to "get an attorney as soon as possible, and get real legal advice" is fundamentally broken.
(Note: I am not an FBI agent, but I have a lot of federal law-enforcement in the family.)
The average game quality may not have changed all that much over the years. In fact, it's probably slightly improved. But the issue is not about average game quality; it's about how large of a standard deviation we saw from that average. Let's say that we've got a hypothetical scale where games of the Pong era have an average quality rating of 0 and a sigma (standard deviation) of 2. Negative numbers are bad, positive numbers are good.
About two-thirds of all games will be in the range -2 (really, really blows) to +2 (really, really good). And about one game in twenty will be +4 (Pong, Tetris) or better. And about one game in twenty will be -4 (Custer's Revenge, anyone?) or worse. But the average is a zero.
Now let's say that in the present day average game quality is a 1 on the Pong scale. Wow! We've made an improvement! The average game of today is markedly, measurably better! But the beancounters from Corporate hate that sigma; sigma is something that an engineering process is supposed to reduce, after all. So while games today are markedly better on average, with a sigma of 0.5, only one game in a million will hit the +4 or -4 of Oregon Trail or Custer's Revenge.
So sure. The averages may be the same. But that's not the point. The point is the standard deviations have been killed by Corporate. The mad magician, the innovator, the two guys with a weird idea, those people are out of the system now. And the games industry is suffering for it, despite the fact that the average game quality is improving.
Me, I'll happily accept the existence of Custer's Revenge or Bad Street Brawler if it means I get a Zork or a System Shock 2. You can focus on the average if you like, but me, I like to buy games that sit out on the far-right tail of the normal distribution.:)
The proposition here is "upper management knows the code is a mess and is embarrassed by it, so they insist on keeping the code closed."
Who here thinks upper management knows what code looks like, at all? Not bad code, not good code, but code, period. Does anyone really believe that the executives who make policy decisions about whether to release code are in any way qualified to comment on code aesthetics?
Hell, I think most programmers are unqualified to comment on code aesthetics. For a lot of people, programming is just the daily grind. People who actually put their heart and soul into crafting a piece of mathematical art are very rare. So if management can't recognize good code and an awful lot of the IT department is apathetic to good code, how is it possible that the decisionmakers know enough to be embarrassed by the code?
And if we can realize this in just ten seconds of thinking, why didn't Schroeder think of it herself?
As near as I can tell, the reason why companies like closed source is very simple: it preserves the asymmetry of information necessary for their bottom line. A free market depends on both parties knowing the product being bought and sold. When you buy a new car, you can read Consumer Reports, you can read Car and Driver, you can read any of a dozen specialist automotive rags that will tell you in excruciating detail what a certain car's dual overhead cam configuration means in context of their competitor's choice for a single overhead cam. The buyer has complete access to information, and that puts the buyer in a position of strength.
Asymmetric information, where the seller knows far more than the buyer, puts the buyer in a position of weakness. If the product is a black box, then you can't really get an informed independent critique; you have to instead rely on the claims of the people selling the product. Which is great, as long as you're the seller.
A complete answer to this question requires a solid (graduate-level) grounding in computational theory.
However, I would point you to Lamport signatures as an example of a digital signature algorithm which is secure even against quantum computation.
Most symmetric algorithms are also secure against quantum computation. Using Grover's algorithm we can reduce the total symmetric keyspace we have to search by an exponential factor of 0.5. This means that a 256-bit keyspace becomes equivalent to a 128-bit keyspace--still totally infeasible.
RSA, DSA and Elgamal are all in serious trouble if superpositional computation comes to pass--and that's a very big if--but we are not without alternatives to those three old warhorses.
More to the point, whether something is a heuristic is a subjective decision based on the subjective value we assign to its approximation. Whether something is an algorithm is an objective assessment based on mathematically demonstrable facts.
Subjective versus objective. The two concepts are orthogonal to each other. As an example of a heuristic that's not an algorithm, if I believe that astrology is an effective tool for deciding what to do, then astrology is a heuristic. It's not an algorithm.
First, please see some comments I made a couple of levels up, outlining the definition of an algorithm according to Don Knuth, Thomas Cormen, Charles Leiserson, Ron Rivest and Cliff Stein, all of whom are world-class experts in algorithms.
The performance of an algorithm is determined by the space and time required for its execution. The Traveling Salesman Problem is an example: it requires a very small amount of space but a factorial amount of time. This is absolutely ridiculous. We have absolutely no idea of how to solve a general instance of the Traveling Salesman Problem using only reasonable computational resources.
But at the same time, there are simpler problems that are tractable because they require less resources. Annealing is an example of this. It turns out that while a perfect answer to a general TSP is far beyond our limited ability to solve, most instances we care about are actually pretty well described by this much simpler problem we do know how to solve. A heuristic, then, is simply using a light-demand algorithm in place of a heavy-demand algorithm, with the knowledge that the light-demand algorithm does not perfectly map to the heavy-demand algorithm.
For instance. If I asked you to list romantic red flowers, a correct answer would be millions of entries long. After all, 'romance' is in the eye of the beholder and there are a ton of plants out there with red flora. But if you were to instead think of the problem "list red flowers commonly given on Valentine's Day", you would pretty quickly chime in with "rose, carnation, orchid".
The problem of "list romantic red flowers" is intractable.
The problem of "list red flowers commonly given on Valentine's Day" is tractable.
Both are algorithms. The latter is a heuristic for approximating a solution to the former.
I'm a graduate student in CS right now. One of the things I'm researching is stochastic approximation heuristics. Without any argument, these are algorithms. They have to be algorithms, or else the Church-Turing Thesis doesn't apply and we wouldn't be able to have computers do them at all.
An algorithm is, broadly speaking, a terminating sequence of deterministic steps that effectively derives outputs from provided inputs. But don't believe me--after all, I'm just a random guy on Slashdot. But maybe Cormen, Leiserson, Rivest and Stein's Introduction to Algorithms should be believed:
Informally, an algorithm is any well-defined computational procedure that takes some value, or set of values, as input and produces some value, or set of values, as output.
Don Knuth has an equivalent definition of algorithm in The Art of Computer Programming. He makes explicit a couple of details which are implicit in the CLRS definition, but other than that they're interchangeable. Knuth talks about the effectiveness of algorithms, in that an algorithm must uphold the promises the programmer makes about it.
So now that we've got a decent definition of "algorithm", one that's approved by five of the brightest lights in computer science, let's look at simulated annealing. This is a stochastic (random) heuristic approximation process. You say it's not an algorithm, because sometimes it'll give barkingly wrong answers. I say it is. So let's look at our definition of algorithm, and see whether it is or not.
It's well-defined, in that every step of the process has mathematical clarity and precision. It's deterministic, in that if I feed it the exact same inputs (including initializing the pseudorandom number generator to the same seed value), I get the exact same outputs. It will always terminate, thanks to a counter that limits the annealing process to a couple of million operations. And finally, it is effective, in that it upholds the promises I, the programmer, make about the outputs.
According to your reasoning, it fails on the effectiveness criteria. It's not an algorithm because it doesn't solve NP-COMPLETE problems, it simply approximates them. But that's a straw man argument: I never claimed it solved NP-COMPLETE problems, therefore the effectiveness of the algorithm is not determined by whether it solves NP-COMPLETE problems.
According to the IBM design team, this is not so: while the NSA made technical suggestions, not one wire in the S-boxes was dictated by the NSA.
Other people have noticed that the "technical suggestions" involved the NSA sending back DES hardware with rewired S-boxes, and assumed the IBM DES crew simply used the NSA's new S-boxes without understanding what was going on. Quite the opposite: the IBM team refused to use anything they didn't understand, and thus independently discovered differential cryptanalysis by reverse-engineering the NSA's changed S-boxes.
Once they understood differential cryptanalysis, they came up with their own S-boxes.
I am a grad student in computer science. I have had to (try to) cryptanalyze DES before. It was the torment of the damned. My remarks here are based on that experience. I daresay it's a lot more than you've ever done with it.
DES is not now, nor has it ever been, a weak design except in the very narrow sense of it having only a 56-bit keyspace. During the time it was created, 56 bits of keyspace was really quite good. Nobody was expecting it to remain a government standard for the next 20+ years. When the only way to attack an encryption algorithm is to exhaust its keyspace, that encryption algorithm is generally considered to be pretty well-designed. Even the small keyspace can be fixed with 3DES, a trivial extension that gives somewhere between 112 and 168 bits of keyspace, depending on just how many trillions of dollars you're assuming the attacker is spending.
Insofar as its "weaknesses", all that I can think is that you're talking about how the S-boxes were hardened against differential cryptanalysis after the IBM design team independently discovered the attack. The NSA asked IBM to keep differential cryptanalysis quiet, and IBM did: but I don't see how you go from "it's specifically hardened against differential cryptanalysis" to "it has weaknesses the NSA knows about".
Please do not fearmonger with crypto when you don't even have the facts right.
Superpositional computation works very nicely against ECC and the discrete logarithm problem.
SC doesn't work against things in class NP-COMPLETE, but it's quite effective against many problems that are in NP but less than NP-COMPLETE. In fact, I'm scratching my head trying to find one that SC doesn't work against.
Also, the total number of qubits required is twice the number of bits in the key. While nontrivial, it is not as ridiculous as you're making it out to be. It's possible we'll have this in twenty years. Less, if engineering breakthroughs go our way; more, if they don't.
Thank you very much for the depth of your response. I wish I had more to say right now, but I'm going to have to spend some time just digesting your answers.:)
Some questions for a practicing cosmologist, then--please don't think that I'm looking for concrete and solid answers (except where such things unambiguously exist); I'm interested in opinion as much as fact, provided the two are carefully distinguished from each other.:)
So:
What do you think of Lee Smolin's The Trouble With Physics? Are his criticisms of string theory on target? What about how string theory has changed the culture of cosmology?
My understanding of science is that theories must explain observed phenomena, predict future phenomena, and provide realistic ways in which a theory may be falsified. Given that:
Is this a reasonable definition of what must go into a cosmological theory?
Can string theory be said to be a "theory" at all, given that with 10**500 possible different cosmoses it's possible to explain away any correlation or discorrelation just as "we're looking at the [right|wrong] universe"?
I'm not a cosmologist; my knowledge of physics is limited to the GR and QM I took as an undergrad. However, I always loved the background independence of GR. The last I heard, the various string theories were background dependent. Is this as big a problem as I suspect it is? If not, why not?
... As you can probably imagine, I have deep skepticism about string theory. However, all of these questions are sincere ones, and I would very much appreciate any light you can shed on them.
If it helps, I'm a Ph.D. candidate in computer science. You can use calculus in your answers without worrying about losing me, along with tensors and vectors and most any other mathematical tool that will help. You'll need to explain phrases like "Minkowski space" and whatnot, though.:)
And one final question, too: how can us CS nerds on our side of academia help you cosmology nerds on your side of academia?
It is not a provable one-way data cable unless you can also prove the serial port drivers on both sides aren't doing something hinky to get around the snipped wire. That explodes the amount of trusted code in the system.
It is also not an auditable one-way data cable unless you build taps into the RS-232 cable, and can somehow prove that those taps truly reflect the contents of the cable as opposed to whatever the system designers want it to reflect.
At USENIX/EVT06 last year a team from the University of Iowa presented a cheap one-way data cable you could make with off-the-shelf parts from Radio Shack. Total cost is about $5 (for bulk, maybe $10 if you're buying single units) and it is provably, auditably, one-way. It was originally developed for electronic voting, to allow for counting computers to communicate with webservers that post election results. An attacker compromising the webserver cannot attack the counting computer, because there is literally no return path.
It works with very high reliability up to about 9600 baud.
You may be able to use this to your benefit. Have an isolated system air-gapped from the rest of the network which listens for log events on a one-way data cable. While you're no longer guaranteed to be safe (since if a logging PC is compromised, an attacker could send compromised data to the syslog PC and perhaps cause some sort of mayhem), but the lack of a return path makes interactive attacks infeasible.
ObDisclosure: I am a graduate student at UI and know the guy who invented the data cable, although I am not associated with the gadget.
What I love about Slashdot armchair lawyers is their naive faith in the criminal justice system.
So you go to trial. So you're acquitted. But by the time you get acquitted, you're front page news in all the local newspapers. You're getting death threats. Your family is shunned. You get let go from your job because you're bringing too much controversy. Your life, not to put too fine a point on it, is fucked.
Hatfill has never been charged. Jewell was totally exonerated, as was De Lorean. Wen Ho Lee pleaded guilty to a minor count just to make the madness stop, and received a profuse apology from the bench for how he was mistreated.
Why do you think hidden-volume mode TrueCrypt is bogus?
Let's imagine that you've got a TrueCrypt container on your hard drive. The FBI gets a tip that you're involved in child porn. You get arrested. The DA has a jailhouse snitch who'll testify that you have kiddie porn. The DA has a forensicist who will testify that you've got an encrypted container on your disk drive. You don't want to be doing 10-to-25 in federal pound-me-in-the-ass prison, because you're a scrawny pimply-faced geek and you don't want to get married off to the biker with the most cigarettes. You tell the DA "... look, okay, here's the passphrase to my TrueCrypt container. See? There's just porn in there I was hiding from my wife! But everyone involved is over 18! Let me go! It's bogus!"
The DA just smiles at you and says... "I'd like to see the hidden container inside that TrueCrypt volume. My forensicist says oftentimes people do that with TrueCrypt."
You say "umm... there isn't a hidden container... there's nothing more there..."
The DA continues to smile. "Prove it to me."
You say "umm... I can't... that's exactly what TrueCrypt means when they say it's hidden... you can't prove it exists and you can't prove it doesn't exist..."
The DA rises from the table. "Say hi to your husband for me when you meet him."
Moral of the story: it is very, very important that you be able to prove the existence or nonexistence of your data.
Can you explain more of this please?
I don't know how to make it any simpler. If compositing encryption functions makes things harder to break, we'd expect two applications of ROT13 to be stronger than one application of ROT13. It doesn't work that way. And in an exactly similar way, two levels of AES may or may not be any better than a single layer of AES. Or one layer of Blowfish and one layer of 3DES. Or...
If you want to get more sophisticated than this, you need to take a collegiate math course focusing on group theory.
You can beat the numbers by refusing to play the numbers. Computers are infamous for leaking information. Side channel attacks are on the rise, interesting stuff is routinely discovered in swap files, use of keyloggers is up, etc., etc.
I'm a computer security Ph.D. candidate focusing in voting machines. It's amazing how much you can find in a supposedly secure system. Vendors love to say "we're using AES256 and we've got a FIPS certification!", but the reality is usually much different than what you see in the four-color glossies.
I am an NSF–funded researcher in computer security, focusing on electronic voting. Data privacy and confidentiality is very important to us, as you can imagine.
Your idea is quite terrible.
First, what do you mean by a file "without signature"? Take a zip archive as an example--even if you strip off the zip header, any forensicist worth his or her salt can figure out it's a zip archive, just because of the way the data is structured. Encrypted filesystems have structure, too. A data forensicist can recognize an encrypted container on the basis of its structure. (Some people have recommended to you TrueCrypt in hidden volume mode. This is bogus. I'll explain that if you want.)
Second, you appear to not understand how crypto works. Two layers are better than one, right? So double ROT13 encryption is stronger than single ROT13, right? You're running smack into a major, well-known area of crypto. A lot of ciphers do not composite themselves well. You are almost always better off just picking one algorithm with a strong keysize than a composition of multiple algorithms.
Third, how do you plan on managing all of your keys? Key management is a thorny enough problem in the best of times. By relying on multiple keys you're multiplying the problem immensely.
You really need to do some basic research in crypto.
Harder metal - more scratching with friction = looser parts and...
The Russian Army has used steel-cased cartridges for decades. Their weapon designs are predicated on an assumption of steel cases. You need a very tapered round to make a steel case work, since it doesn't have the elasticity of brass and a straight-wall design will have massive reliability problems. But in that case, the unreliability is a function of steel's elastic response to explosive deformation, not because it'll scratch the weapon chamber.
Also, I'm unaware of any credible source that says steel-jacketed rounds are "used so often in assassinations". If you can point to a historical assassination that took place with steel-jacketed rounds, I'd be interested in hearing it.
The 7.62x39 Russian round has a massive taper to it, which means you can get away with using just about anything for the cartridge. The round was designed that way for a reason; it was thought that, given the Soviet Union's relative lack of manufacturing ability, the ability to make cartridges out of damned near anything would outweigh the ballistic tradeoffs that went into the highly-tapered round.
NATO has always had excellent manufacturing resources. Thus, NATO has always used a very, very shallow taper. Typically, the cartridge wall is less than one degree off straight vertical. This means NATO has to use brass cartridges for reliable feeding--steel and other metals just won't cut it.
Moral of the story: don't use steel cartridges in anything that's got a shallow taper.
First, don't worry about struggling in your classes. Generally speaking, it's the people who struggle who succeed the most later. People who sail through their courses without ever having to challenge themselves tend to crash and burn in the Real World the first time they run into something bigger than they are. If you're struggling, keep struggling. Don't quit. Don't give up. You might discover you're capable of a lot more than you think--and that kind of growth experience will reward you big-time in the Real World. If it's any help, I'm a couple of months away from a Ph.D. and every single day I still have to fight like hell for the grades. It can either crush you, or you can learn how to savor it. I recommend the latter.
Second, have you emailed your advisor yet and arranged for an appointment?:)
Slashdot Mirror
You have never had me as an instructor.
Here (the University of Iowa's Department of Computer Science), the general policy is that Wikipedia is not an academic reference and citing it will get you dinged hard. Reading the Wiki is fine, but you have to go to print media for citations--even preprints of journal articles are considered suspect and only accepted grudgingly.
In my experience talking to people at various institutions, very few places accept Wikipedia as a reference. I would suggest that you talk to your professors and ask them outright whether Wikipedia is an accepted reference in the department. It may prevent some unpleasant surprises in the future.
This is not actually good advice. When interviewed by federal agents, the proper response is I'd love to help, but I need to talk to my attorney first. I'll have him get in touch with you.
If you express an unwillingness to talk to the agents, that can be used to support warrants against you, on the grounds that it's indicative of some sort of suspicious behavior. If you express a willingness to talk but you assert your right to counsel before any conversation, they can't use that to support a warrant.
The key is to say this, to smile, to accept their business cards, to offer them a cup of coffee, to be sociable and cooperative without telling them anything. Once they're gone, call your lawyer and have your lawyer place the phone calls. If you and your lawyer decide that cooperation is called for, then your attorney will arrange a time to talk to the agents. If you and your lawyer decide to clam up, your lawyer will have a lot of experience in how to keep your silence from being used against you.
Any advice on how to deal with the FBI which does not reduce down to "get an attorney as soon as possible, and get real legal advice" is fundamentally broken.
(Note: I am not an FBI agent, but I have a lot of federal law-enforcement in the family.)
The average game quality may not have changed all that much over the years. In fact, it's probably slightly improved. But the issue is not about average game quality; it's about how large of a standard deviation we saw from that average. Let's say that we've got a hypothetical scale where games of the Pong era have an average quality rating of 0 and a sigma (standard deviation) of 2. Negative numbers are bad, positive numbers are good.
:)
About two-thirds of all games will be in the range -2 (really, really blows) to +2 (really, really good). And about one game in twenty will be +4 (Pong, Tetris) or better. And about one game in twenty will be -4 (Custer's Revenge, anyone?) or worse. But the average is a zero.
Now let's say that in the present day average game quality is a 1 on the Pong scale. Wow! We've made an improvement! The average game of today is markedly, measurably better! But the beancounters from Corporate hate that sigma; sigma is something that an engineering process is supposed to reduce, after all. So while games today are markedly better on average, with a sigma of 0.5, only one game in a million will hit the +4 or -4 of Oregon Trail or Custer's Revenge.
So sure. The averages may be the same. But that's not the point. The point is the standard deviations have been killed by Corporate. The mad magician, the innovator, the two guys with a weird idea, those people are out of the system now. And the games industry is suffering for it, despite the fact that the average game quality is improving.
Me, I'll happily accept the existence of Custer's Revenge or Bad Street Brawler if it means I get a Zork or a System Shock 2. You can focus on the average if you like, but me, I like to buy games that sit out on the far-right tail of the normal distribution.
The proposition here is "upper management knows the code is a mess and is embarrassed by it, so they insist on keeping the code closed."
Who here thinks upper management knows what code looks like, at all? Not bad code, not good code, but code, period. Does anyone really believe that the executives who make policy decisions about whether to release code are in any way qualified to comment on code aesthetics?
Hell, I think most programmers are unqualified to comment on code aesthetics. For a lot of people, programming is just the daily grind. People who actually put their heart and soul into crafting a piece of mathematical art are very rare. So if management can't recognize good code and an awful lot of the IT department is apathetic to good code, how is it possible that the decisionmakers know enough to be embarrassed by the code?
And if we can realize this in just ten seconds of thinking, why didn't Schroeder think of it herself?
As near as I can tell, the reason why companies like closed source is very simple: it preserves the asymmetry of information necessary for their bottom line. A free market depends on both parties knowing the product being bought and sold. When you buy a new car, you can read Consumer Reports, you can read Car and Driver, you can read any of a dozen specialist automotive rags that will tell you in excruciating detail what a certain car's dual overhead cam configuration means in context of their competitor's choice for a single overhead cam. The buyer has complete access to information, and that puts the buyer in a position of strength.
Asymmetric information, where the seller knows far more than the buyer, puts the buyer in a position of weakness. If the product is a black box, then you can't really get an informed independent critique; you have to instead rely on the claims of the people selling the product. Which is great, as long as you're the seller.
A complete answer to this question requires a solid (graduate-level) grounding in computational theory.
However, I would point you to Lamport signatures as an example of a digital signature algorithm which is secure even against quantum computation.
Most symmetric algorithms are also secure against quantum computation. Using Grover's algorithm we can reduce the total symmetric keyspace we have to search by an exponential factor of 0.5. This means that a 256-bit keyspace becomes equivalent to a 128-bit keyspace--still totally infeasible.
RSA, DSA and Elgamal are all in serious trouble if superpositional computation comes to pass--and that's a very big if--but we are not without alternatives to those three old warhorses.
More to the point, whether something is a heuristic is a subjective decision based on the subjective value we assign to its approximation. Whether something is an algorithm is an objective assessment based on mathematically demonstrable facts.
Subjective versus objective. The two concepts are orthogonal to each other. As an example of a heuristic that's not an algorithm, if I believe that astrology is an effective tool for deciding what to do, then astrology is a heuristic. It's not an algorithm.
I almost agree with you.
First, please see some comments I made a couple of levels up, outlining the definition of an algorithm according to Don Knuth, Thomas Cormen, Charles Leiserson, Ron Rivest and Cliff Stein, all of whom are world-class experts in algorithms.
The performance of an algorithm is determined by the space and time required for its execution. The Traveling Salesman Problem is an example: it requires a very small amount of space but a factorial amount of time. This is absolutely ridiculous. We have absolutely no idea of how to solve a general instance of the Traveling Salesman Problem using only reasonable computational resources.
But at the same time, there are simpler problems that are tractable because they require less resources. Annealing is an example of this. It turns out that while a perfect answer to a general TSP is far beyond our limited ability to solve, most instances we care about are actually pretty well described by this much simpler problem we do know how to solve. A heuristic, then, is simply using a light-demand algorithm in place of a heavy-demand algorithm, with the knowledge that the light-demand algorithm does not perfectly map to the heavy-demand algorithm.
For instance. If I asked you to list romantic red flowers, a correct answer would be millions of entries long. After all, 'romance' is in the eye of the beholder and there are a ton of plants out there with red flora. But if you were to instead think of the problem "list red flowers commonly given on Valentine's Day", you would pretty quickly chime in with "rose, carnation, orchid".
The problem of "list romantic red flowers" is intractable.
The problem of "list red flowers commonly given on Valentine's Day" is tractable.
Both are algorithms. The latter is a heuristic for approximating a solution to the former.
I'm a graduate student in CS right now. One of the things I'm researching is stochastic approximation heuristics. Without any argument, these are algorithms. They have to be algorithms, or else the Church-Turing Thesis doesn't apply and we wouldn't be able to have computers do them at all.
An algorithm is, broadly speaking, a terminating sequence of deterministic steps that effectively derives outputs from provided inputs. But don't believe me--after all, I'm just a random guy on Slashdot. But maybe Cormen, Leiserson, Rivest and Stein's Introduction to Algorithms should be believed:
Don Knuth has an equivalent definition of algorithm in The Art of Computer Programming. He makes explicit a couple of details which are implicit in the CLRS definition, but other than that they're interchangeable. Knuth talks about the effectiveness of algorithms, in that an algorithm must uphold the promises the programmer makes about it.
So now that we've got a decent definition of "algorithm", one that's approved by five of the brightest lights in computer science, let's look at simulated annealing. This is a stochastic (random) heuristic approximation process. You say it's not an algorithm, because sometimes it'll give barkingly wrong answers. I say it is. So let's look at our definition of algorithm, and see whether it is or not.
It's well-defined, in that every step of the process has mathematical clarity and precision. It's deterministic, in that if I feed it the exact same inputs (including initializing the pseudorandom number generator to the same seed value), I get the exact same outputs. It will always terminate, thanks to a counter that limits the annealing process to a couple of million operations. And finally, it is effective, in that it upholds the promises I, the programmer, make about the outputs.
According to your reasoning, it fails on the effectiveness criteria. It's not an algorithm because it doesn't solve NP-COMPLETE problems, it simply approximates them. But that's a straw man argument: I never claimed it solved NP-COMPLETE problems, therefore the effectiveness of the algorithm is not determined by whether it solves NP-COMPLETE problems.
According to the IBM design team, this is not so: while the NSA made technical suggestions, not one wire in the S-boxes was dictated by the NSA.
Other people have noticed that the "technical suggestions" involved the NSA sending back DES hardware with rewired S-boxes, and assumed the IBM DES crew simply used the NSA's new S-boxes without understanding what was going on. Quite the opposite: the IBM team refused to use anything they didn't understand, and thus independently discovered differential cryptanalysis by reverse-engineering the NSA's changed S-boxes.
Once they understood differential cryptanalysis, they came up with their own S-boxes.
I am a grad student in computer science. I have had to (try to) cryptanalyze DES before. It was the torment of the damned. My remarks here are based on that experience. I daresay it's a lot more than you've ever done with it.
DES is not now, nor has it ever been, a weak design except in the very narrow sense of it having only a 56-bit keyspace. During the time it was created, 56 bits of keyspace was really quite good. Nobody was expecting it to remain a government standard for the next 20+ years. When the only way to attack an encryption algorithm is to exhaust its keyspace, that encryption algorithm is generally considered to be pretty well-designed. Even the small keyspace can be fixed with 3DES, a trivial extension that gives somewhere between 112 and 168 bits of keyspace, depending on just how many trillions of dollars you're assuming the attacker is spending.
Insofar as its "weaknesses", all that I can think is that you're talking about how the S-boxes were hardened against differential cryptanalysis after the IBM design team independently discovered the attack. The NSA asked IBM to keep differential cryptanalysis quiet, and IBM did: but I don't see how you go from "it's specifically hardened against differential cryptanalysis" to "it has weaknesses the NSA knows about".
Please do not fearmonger with crypto when you don't even have the facts right.
This has never been proven.
If you can solve DLP, then you can solve IFP, that much is known to be true. We don't know that solving IFP will necessarily lead to solving DFP.
Superpositional computation works very nicely against ECC and the discrete logarithm problem.
SC doesn't work against things in class NP-COMPLETE, but it's quite effective against many problems that are in NP but less than NP-COMPLETE. In fact, I'm scratching my head trying to find one that SC doesn't work against.
Also, the total number of qubits required is twice the number of bits in the key. While nontrivial, it is not as ridiculous as you're making it out to be. It's possible we'll have this in twenty years. Less, if engineering breakthroughs go our way; more, if they don't.
Thank you very much for the depth of your response. I wish I had more to say right now, but I'm going to have to spend some time just digesting your answers. :)
So:
- What do you think of Lee Smolin's The Trouble With Physics? Are his criticisms of string theory on target? What about how string theory has changed the culture of cosmology?
- My understanding of science is that theories must explain observed phenomena, predict future phenomena, and provide realistic ways in which a theory may be falsified. Given that:
- Is this a reasonable definition of what must go into a cosmological theory?
- Can string theory be said to be a "theory" at all, given that with 10**500 possible different cosmoses it's possible to explain away any correlation or discorrelation just as "we're looking at the [right|wrong] universe"?
- I'm not a cosmologist; my knowledge of physics is limited to the GR and QM I took as an undergrad. However, I always loved the background independence of GR. The last I heard, the various string theories were background dependent. Is this as big a problem as I suspect it is? If not, why not?
... As you can probably imagine, I have deep skepticism about string theory. However, all of these questions are sincere ones, and I would very much appreciate any light you can shed on them.If it helps, I'm a Ph.D. candidate in computer science. You can use calculus in your answers without worrying about losing me, along with tensors and vectors and most any other mathematical tool that will help. You'll need to explain phrases like "Minkowski space" and whatnot, though.
And one final question, too: how can us CS nerds on our side of academia help you cosmology nerds on your side of academia?
It is not a provable one-way data cable unless you can also prove the serial port drivers on both sides aren't doing something hinky to get around the snipped wire. That explodes the amount of trusted code in the system.
It is also not an auditable one-way data cable unless you build taps into the RS-232 cable, and can somehow prove that those taps truly reflect the contents of the cable as opposed to whatever the system designers want it to reflect.
(a) snipping RX doesn't make the cable auditable or provable.
(b) serial cards are cheap.
At USENIX/EVT06 last year a team from the University of Iowa presented a cheap one-way data cable you could make with off-the-shelf parts from Radio Shack. Total cost is about $5 (for bulk, maybe $10 if you're buying single units) and it is provably, auditably, one-way. It was originally developed for electronic voting, to allow for counting computers to communicate with webservers that post election results. An attacker compromising the webserver cannot attack the counting computer, because there is literally no return path.
It works with very high reliability up to about 9600 baud.
You may be able to use this to your benefit. Have an isolated system air-gapped from the rest of the network which listens for log events on a one-way data cable. While you're no longer guaranteed to be safe (since if a logging PC is compromised, an attacker could send compromised data to the syslog PC and perhaps cause some sort of mayhem), but the lack of a return path makes interactive attacks infeasible.
ObDisclosure: I am a graduate student at UI and know the guy who invented the data cable, although I am not associated with the gadget.
See my remark to another poster. Your faith in the criminal justice system is quite badly misplaced.
What I love about Slashdot armchair lawyers is their naive faith in the criminal justice system.
So you go to trial. So you're acquitted. But by the time you get acquitted, you're front page news in all the local newspapers. You're getting death threats. Your family is shunned. You get let go from your job because you're bringing too much controversy. Your life, not to put too fine a point on it, is fucked.
You may want to look into Wen Ho Lee, Steven Hatfill, Richard Jewell and John De Lorean, all of whom had this exact thing happen to them.
Hatfill has never been charged. Jewell was totally exonerated, as was De Lorean. Wen Ho Lee pleaded guilty to a minor count just to make the madness stop, and received a profuse apology from the bench for how he was mistreated.
Also, have you been following what happened in Durham, North Carolina recently with respect to prosecutorial misconduct in a rape case?
You really, really need to acquaint your beliefs on how the law works with the reality of how the law works.
The DA just smiles at you and says... "I'd like to see the hidden container inside that TrueCrypt volume. My forensicist says oftentimes people do that with TrueCrypt."
You say "umm... there isn't a hidden container... there's nothing more there..."
The DA continues to smile. "Prove it to me."
You say "umm... I can't... that's exactly what TrueCrypt means when they say it's hidden... you can't prove it exists and you can't prove it doesn't exist..."
The DA rises from the table. "Say hi to your husband for me when you meet him."
Moral of the story: it is very, very important that you be able to prove the existence or nonexistence of your data.I don't know how to make it any simpler. If compositing encryption functions makes things harder to break, we'd expect two applications of ROT13 to be stronger than one application of ROT13. It doesn't work that way. And in an exactly similar way, two levels of AES may or may not be any better than a single layer of AES. Or one layer of Blowfish and one layer of 3DES. Or...
If you want to get more sophisticated than this, you need to take a collegiate math course focusing on group theory.
You can beat the numbers by refusing to play the numbers. Computers are infamous for leaking information. Side channel attacks are on the rise, interesting stuff is routinely discovered in swap files, use of keyloggers is up, etc., etc.
I'm a computer security Ph.D. candidate focusing in voting machines. It's amazing how much you can find in a supposedly secure system. Vendors love to say "we're using AES256 and we've got a FIPS certification!", but the reality is usually much different than what you see in the four-color glossies.
I am an NSF–funded researcher in computer security, focusing on electronic voting. Data privacy and confidentiality is very important to us, as you can imagine.
Your idea is quite terrible.
First, what do you mean by a file "without signature"? Take a zip archive as an example--even if you strip off the zip header, any forensicist worth his or her salt can figure out it's a zip archive, just because of the way the data is structured. Encrypted filesystems have structure, too. A data forensicist can recognize an encrypted container on the basis of its structure. (Some people have recommended to you TrueCrypt in hidden volume mode. This is bogus. I'll explain that if you want.)
Second, you appear to not understand how crypto works. Two layers are better than one, right? So double ROT13 encryption is stronger than single ROT13, right? You're running smack into a major, well-known area of crypto. A lot of ciphers do not composite themselves well. You are almost always better off just picking one algorithm with a strong keysize than a composition of multiple algorithms.
Third, how do you plan on managing all of your keys? Key management is a thorny enough problem in the best of times. By relying on multiple keys you're multiplying the problem immensely.
You really need to do some basic research in crypto.
Also, I'm unaware of any credible source that says steel-jacketed rounds are "used so often in assassinations". If you can point to a historical assassination that took place with steel-jacketed rounds, I'd be interested in hearing it.
The 7.62x39 Russian round has a massive taper to it, which means you can get away with using just about anything for the cartridge. The round was designed that way for a reason; it was thought that, given the Soviet Union's relative lack of manufacturing ability, the ability to make cartridges out of damned near anything would outweigh the ballistic tradeoffs that went into the highly-tapered round.
NATO has always had excellent manufacturing resources. Thus, NATO has always used a very, very shallow taper. Typically, the cartridge wall is less than one degree off straight vertical. This means NATO has to use brass cartridges for reliable feeding--steel and other metals just won't cut it.
Moral of the story: don't use steel cartridges in anything that's got a shallow taper.
A couple of last pieces of advice for you.
:)
First, don't worry about struggling in your classes. Generally speaking, it's the people who struggle who succeed the most later. People who sail through their courses without ever having to challenge themselves tend to crash and burn in the Real World the first time they run into something bigger than they are. If you're struggling, keep struggling. Don't quit. Don't give up. You might discover you're capable of a lot more than you think--and that kind of growth experience will reward you big-time in the Real World. If it's any help, I'm a couple of months away from a Ph.D. and every single day I still have to fight like hell for the grades. It can either crush you, or you can learn how to savor it. I recommend the latter.
Second, have you emailed your advisor yet and arranged for an appointment?
If you want to take this to email, feel free.