International Association for Cryptologic Research

International Association
for Cryptologic Research

IACR News item: 10 April 2015

Grégory Demay, Peter Gaži, Ueli Maurer, Björn Tackmann
ePrint Report ePrint Report
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$.

Expand

Additional news items may be found on the IACR news page.