Q:

How is padding oracle attack mitigated by encrypt-then-MAC?

Let us suppose Alice sends a message to Bob.
As far as I know, the most popular scheme of MAC-then-encrypt is as follows: Alice computes the HMAC of the plaintext using her private key, and then encrypts plaintext+MAC by random one-time symmetric key, which is, in turn, encrypted by Bob's public key.
Padding oracle attack allows Eve to reconstruct the plaintext+MAC by sending modified versions of Alice's message to Bob and observing whether the modified version will trigger padding error or MAC verification error (when Bob will try to decrypt the encrypted message by symmetric key).
It is said (e.g. Should we MAC-then-encrypt or encrypt-then-MAC?) that switching to encrypt-then-MAC should mitigate the possibility of attack.
In that scenario, Alice first encrypts plaintext by random one-time symmetric key, which is, in turn, encrypted by Bob's public key, and sends both encrypted message and its HMAC computed using her private key.
I don't see how that prevents padding oracle attack, as long as Bob accepts messages from everyone (including Eve). Eve still could modify Alice's encrypted message, compute HMAC using Eve's private key, and send it to Bob.
Does encrypt-then-HMAC actually prevent padding oracle attack in this scenario?

A:

The biggest issue with padding oracle attacks are when the padding is not very carefully implemented (for example if using EtM you must calculate the MAC over everything - including the padding). To pre-empt references to the classic Belare-Namprempre paper, be wary - their results do not apply to modern primitives, since nowadays we prove security differently. See instead the relevant Namprempre-Rogaway-Shrimpton paper from Eurocrypt 2014 (discussed here).
Padding oracle attacks are (supposed) to be mitigated by only presenting a single error. This is pretty well standard now (in that a sensible scheme will just say 'invalid' rather than 'padding wrong' etc), but timing errors exist that allow you to differentiate padding errors from other errors.
The idea is the in Encrypt-then-HMAC, you are always calculating the MAC over the entire message. So, let Bob receive a message, which he will parse as $(C||T)$. He will calculate $HMAC(C)=^?=T$. He can do this without caring how $C$ was put together, and as such calculating/checking the MAC won't leak any information about what's within $C$.
Conversely, suppose we have MtE. Then he receives $C$, for which he believes $C=E(M||T)$, with $T=HMAC(M)$. Having decrypted $C$ to get $M′||T′$, he now has to work out how to calculate a MAC over $M′$. This is where the padding oracle occurs, because the decryption algorithm has to work out how much padding there should be, leaking information about the message.

