Increasing the computational complexity of evaluating a hashfunction, both for the honest users as well as for an

adversary, is a useful technique employed for example in

password-based cryptographic schemes to impede brute-force

attacks, and also in so-called proofs of work (used in

protocols like Bitcoin) to show that a certain amount of

computation was performed by a legitimate user. A natural

approach to adjust the complexity of a hash function is to

iterate it $c$~times, for some parameter

$c$, in the hope that any query to the scheme

requires $c$ evaluations of the underlying

hash function. However, results by Dodis et al. (Crypto

2012) imply that plain iteration falls short of achieving

this goal, and designing schemes which provably have such a

desirable property remained an open problem.

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$.