Paper 2018/804
Double-block Hash-then-Sum: A Paradigm for Constructing BBB Secure PRF
Nilanjan Datta, Avijit Dutta, Mridul Nandi, and Goutam Paul
Abstract
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 Double-block Hash-then-Sum or in short (DbHtS). A DbHtS construction, as the name implies, computes a double block hash on the message and then sum 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 $2n/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.
Note: A Minor change in the constant of the 2K-ECBC Security Bound.
Metadata
- Available format(s)
-
PDF
- Category
- Secret-key cryptography
- Publication info
- Published by the IACR in FSE 2019
- Keywords
- DbHtSBeyond BirthdayCover-freeBlock-wise UniversalPRFSum of PRP
- Contact author(s)
-
nilanjan_isi_jrf @ yahoo com
avirocks dutta13 @ gmail com
mridul nandi @ gmail com
goutam k paul @ gmail com - History
- 2018-09-10: revised
- 2018-09-06: received
- See all versions
- Short URL
- https://ia.cr/2018/804
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2018/804,
author = {Nilanjan Datta and Avijit Dutta and Mridul Nandi and Goutam Paul},
title = {Double-block Hash-then-Sum: A Paradigm for Constructing {BBB} Secure {PRF}},
howpublished = {Cryptology {ePrint} Archive, Paper 2018/804},
year = {2018},
url = {https://eprint.iacr.org/2018/804}
}
