**Adaptive Preimage Resistance Analysis Revisited:\\ Requirements, Subtleties and Implications**

*Donghoon Chang and Moti Yung*

**Abstract: **In the last few years, the need to design new cryptographic hash
functions has led to the intense study of when desired hash
multi-properties are preserved or assured under compositions and
domain extensions. In this area, it is important to identify the
exact notions and provide often complex proofs of the resulting
properties. Getting this analysis right (as part of provable security
studies) is, in fact, analogous to cryptanalysis. We note that it is
important and quite subtle to get indeed the ``right'' notions and
properties, and ``right'' proofs in this relatively young
area. Specifically, the security notion we deal with is ``adaptive
preimage resistance'' (apr) which was introduced by Lee and Park as an extension of ``preimage resistance'' (pr). In
Eurocrypt 2010, in turn, Lee and Steinberger already
used the apr security notion to prove ``preimage awareness'' and
``indifferentiable security'' of their new double-piped mode of
operation. They claimed that if $H^P$ is collision-resistant (cr) and apr,
then $F(M)=\mathcal{R}(H^P(M))$ is indifferentiable from a variable
output length (VIL) random oracle $\mathcal{F}$, where $H^P$ is a
function based on an ideal primitive $P$ and $\mathcal{R}$ is a fixed
input length (FIL) random oracle. However, there are some limitations in their claim, because they considered only indifferentiability security notion in the information-theoretic adversarial model, not in the computation-theoretic adversarial model. As we show in the current
work, the above statement is \textit{not} correct in the computation-theoretic adversarial model. First in our
studies, we give a counterexample to the above. Secondly, we describe
\textit{a new requirement} on $H^P$ (called ``admissibility'') so that
the above statement is correct even in the computation-theoretic adversarial model. Thirdly, we show that apr is, in fact,
not a strengthened notion of preimage resistance. Fourthly, we
explain the relation between preimage awareness and cr+apr+(our new
requirement) in the computation-theoretic adversarial model. Finally, we show that a polynomial-based mode of
operation \cite{LeSt10} satisfies our new requirement; namely, the
polynomial-based mode of operation with fixed-input-length random
oracles is indifferentiable from a variable-input-length random oracle in the computation-theoretic adversarial model.

**Category / Keywords: **secret-key cryptography / hash function, adaptive preimage resistance

**Date: **received 16 Apr 2012

**Contact author: **pointchang at gmail com

**Available format(s): **Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

**Version: **20120422:224000 (All versions of this report)

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]