TY - JOUR AU - Datta, Nilanjan AU - Dutta, Avijit AU - Nandi, Mridul AU - Paul, Goutam PY - 2018/09/03 Y2 - 2024/03/28 TI - Double-block Hash-then-Sum: A Paradigm for Constructing BBB Secure PRF JF - IACR Transactions on Symmetric Cryptology JA - ToSC VL - 2018 IS - 3 SE - Articles DO - 10.13154/tosc.v2018.i3.36-92 UR - https://tosc.iacr.org/index.php/ToSC/article/view/7297 SP - 36-92 AB - <p>SUM-ECBC (Yasuda, CT-RSA 2010) is the first beyond birthday bound (BBB) secure block cipher based deterministic MAC. After this work, some more BBB secure deterministic MACs have been proposed, namely PMAC_Plus (Yasuda, CRYPTO 2011), 3kf9 (Zhang et al., ASIACRYPT 2012) and LightMAC_Plus (Naito, ASIACRYPT 2017). In this paper, we have abstracted out the inherent design principle of all these BBB secure MACs and present a generic design paradigm to construct a BBB secure pseudo random function, namely <strong>Double-block Hash-then- Sum</strong> or in short (DbHtS). A DbHtS construction, as the name implies, computes a <em>double block hash</em> on the message and then <em>sum</em> the encrypted output of the two hash blocks. Our result renders that if the underlying hash function meets certain security requirements (namely cover-free and block-wise universal advantage is low), DbHtS construction provides 2<em>n</em>/3-bit security. We demonstrate the applicability of our result by instantiating all the existing beyond birthday secure deterministic MACs (e.g., SUM-ECBC, PMAC_Plus, 3kf9, LightMAC_Plus) as well as a simple two-keyed variant for each of them and some algebraic hash based constructions.</p> ER -