If we use non-deterministic MACs in encrypt-and-authenticate approach， is it secure？
$\begingroup$
$\endgroup$
-
$\begingroup$ How would a non-deterministic MAC have unique tags? $\endgroup$ – Maeher May 17 '19 at 7:13
$\begingroup$
$\endgroup$
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.
answered May 16 '19 at 22:17
