NIST logo

Publication Citation: Adaptive Preimage Resistance Analysis Revisited: Requirements, Subtleties and Implications

NIST Authors in Bold

Author(s): Dong H. Chang; Moti Yung;
Title: Adaptive Preimage Resistance Analysis Revisited: Requirements, Subtleties and Implications
Published: April 16, 2012
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 in [5] as an extension of ,preimage resistanceŠ (PR). In Eurocrypt 2010, in turn, Lee and Steinberger [6] 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 HP is collision-resistant and APR, then F(M) = R(HP (M)) is indifferentiable from a variable output length (VIL) random oracle F, where HP is a function based on an ideal primitive P and R is a fixed input length (FIL) random oracle. However, as we show in the current work, the above statement is not correct. First in our studies, we give a counterexample to the above. Secondly, we describe a new requirement on HP (called ,admissibilityŠ) so that the above statement is correct. Thirdly, we show that APR is, in fact, not a strengthened notion of preimage resistance (PR). Fourthly, we explain the relation between preimage awareness and CR+APR+(our new requirement). Finally, we show that a polynomial-based mode of operation [6] 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 (as originally claimed, but based on the refined arguments and subtleties presented here).
Citation: IACR Cryptology ePrint Archive
Pages: 12 pp.
Keywords: Adaptive Preimage Resistance, Preimage Awareness, Indifferentiability
Research Areas: Computer Security, Cybersecurity, Information Technology, Math
PDF version: PDF Document Click here to retrieve PDF version of paper (281KB)