cantos

Sadly, Crypto 2 seems to be delayed to Oct 15 now.

My knowledge of this topic is limited but I believe if you are saying that the majority of crypto libraries have had major bugs, in the sense that they are made trivial to break, that you are overreaching.

On the other hand if you are including minor bugs, that have a low impact on security, then you are surely right but this doesn't mean much. Minor bugs get caught even in audits of the code for nuclear power plants.

jerf started from two propositions, 1) "a sterotype exists" 2) "the study is correct" he argued that these propositions imply the proposition "a stereotype does not exist." This contradicts the starting propositions. If you accept his argument then one of the starting propositions must be false. It could be the first, the second or both. He has not said which he believes to be true or false so your response is groundless.

Yes algorithms courses are a bit of a grab bag. Really, whether you enjoy them just comes down to your interests. I loved learning algorithms because the important ideas can be conveyed without getting bogged down in applications. On top of that a lot of what I learned in CS will be useless in 20 years, but algorithms have lasting value.

If you are really worried about government or government contractors building quantum computers in secret to break RSA in order to read your email you can just encrypt with either NTRU or McElice schemes which have been around for a while and aren't known to be breakable with an efficient quantum computer.

Of course if you are truly paranoid you might believe that the government knows how to break these schemes as well. In that case I have a great deal on bulk orders of carrier pigeons that might interest you

It bothers me that finding someone's location is such a problem since the technology exists to do it. How much would it cost to track a boat by GPS? Search and rescue missions over ocean must cost a fortune. Why don't governments subsidize the cost of GPS tracking?

Average-case complexity is a not a topic I know a lot about, and I can't easily get the paper itself, but what the abstract seems to say is that for some particular NP complete problem, if an efficient average case algorithm exists for that problem then efficient average case algorithms exist for all NP complete problems. There is no mention of showing that such an algorithm does not exist.

My reference is Impagliazzo's 1995 survey paper "A Personal View of Average-Case Complexity" where he lays out five possible worlds based on open problems in complexity theory. He calls the world where P!=NP but all NP problems are easy on average "Heuristica." This is still an open problem as far as I know.

On your second point I can say a bit more. Cryptosystems in general do not need all instances to be hard. With RSA for example, there are all kinds of weird attacks, like the modulus n can easily be factored if phi(n) or phi(phi(n)) are products of small primes. There is no need to filter out these cases because the probability of them occurring is so small. There are cryptosystems where an arbitrary instance of the problem is as hard as the average case. This was a notable selling point for lattice cryptosystems when they were first invented.

In the RSA case the probability of these corner case attacks decreases with the size of the instance. So for current parameters the probability is near zero. However, even if you only had a scheme where the probability didn't diminish with the instance size and there are attacks that you can't check for, you can still securely send messages. Say the probability that your key generation algorithm gives you an instance that is hard is 50% (or any constant). You can securely send messages with arbitrarily small probability of having your message decrypted by using multiple keys and breaking up your message with a secret sharing scheme (Shamir's for example) and encrypting each message share with each of the keys. The attacker, able to only get a constant number of decrypted message shares will not be able to get decrypt your message.

Apparently it is very hard to prove results in average case complexity theory. We don't even know if computational problems that are hard on average assuming P!=NP exist, let alone actually designing a cryptosystem out of one.

There are two things wrong with this. First, you are assuming that a nonzero fraction of people will sign up for every open-membership community available to them, frequent, and vote in each such community. Realistically most people probably can't do this for more than ten communities. Second, even if there is eventually convergence it may not occur quickly. For example, the universe will eventually reach a state of maximum entropy but it isn't something that any of us need to worry about today.

Let me be more specific. All that is required is "reasonable suspicion" in order to require access to all the files on your computer, unencrypted. "Reasonable suspicion" is a very weak requirement, as you can see from the document linked to in the techdirt article, and is exactly the same as what is needed for an extended physical search or an extended search of non-electronic property. In other words, there are no special considerations that apply to property just because it is electronic.

I postulate that it would be a good place to start.

All electronic devices are subject to search at the U.S. border.

http://www.dhs.gov/sites/default/files/publications/crcl-bor...

I've often heard the claim that elliptic curve cryptography is not used much in practice compared to RSA. I don't doubt its true but I would like to have some evidence for it so I can also say it without being a parrot.

I don't know anything about real world implementations of cryptography. How can I go about getting data that RSA is more widely used?

It's either collecting call metadata on US citizens or open war mongering? I was going to say that you're giving a false choice but then I realized there doesn't really seem to be a connection between the choices you're giving.

I agree their front page is overloaded with silly human interest stories and other fluff.

However, this is an update to an older story that was apparently broken on May 11th 2006 by USA today. It was covered by CNN tv on that day:

http://mediamatters.org/research/2006/05/11/despite-bipartis...

I agree. I email my friends, or see them in person so I know what's going on in their lives. Too often people only want to analyze facebook as an organizational tool. But there is a great entertainment component built in as well.

You get to learn the kind of personal information about your past acquaintances that otherwise you could only get by going to a reunion. You can find out if anyone you thought would be successful has ended up struggling, if anyone you thought was a slacker has done something interesting, if that person who is attractive, and successful is somehow also a nice person, etc.

Spending a few minutes looking at this kind of trivia can be a lot more fun than yet another youtube cat and the game only gets more interesting the more friends you have on facebook.

Here's a transcript

http://www.script-o-rama.com/movie_scripts/f/food-inc-script...

Several people in the farm industry are interviewed. Their statements are not questioned or further investigated by the filmmakers.

The study of solutions to equations only in the positive integers, or other subsets of integers also falls under Diophantine equations, as far as I know.

Subset sum problems are obviously decidable since the number of values that must be tried to find a solution is finite. However, subset sum is NP complete even when restricted to positive integers [Garey and Johnson, p223] so there is no polynomial time algorithm.

I don't have access to the original paper but from the summary here http://www.epi.umn.edu/cvdepi/study.asp?id=13 it looks like the study was only observational, roles were not randomly assigned.

I had a brief look at the paper. I got stuck on the section about scalability. I can't see how that could be implemented so that authentication can be done given that the nodes are untrusted (by which I mean implemented with a much smaller amount of computation and storage than was required in the non-optimized approach).

If any evidence of the kind ever came out it would be the top story for every news organization in the US.

So logically, since we all know with unshakable certainty that the NSA has such capabilities, they must be suppressing and controlling the media.

The changes are good.

On another note, don't buy into golden ratio hype. The supposed "beauty" of this ratio and its appearance "over and over again" in nature is one of those myths that just can't be killed. Every human should be made to read

http://www.lhup.edu/~dsimanek/pseudo/fibonacc.htm

or something equivalent.

Attempted proofs of Fermat's Last theorem by cranks used to be so common that Edmund Landau, a German mathematician, had a form letter for them: “Dear Sir/Madam: Your proof of Fermat’s Last Theorem has been received. The first mistake is on page _____, line _____.”

I have sometimes seen notes on the pages of prominent mathematicians that they don't have time to examine unsolicited attempts at major problems by amateurs so there must still be a good number. I also have known someone whose sibling is a software engineer and whose hobby is trying to resolve P ? NP.

The most dramatic example I know of someone who is older and also not a well known who found a major result is Kurt Heegner. He was a 59 year old private tutor and radio engineer with no previous published results when he proved the Class Number 1 problem. His proof was initially rejected by the mathematical establishment and he died before learning that the proof was a major advance and essentially correct.

http://en.wikipedia.org/wiki/Stark%E2%80%93Heegner_theorem

This story and Heegner's are particularly interesting because over the years some prominent mathematicians have stated that they believe mathematical creative declines rapidly with age.

I see now. I guess since there wasn't a closing quotation mark my brain just decided to invent one at a random point.

As far as I can tell, nothing in your second link is inconsistent with anything Scott has written.

Real quantum computers don't exist. If one did exist it would need to factor numbers much larger than 4096 bits efficiently for it to be considered a real quantum computer.

If airlines really believed that use of electronics could bring down an aircraft then they would ban passengers from using them entirely. Allowing passengers to take them on the plane and simultaneously claiming they are extremely dangerous is simply confusing. The passengers guess that the risk is being exaggerated as a way to control them so they resist on principle rather than because they care very much about using the devices.

There are 2 mostly distinct branches of number theory additive and multiplicative. Integer factorization is related to multiplicative number theory, but not really additive (as far as is known). This is a result in additive number theory so you shouldn't be any more concerned than say if a major problem in graph theory or differential equations was solved.

The fact that the security of a cryptosystem can only degrade over time is what I find so interesting about them. You can't just plug in a cryptosystem and forget about it. If you want real security you will regularly have to make changes.

I think linking to journal articles is a good thing even when they are paywalled like this but please give some context and a summary of the results.