Symmetric and Dual PRFs from Standard Assumptions: A Generic Validation of a Prevailing Assumption

Mihir Bellare; Anna Lysyanskaya

Paper 2015/1198

Symmetric and Dual PRFs from Standard Assumptions: A Generic Validation of a Prevailing Assumption

Mihir Bellare

, University of California, San Diego

Anna Lysyanskaya, Brown University

Abstract

A two-input function is a dual PRF if it is a PRF when keyed by either of its inputs. Dual PRFs are assumed in the design and analysis of numerous primitives and protocols including HMAC, AMAC, TLS 1.3 and MLS. But, not only do we not know whether particular functions on which the assumption is made really are dual PRFs; we do not know if dual PRFs even exist. What if the goal is impossible? This paper addresses this with a foundational treatment of dual PRFs, giving constructions based on standard assumptions. This provides what we call a generic validation of the dual PRF assumption. Our approach is to introduce and construct symmetric PRFs, which imply dual PRFs and may be of independent interest. We give a general construction of a symmetric PRF based on a function having a weak form of collision resistance coupled with a leakage hardcore function, a strengthening of the usual notion of hardcore functions we introduce. We instantiate this general construction in two ways to obtain two specific symmetric and dual PRFs, the first assuming any collision-resistant hash function, and the second assuming any one-way permutation. A construction based on any one-way function evades us and is left as an intriguing open problem.

Metadata

Available format(s): PDF
Category: Foundations
Publication info: A minor revision of an IACR publication in JOC 2024
DOI: 10.1007/S00145-024-09513-6
Keywords: HMAC PRF Dual PRF One-Way Function Hardcore Function Extractor Hash Function
Contact author(s): mbellare @ ucsd edu
anna_lysyanskaya @ brown edu
History: 2024-09-20: last of 3 revisions; 2015-12-16: received; See all versions
Short URL: https://ia.cr/2015/1198
License: CC BY

BibTeX

@misc{cryptoeprint:2015/1198,
      author = {Mihir Bellare and Anna Lysyanskaya},
      title = {Symmetric and Dual {PRFs} from Standard Assumptions: A Generic Validation of a Prevailing Assumption},
      howpublished = {Cryptology {ePrint} Archive, Paper 2015/1198},
      year = {2015},
      doi = {10.1007/S00145-024-09513-6},
      url = {https://eprint.iacr.org/2015/1198}
}