Can the encrypt-and-authenticate method result in secure authenticated encryption if the MAC scheme has unique tags（non-deterministic）？

Question

If we use non-deterministic MACs in encrypt-and-authenticate approach， is it secure？

Answer 1

Not necessarily. Let $M$ be a secure deterministic MAC like HMAC-SHA256. Define the randomized MAC $M'_{k, \rho}(m) := M_k(m) \mathbin\| \rho$; that is, $M'$ just appends the randomization to the MAC. Then encrypt-and-authenticate with $M'$ still leaks message equality, even though the MAC is technically randomized.