Welcome to the resource topic for 2012/209
Title:
Adaptive Preimage Resistance Analysis Revisited:\ Requirements, Subtleties and Implications
Authors: Donghoon Chang, 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.
ePrint: https://eprint.iacr.org/2012/209
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .