International Association for Cryptologic Research

International Association
for Cryptologic Research

IACR News item: 29 December 2013

Adam Smith, Ye Zhang
ePrint Report ePrint Report
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.

Expand

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