tbmbob

Now if I actually brought these questions to an interview the interviewee could ruin my day by asking "what's the runtime complexity?"

This completely undermines the author's main point. Constraint solvers don't solve hard leetcode problems if they can't solve large instances quickly enough.

Many hard leetcode problems can be solved fairly simply with more lax runtime requirements -- coming up with an efficient solution is a large part of the challenge.

This is not quite true: the mathematical problems upon which they base their security, though related, have some important differences. Most significantly, the problem upon which this new implementation is based (Ring-Learning with errors) is theoretically much more time and space efficient than the problem upon which your linked implementation is based (approximate GCD).

To build off of the comments below, this attack is foiled by the fact that one message can be encrypted to one of a large number of ciphertexts.

As mentioned below, this is true for ElGamal. It is also true for all other styles of FHE scheme I'm aware of (including Ring-Learning With Errors based schemes, like this one).

In fact, if a message can only encrypt to one of a small number of ciphertexts, even more direct brute force attacks are often possible. For example, many FHE systems publish a public key. In this case, one can just encrypt E(1), E(2), etc oneself.

"If you need extra data to prove this "yes" in polynomial time, then the answer isn't a boolean anymore, but a boolean plus the extra data, so how can you still call that a yes/no problem?"

You are combining two distinct concepts: the answer and the 'evidence'. The answer to an NP-complete problem is always Yes or No. But, we say that we can "verify" a decision problem in polynomial time if, given an answer AND evidence, we can check that the answer is true.

For concreteness: the k-clique problem (determining if there's a clique of at least size k in a graph) is hard. But, if somebody told us the answer was Yes, and gave us appropriate evidence (say, a set of k nodes in the graph which form a clique), verifying would be easy.