Abstract:Double-block Hash-then-Sum (DbHtS) MACs are a class of MACs that aim for achieving beyond-birthday-bound security, including SUM-ECBC, PMAC_Plus, 3kf9 and LightMAC_Plus. Recently Datta et al. (FSE'19), and then Kim et al. (Eurocrypt'20) prove that DbHtS constructions are secure beyond the birthday bound in the single-user setting. However, by a generic reduction, their results degrade to (or even worse than) the birthday bound in the multi-user setting.
