---
res:
bibo_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.@eng
bibo_authorlist:
- foaf_Person:
foaf_givenName: Grégory
foaf_name: Demay, Grégory
foaf_surname: Demay
- foaf_Person:
foaf_givenName: Peter
foaf_name: Gazi, Peter
foaf_surname: Gazi
foaf_workInfoHomepage: http://www.librecat.org/personId=3E0BFE38-F248-11E8-B48F-1D18A9856A87
- foaf_Person:
foaf_givenName: Ueli
foaf_name: Maurer, Ueli
foaf_surname: Maurer
- foaf_Person:
foaf_givenName: Björn
foaf_name: Tackmann, Björn
foaf_surname: Tackmann
bibo_doi: 10.1007/978-3-319-17470-9_10
bibo_volume: 9063
dct_date: 2015^xs_gYear
dct_language: eng
dct_publisher: Springer@
dct_title: Query-complexity amplification for random oracles@
...