**Query-Complexity Amplification for Random Oracles**

*Grégory Demay and Peter Gaži and Ueli Maurer and Björn Tackmann*

**Abstract: **Increasing the computational complexity of evaluating a hash
function, 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$.

**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

[ Cryptology ePrint archive ]