This paper formalizes explicitly what it means for a given scheme to amplify the query complexity of a hash function. In the random oracle model, the goal of a secure query-complexity amplifier (QCA) scheme is captured as transforming, in the sense of indifferentiability, a random oracle allowing $R$ queries (for the adversary) into one provably allowing only $r < R$ queries. Turned around, this means that making $r$ queries to the scheme requires at least $R$ queries to the actual random oracle. Second, a new scheme, called collision-free iteration, is proposed and proven to achieve $c$-fold QCA for both the honest parties and the adversary, for any fixed parameter~$c$.
Category / Keywords: foundations / hash functions, random oracle, indifferentiability, moderately hard functions Original Publication (with minor differences): ICITS 2015 Date: received 7 Apr 2015, last revised 12 Jun 2015 Contact author: gregory demay at inf ethz ch Available format(s): PDF | BibTeX Citation Note: Added a section to show more explicitly that the evaluation of a query-complexity amplifier scheme requires a certain minimum amount of queries to the underlying random oracle. Version: 20150612:081707 (All versions of this report) Short URL: ia.cr/2015/315