"It is widely known that elliptic curve Diffie-Hellman is vulnerable to maliciously crafted public keys, where a honestly generated private key combined with a malicious public key may result in predictable output." Actually, there are well known ways to protect against that. For prime order curves (e.g. P256), all you need to do is verify that the public key is a point on the curve (and not the point at infinity).

I do not believe that Fujisaki-Okamoto protects against malicious public keys. What it protects against are malicious ciphertexts. The FO transform is run by the decapsulator (Bob in your example); this attack is against Alice, who does not perform it.

It appears that $N$ is defined two different ways, $N = pq$ and $N = p^2 - q^2$. What you mean is clear - it might be better if you didn't give those two different values the same name.

@PaŭloEbermann: the XOR sum not repeating is critical, but that can be done by keeping on a constant, and the other an incrementing sum - no unpredictability required

If you don't want to send the IV, one trick you could do with CBC is just prepend 16 bytes of anything to the plaintext and encrypt it with an arbitrary IV. Then, the decryptor picks an IV (unlikely to be the one the encryptor used), and decrypt that, and then strip off the first 16 bytes. Then, by magic, that's the original plaintext (!).

There's the observation that if you know the value of $s$ for a fixed $a$, then (unless $a$ has a tiny order, which is improbable if $a$ is selected randomly), you can factor $m$. This is how Shor's algorithm (which is a Quantum algorithm which recovers $s$) is used to factor.

These are the assumptions for a standard CCA attack. We generally assert that if a symmetric system isn't strong against such an attack, it's not considered secure.

@JasonS: that you for the correction - I fixed the text