What kind of computer science program doesn't have an algorithms course?

Sort of, in that it would be really weird if it wasn't true. It is generally thought that primes follow a certain distribution (i.e. any given odd number has a certain probability of being prime, decreasing as the number gets larger). We know there are an infinite number of primes. That means this probability never reaches zero. If it is always non-zero, then there is also always some non-zero probability that we get two primes in a row (just the square of the probability). If there were not infinite twin primes, then it would mean that the "prime event" is not i.i.d., which is not impossible but would be strange. For there to be a point where there ceases to be twin primes would imply some weird arbitrary limit, beyond which primes don't want to "clump" any more.

You mean multiply? If you add then you get ambiguous cases, i.e 2+3=5 where you don't know if it was just five or if it was two and three. If you want to add you would have to do powers of two. Pretty cool, but it has nothing to do with the article :D

Depends on what you mean by "construct". You can just start at N+1 and test everything for primality. We know now that primality testing is in P, and the prime number theorem tells us that the distribution of primes is dense, so this is even efficient.

Nice that they included some highlights of these features in the summary then instead of saying nothing that the title wouldn't tell you just as well... oh wait.

I think he just didn't read the sentence correctly.

I'm not sure what you mean about the labeling thing. Your labels could all be encrypted and shuffled so he doesn't even know which file is file 50 (although it turns out this is not necessary). The process I am describing is a form of private information retrieval if you want more information. It does not strictly require FHE, but is enabled by it.

The serve would always learn the circuit you are using, so he would be able to tell which function you are evaluating over your data. There are methods to hide the function as well, but that feature is not provided by basic FHE.

Not sure where you got this idea, it is certainly necessary that P != NP for almost all of cryptography. If P = NP, then there are no problems in NP which are easy to come up with but hard to solve. Cryptography relies crucially on this asymmetry, it should be easy for a legitimate user but hard for someone without the key.

Sure there are classes harder than NP, but it is necessary that our problems be in NP because otherwise it would be intractable for legitimate users. Take public key cryptography for example. The problem it is based on needs to be in NP because, given a ciphertext encrypted with one half of the key, you need to be able to efficiently verify (decrypt) it with the other half. If your encryption was in NEXP, but not in NP, it would take exponential time to decrypt even for users with the key. This is just one example, but I promise you that all our useful problems need to be in NP.

If our problems need to be in NP, then they also must not be in P. If P = NP, then it takes as long to verify a problem as it does to actually solve it. It would be just as fast to break an encryption as it is to decrypt with the key. A good explanation is in Impagliazzo's worlds. Interestingly, it necessary but not actually sufficient for P != NP. For instance, hard problems could exist but not trapdoor functions, which would make public key encryption impossible.

It's only possible if P != NP. Hashing itself is impossible if P=NP, along with all the rest of cryptography save for information theoretically secure constructions. You might as well say encryption only exists if P != NP.

A homomorphic search would not operate the way you are thinking. It would have to compute over the entire set of possible results (otherwise, as you say, the adversary learns at least that some results are not possible) and piece by piece obliviously combine them. As a simplification, if you know your search is going to only return one result then you can have the server run a circuit over each file which evaluates whether that file will be the result or not. If it is, out comes an encrypted one, if it is not then it will be an encrypted zero. The server then multiplies the file itself by this encrypted result and adds it to a running total. All the files which weren't chosen will be zeroed out and the single file you want will end up in this "register", although the server has no idea which one you wanted and which ones were zeroed out.

Nobody said these things weren't possible, just that homomorphic encryption out of the box does not do them. There are recent techniques for functional encryption, which use FHE as a component, that allow these exact scenarios. As you pointed out though, you have to be very careful if you don't want to ruin security. The way they work now, you can supply a server with a specific token which allows him to evaluate one very specific function on your encrypted data and get the plaintext result of that function. For instance, you could give your email server a token which allows him to run spam filtering over your incoming emails and output a plaintext bit which is '1' if it is spam and '0' if it is not. The security property of these schemes is that you cannot learn any information other than the output of this function run over encrypted data. It is veeery tricky at this point because you could leak some dangerous information unknowingly, but the techniques do exist.

Nah because it is also semantically secure. For every plaintext value, there are lots and lots of different ciphertext values (it is a one-to-many mapping). So many, in fact, that knowing the plaintext value of any particular ciphertext doesn't give you any good information.

You do have the problem that anyone can come up with any valid ciphertext and jam it into your computation wherever they want, but we have some other cool stuff for verifying that only authenticated ciphertexts were used and that the function the guy evaluated was the one he was supposed to do. Lots of very cool stuff :-)

So, let me first say that the main selling point for this technology is that it allows you to outsource your computation. You can use a low powered device like a cell phone and take advantage of more powerful computation in the cloud, while maintaining data privacy. You are correct that certain things will be leaked, like if I am storing encrypted email and I search for all emails sent by so-and-so then the server would learn how many emails I have from that guy. This is still a huge advantage over what we have now.

Now, I can outline a cool use that you probably have not thought of which is a little different. Imagine that a server is storing some really sensitive stuff for me. Obviously I don't trust the server so I am encrypting all my files. If he is really sneaky, however, he can learn something about the contents of those files by watching when, where and how often I access them. We call this the access pattern, and usually people just write this off as a cost of doing business. However, with homomorphic encryption we can hide even that!

Since I can evaluate any program homomorphically over my data, I write a program that says "return file number x" and give it an encrypted value, say 50, for x. The server now evaluates this program, with my encrypted 50, over the entire set of files. What he gives back to me is my file that I wanted, but from his point of view he can't actually tell which file he gave me! All he knows is he ran a circuit over all the files in the database, with my input that specifies which one I want, but he can't tell what my input is because it is encrypted.

If your scheme is over a finite field, then E(a) - E(a) will just be a literal zero. Technically this is an encryption of zero, but it has not security as it is an encryption of zero under every possible key. Knowing it doesn't really give anything to an adversary.

It is not that the algorithms have not been well tested. Actually the "algorithms" do not really need to be tested as we have security proofs that reduce to hardness assumptions. The problem is that the hardness assumptions simply have not been around long enough to be thoroughly vetted. RSA is based on the hardness of the RSA assumption (related to the hardness of factoring) which has had 40 years to be broken. These new homomorphic encryption schemes have been around for at most 4 years, which is NOTHING in the scheme of things.