@article{Datta_Dutta_Nandi_Paul_2018, title={Double-block Hash-then-Sum: A Paradigm for Constructing BBB Secure PRF}, volume={2018}, url={https://tosc.iacr.org/index.php/ToSC/article/view/7297}, DOI={10.13154/tosc.v2018.i3.36-92}, abstractNote={<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>}, number={3}, journal={IACR Transactions on Symmetric Cryptology}, author={Datta, Nilanjan and Dutta, Avijit and Nandi, Mridul and Paul, Goutam}, year={2018}, month={Sep.}, pages={36–92} }