Should we sign-then-encrypt, or encrypt-then-sign?
...
Do the same issues with (symmetric-key) MAC-then-encrypt apply to (public-key) sign-then-encrypt?
Yes. From a security engineering standpoint, you are consuming unauthenticated data during decryption if you mac-then-encrypt or sign-then-encrypt. A very relevant paper is Krawczyk's The Order of Encryption and Authentication for Protecting Communications.
The order may (or may not) be problematic in practice for you. But as the SSL/TLS folks have repeatedly shown, its problematic in practice.
Another important paper is cited by D.W. and Sashank: Don Davis' Defective Sign & Encrypt in S/MIME, PKCS#7, MOSS, PEM, PGP, and XML.
I think the primitive of sign vs mac is less important. With all things being equal (like security levels, key management and binding), then one of the top criteria is efficiency. Obviously, a symmetric cipher is more efficient than an asymmetric cipher.
Data authentication is a different property than entity authentication. You can use a MAC for data authentication and a signature for entity authentication.
But its not entirely clear to me if you want data authentication or entity authentication. The security goal you state in (b) begs for data authentication (a MAC), and not entity authentication (a signature).
I think that's why CodesInChaos said he signs then performs authenticated encryption. That's another way to say he signs-then-encrypts-then-macs. If the MAC is good, then he decrypts and verifies the signature to verify who sent the message. If the MAC is bad, then he does not bother decrypting - he just returns FAIL.
If you look at the link provided by Sashank, CodesInChaos' fix is effectively Sign/Encrypt/Sign from Section 5.2 of the paper. And D.W's solution is effectively Naming Repairs from Section 5.1.
There's a third option that's not readily apparent. It combines Encrypt-Then-MAC for bulk encryption with public key cryptography. Its also IND-CCA2 as D.W. suggested you strive for.
The option is an Integrated Encryption Scheme. There are two of them that I am aware. The first is Shoup's ECIES, which operates elliptic curves; the second is Abdalla, Bellare and Rogaway's DLIES, which operates over integers. Crypto++ provides both ECIES and DLIES. Bouncy Castle provides ECIES.
ECIES and DLIES combine a Key Encapsulation Mechanism (KEM) with a Data Encapsulation Mechanism (DEM). The system independently derives a symmetric cipher key and a MAC key from a common secret. Data is first encrypted under a symmetric cipher, and then the cipher text is MAC'd under an authentication scheme. Finally, the common secret is encrypted under the public part of a public/private key pair. The output of the encryption function is the tuple {K,C,T}, where K is the encrypted common secret, C is the ciphertext, and T is the authentication tag.
There's some hand waiving around the use of a symmetric cipher. The schemes use a stream cipher that XORs the plaintext with the output of the KDF. The design choice here was to avoid a block cipher with padding. You could use a block cipher in a streaming mode, like AES/CTR to the same effect.
There is some hand waiving around the "common secret" since its actually the result of applying a Key Agreement function and later digesting the shared secret with a KDF. The Key Agreement function uses the recipient's static public key and an ephemeral key pair. The ephemeral key pair is created by the person doing the encryption. The person performing the decrypt uses their public key to perform the other half of the key exchange to arrive at the "common secret".
The KEM and the DEM avoid padding, so padding oracles are not a concern. That's why a KDF is used to digest the large "common secret" under the KEM. Omitting the padding vastly simplifies the security proofs of the system.
