You are looking at a specific version 20170527:000812 of this paper. See the latest version.

Paper 2017/461

Context-Restricted Indifferentiability: Generalizing UCE and Implications on the Soundness of Hash-Function Constructions

Daniel Jost and Ueli Maurer

Abstract

Understanding how hash functions can be used in a sound manner within cryptographic protocols, as well as how they can be constructed in a sound manner from compression functions, are two important problems in cryptography with a long history. Two approaches towards solving the first problem are the random oracle model (ROM) methodology and the UCE framework, and an approach to solving the second problem is the indifferentiability framework. This paper revisits the two problems and the above approaches and makes three contributions. First, indifferentiability, which comes with a composition theorem, is generalized to context-restricted indifferentiability (CRI) to capture settings that compose only in a restricted context. Second, we introduce a new composable notion based on CRI, called RO-CRI, to capture the security of hash functions. We then prove that a non-interactive version of RO-CRI is equivalent to the UCE framework, and therefore RO-CRI leads to natural interactive generalizations of existing UCE families. Two generalizations of split UCE-security, called strong-split CRI-security and repeated-split CRI-security, are introduced. Third, new, more fine-grained soundness properties for hash function constructions are proposed which go beyond collision-resistance and indifferentiability guarantees. As a concrete result, a new soundness property of the Merkle-Damgard construction is shown: If the compression function is strong-split CRI-secure, then the overall hash function is split secure. The proof makes use of a new lemma on min-entropy splitting which may be of independent interest.

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Keywords
IndifferentiabilityUCEhash functionsMerkle-Damgard construction
Contact author(s)
daniel jost @ inf ethz ch
History
2018-07-11: revised
2017-05-27: received
See all versions
Short URL
https://ia.cr/2017/461
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.