Paper 2020/1097

How to Build Optimally Secure PRFs Using Block Ciphers

Benoît Cogliati, Ashwin Jha, and Mridul Nandi

Abstract

In EUROCRYPT '96, Aiello and Venkatesan proposed two candidates for $ 2n $-bit to $ 2n $-bit pseudorandom functions (PRFs), called Benes and modified Benes (or mBenes), based on $ n $-bit to $ n $-bit PRFs. While Benes is known to be secure up to $ 2^n $ queries (Patarin, AFRICACRYPT '08), the security of mBenes has only been proved up to $ 2^{n(1-\epsilon)} $ queries for all $ \epsilon > 0 $ by Patarin and Montreuil in ICISC '05. In this work, we show that the composition of a $ 2n $-bit hash function with mBenes is a secure variable input length (VIL) PRF up to $ 2^{n-2} $ queries (given appropriate hash function bounds). We extend our analysis with block ciphers as the underlying primitive and obtain two optimally secure VIL PRFs using block ciphers. The first of these candidates requires $ 6 $ calls to the block cipher. The second candidate requires just $ 4 $ calls to the block cipher, but here the proof is based on Patarin's mirror theory. Further, we instantiate the hash function with a PMAC+/LightMAC+ like hash, to get six candidates for deterministic message authentication codes with optimal security.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
A major revision of an IACR publication in ASIACRYPT 2020
Keywords
PRFMACBenesmodified BenesPMAC+LightMAC+
Contact author(s)
ashwin jha1991 @ gmail com
History
2020-09-15: received
Short URL
https://ia.cr/2020/1097
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/1097,
      author = {Benoît Cogliati and Ashwin Jha and Mridul Nandi},
      title = {How to Build Optimally Secure PRFs Using Block Ciphers},
      howpublished = {Cryptology ePrint Archive, Paper 2020/1097},
      year = {2020},
      note = {\url{https://eprint.iacr.org/2020/1097}},
      url = {https://eprint.iacr.org/2020/1097}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.