Paper 2013/864

Near-linear time, Leakage-resilient Key Evolution Schemes from Expander Graphs

Adam Smith and Ye Zhang

Abstract

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.