We develop new schemes for deterministically updating a stored
cryptographic key that provide security against an internal
adversary who can control the update computation and leak bounded
amounts of information to the outside world. Our schemes are much
more efficient than the previous schemes for this model, due to Dziembowski,
Kazana and Wichs (CRYPTO 2011). Specifically, our update operation
runs in time quasilinear in the key length, rather than quadratic,
while offering a similar level of leakage resilience.
In order to design our scheme, we strengthen the connections between
the model of Dziembowski et al. and ``pebbling games\'\', showing that
random-oracle-based key evolution schemes are secure as long as the
graph of the update function\'s calls to the oracle has
appropriate combinatorial properties. This builds on a connection
between pebbling and the random oracle model first established by
Dwork, Naor and Wee (CRYPTO 2005). Our scheme\'s efficiency relies on the
existence (which we show) of families of ``local\'\'
bipartite expander graphs of constant degree.