**Abstract.**
Much recent work in cryptography attempts to build secure schemes
in the presence of side-channel leakage or leakage caused by malicious software,
like computer viruses. In this setting, the adversary may obtain some additional
information (beyond the control of the scheme designer) about the internal secret
state of a cryptographic scheme. Here, we consider key-evolution schemes that
allow a user to evolve a secret-key *K*_{1}
via a *deterministic* function
*f*, to get updated
keys *K*_{2} = *f*(*K*_{1}),
*K*_{3} = *f*(*K*_{2}), ….
Such a scheme is *leakage-resilient* if
an adversary that can leak on the first *i* steps of the evolution process does not get
any useful information about any future keys. For such schemes, one must assume
some restriction on the complexity of the leakage to prevent *pre-computation attacks*,
where the leakage on a key *K _{i}*
simply pre-computes a future key

Much of the prior work on this problem, and the restrictions made therein, can be divided into two types. Theoretical work offers rigor and provable security, but at the cost of having to make strong restrictions on the type of leakage and designing complicated schemes to make standard reduction-based proof techniques go through (an example of such an assumption is the “only computation leaks” axiom). On the other hand, practical work focuses on simple and efficient schemes, often at the cost of only achieving an intuitive notion of security without formal well-specified guarantees.

In this paper, we complement the two tracks via a middle-of-the-road approach.
On one hand, we rely on the random-oracle model. On the other hand, we show
that even in the random-oracle model, designing secure leakage-resilient schemes
is susceptible to pitfalls. For example, just assuming that leakage “cannot evaluate
the random oracle” can be misleading. Instead, we define a new model in which
we assume that the “leakage” can be any arbitrary *space bounded* computation
that can make random oracle calls itself. We connect the space-complexity of a
computation in the random-oracle modeling to the *pebbling complexity* on graphs.
Using this connection, we derive meaningful guarantees for relatively simple keyevolution
constructions.

Our scheme is secure also against a large and natural class of active attacks, where
an attacker can leak as well as tamper with the internals of a device. This is
especially important if the key evolution is performed on a PC that can be attacked
by a virus, a setting considered by prior work in the *bounded retrieval model
(BRM)*). This paper provides the first scheme were the adversary in the BRM can
also modify the data stored on the machine.

**Keywords:**
graph pebbling, leakage-resilient cryptography, bounded-storage model