Security of Truncated Permutation Without Initial Value

Lorenzo Grassi and Bart Mennink

Abstract

Indifferentiability is a powerful notion in cryptography. If a construction is proven to be indifferentiable from an ideal object, it can under certain assumptions instantiate that ideal object in higher-level constructions. Indifferentiability is a particularly useful model for cryptographic hash functions, and myriad results are known proving that a hash function behaves like a random oracle under the assumption that the underlying primitive (typically a compression function, a block cipher, or a permutation) is random. Recently, advances have been made in proving indifferentiability of one-way functions with fixed input length. One such example is truncation of a permutation. If one evaluates a random permutation on an input value concatenated with a fixed initial value, and truncates the output, one obtains a construction that is indifferentiable from a random function up to a certain bound (Dodis et al., FSE 2009; Choi et al., ASIACRYPT 2019). Security of this construction, however, is in part determined by the length of the initial value; omission of this fixed value yields an insecure construction. In this paper, we reconsider truncation of a permutation, and prove that the construction is indifferentiable from a random oracle, even if this fixed initial value is replaced by a randomized value. This randomized value may be the same for different evaluations of the construction, or freshly generated, up to the discretion of the adversary. The security level is the same as that of truncation with fixed initial value, up to collisions in the randomized value. We show that our construction has immediate implications in the context of parallel variable-length digest generation. In detail, we describe Cascade-MGF, that operates on top of any cryptographic hash function and uses the hash function output as randomized initial value in truncation. We demonstrate that Cascade-MGF compares favorably over earlier parallel variable-length digest generation constructions, namely Counter-MGF and Chained-MGF, in almost all settings.

Available format(s)
Category
Secret-key cryptography
Publication info
Preprint. Minor revision.
Contact author(s)
l grassi @ cs ru nl
b mennink @ cs ru nl
History
Short URL
https://ia.cr/2022/508

CC BY

BibTeX

@misc{cryptoeprint:2022/508,
author = {Lorenzo Grassi and Bart Mennink},
title = {Security of Truncated Permutation Without Initial Value},
howpublished = {Cryptology ePrint Archive, Paper 2022/508},
year = {2022},
note = {\url{https://eprint.iacr.org/2022/508}},
url = {https://eprint.iacr.org/2022/508}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.